The two-pointer technique is a simple yet powerful algorithmic approach used to solve a variety of problems, especially those involving arrays, strings, or linked lists. It is called a “two-pointer” technique because it involves maintaining two pointers that traverse through a data structure to find a solution efficiently.

How the Two-Pointer Technique Works:

The basic idea behind the two-pointer technique is to have two pointers, often named slow and fast, that move through a data structure at different speeds. These pointers help identify the desired elements or subarrays that meet specific criteria. Here’s a general overview of how the technique works:

1. Initialize two pointers, slow and fast, and point them to the beginning of the data structure.
2. Move the fast pointer ahead by one step and the slow pointer by some condition-based steps. The specific condition depends on the problem you’re trying to solve.
3. Continue moving the pointers until a certain condition is met, such as the fast pointer reaching the end of the data structure or a specific relationship between the elements pointed to by the two pointers.
4. When the condition is met, you’ve typically found the answer or a subarray/substring that satisfies the problem’s requirements.
5. Process the identified elements or subarray/substring as needed to obtain the final solution.

Example: Two Sum

Let’s implement the Two Pointers technique using Swift to solve a classic problem: Given a sorted array, find a pair of numbers that sum up to a specific target value. We’ll use two pointers, one at the beginning and the other at the end of the array, to find the pair.

func findPairWithSum(array: [Int], target: Int) -> (Int, Int)? {
  // Initlise the pointers to point to the first and the last element of the array
  var left = 0
  var right = array.count - 1

  while left < right {
    let sum = array[left] + array[right]

    if sum == target {
      return (array[left], array[right])
    } else if sum < target {
      left += 1
    } else {
      right -= 1
    }
  }

  return nil
}

Now, let’s test our function with a sample sorted array and target value:

let array = [1, 2, 3, 4, 6, 8, 9]
let target = 10

if let pair = findPairWithSum(array: array, target: target) {
  print("Pair found: (\(pair.0), \(pair.1))")
} else {
  print("No pair found")
}

Output:

Pair found: (1, 9)

The function successfully found the pair (1, 9) in the sorted array, which sums up to the target value of 10.

Conclusion:

The two-pointer technique is a versatile algorithmic approach that simplifies the solution to many problems. It helps eliminate the need for nested loops or complex iterations, resulting in more efficient and elegant code. Understanding this technique will enable you to tackle a wide range of coding challenges and improve your problem-solving skills.

Furter Reading:

• Leetcode - Two-pointer questions