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

Two Sum IV - Input is a BST

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