DSA - Two Pointers Technique

What is the Two Pointers Technique?

The two pointers technique helps track indices in a collection of elements to access objects in memory by index with O(1) space. This technique is very handy when you need to optimize the time and space of a solution.

What Problems Does It Solve?

The two pointers technique solves problems involving collections. For example, it is useful when you need to compare each element to other elements in that collection.

What Are the Ways to Use It?

The first way to use the two pointers technique is to set the `left` pointer at the beginning of the array and the `right` pointer at the end, then `increment` the `left` and `decrement` the `right` pointer until they meet.

while l < r {
    l += 1
    r -= 1
}

The second way is to use `slow` and `fast` pointers for cycle detection in a LinkedList. It is called `fast` and `slow` because the `fast` pointer moves `twice` as fast as the `slow` pointer.

class Node {
    var val: Int 
    var next: Node?

    init(val: Int, next: Node? = nil) {
        self.val = val
        self.next = next
    }
}

func hasCycle(_ head: Node?) -> Bool {
    var fast = head
    var slow = head
    while fast != nil && fast?.next != nil {
        fast = fast?.next?.next
        slow = slow?.next
        if fast == slow {
            return true
        }
    }
    return false
}

Problem

As an example, let's look at the Two Sum II - Input Array Is Sorted.

Given a 1-indexed array of integers `numbers` that is already sorted in non-decreasing order, find two numbers such that they add up to a specific `target` number. Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`.

Return the indices of the two numbers, `index1` and `index2`, added by one, as an integer array `[index1, index2]` of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Solution

Let's look at the solution to the Two Sum II - Input Array Is Sorted that uses the two pointers technique, where the `left` pointer is initialized with the first index in the array and the `right` pointer is initialized with the last index.

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var l: Int = 0
        var r: Int = numbers.count - 1
        while l < r {
            if numbers[l] + numbers[r] < target {
                l += 1
            } else if numbers[l] + numbers[r] > target {
                r -= 1
            } else {
                return [l+1,r+1]
            }
        }
        return []
    }
}