Two-Pointer Patterns in Ruby

,

Two pointers are useful when moving one boundary changes the result monotonically. The pattern is not “put two variables in a loop”; the movement must let us prove that discarded candidates cannot be better.

3Sum Closest

Sort the array, fix one value, then move two pointers through the remaining range.

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
def three_sum_closest(numbers, target)
  raise ArgumentError, "at least three numbers are required" if numbers.length < 3

  values = numbers.sort
  closest = values[0, 3].sum

  0.upto(values.length - 3) do |index|
    left = index + 1
    right = values.length - 1

    while left < right
      sum = values[index] + values[left] + values[right]
      return target if sum == target

      closest = sum if (target - sum).abs < (target - closest).abs

      if sum < target
        left += 1
      else
        right -= 1
      end
    end
  end

  closest
end

Sorting costs O(n log n) and the nested scan costs O(n²), so total time is O(n²). Using sort instead of sort! avoids mutating the caller’s array as a surprise bonus feature.

Container With Most Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def max_area(heights)
  left = 0
  right = heights.length - 1
  best = 0

  while left < right
    width = right - left
    height = [heights[left], heights[right]].min
    best = [best, width * height].max

    if heights[left] <= heights[right]
      left += 1
    else
      right -= 1
    end
  end

  best
end

The shorter wall limits the area. Moving the taller wall inward only reduces width while keeping the same limiting wall, so it cannot improve the result. We move the shorter wall because only a taller replacement can compensate for the lost width.

  • Time complexity: O(n).
  • Extra space: O(1).

That proof is the pattern. The pointers are merely its employees.