Two Sum Series
excerpt: This article covers the building blocks - two pointers, three way comparison and frequency counter.
tags: two-pointers-moving-towards-each-other three-way-comparison frequency-counter
In this article we will discuss problems in the two sum series:
- Two Sum
- Two Sum II
- Two Sum III - Data structure design
- Two Sum Less Than K
Precondition: Array is sorted
Two Sum Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def two_sum(nums, target)
i = 0
j = nums.size - 1
while i < j
sum = nums[i] + nums[j]
if sum == target
return [i, j]
elsif sum < target
i += 1
else
j -= 1
end
end
end
nums = [2,7,11,15]
target = 9
p two_sum(nums, target)
|
Two Sum III - Datastructure Design
Approach #1: Sort and use the same solution for the Two Sum problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class TwoSum
def initialize
@input = []
end
def add(number)
@input << number
end
def find(value)
@input.sort!
two_sum(@input, value)
end
def two_sum(nums, target)
i = 0
j = nums.size - 1
while i < j
sum = nums[i] + nums[j]
if sum == target
return true
elsif sum < target
i += 1
else
j -= 1
end
end
return false
end
end
|
Approach #2: Hashtable with frequency counter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class TwoSum
def initialize
@input = {}
end
def add(number)
if @input.include?(number)
@input[number] += 1
else
@input[number] = 1
end
end
def find(value)
for num in @input.keys
complement = value - num
if num != complement
if @input.include?(complement)
return true
end
elsif @input[num] > 1
return true
end
end
return false
end
end
|
The first attempt does not handle both true and false cases. Why is not possible to do the processing on the fly? The solutions are using auxiliary data structure.
- What should be the return value?
- Where should the return value be handled?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def wrapper(node, target)
if node.nil?
return
end
if node.val == target
return true
elsif target < node.val
wrapper(node.left, target)
else
wrapper(node.right, target)
end
return true
end
def find_target(root, k)
target = root.val - k
wrapper(root, target)
end
|
Don’t make the problem more difficult that it is by applying unnecessary constraints. There is no constraints on the space complexity. Since the input is a BST, we can traverse the tree in order and save the values in an array and apply the solution for Two Sum problem to solve it by using two pointers.
Working Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| # Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val = 0, left = nil, right = nil)
# @val = val
# @left = left
# @right = right
# end
# end
# @param {TreeNode} root
# @param {Integer} k
# @return {Boolean}
def two_sum(array, target)
i = 0
j = array.size - 1
while i < j
sum = array[i] + array [j]
if sum == target
return true
elsif sum < target
i += 1
else
j -= 1
end
end
return false
end
def inorder(node, values)
if node.nil?
return
end
inorder(node.left, values)
values << node.val
inorder(node.right, values)
end
def find_target(root, k)
values = []
inorder(root, values)
two_sum(values, k)
end
|
Building Blocks
- Two Pointers Moving Towards Each Other
- Three Way Comparison
- Frequency Counter