Two Pointer Pattern — Swift

Two pointers is an easy and effective technique used for searching pairs in collections such as arrays or even on string.

This technique is used for solving problems with minimal space complexity.

Common patterns in the two-pointer approach are:

1. First pointer starting at the beginning and the other at the end until they both meet.
2. One pointer moving at a slow pace, while the other pointer moves at twice the speed.

Now let’s see how the first two-pointer technique works. We take two pointers, one representing the index of first element and other representing the index of last element of the array, and then we add the values at both the pointers. If their sum is smaller than the required sum X then we shift the left pointer to right by 1. If their sum is greater than the required sum X then we shift the right pointer to left by 1 to get closer to the sum. We keep moving the pointers until we get the sum as X.

Space Complexity — O(1) Time Complexity — O(n)

Let’s see the first two pointer technique in practice with two examples.

Example 1

Create a function that takes a sorted array as input and returns pairs of numbers whose sums equals a given sum.

func sumPairs(_ nums: [Int], matching sum: Int) -> [[Int]] {
    if nums.isEmpty {
        // If the input array is empty there is no pair to return
        return []
    }
    var leftIndex = 0 // Starting index of input array
    var rightIndex = nums.count - 1 // Last index of input array
    var pairs = [[Int]]() // Array to return matching pairs
    while leftIndex < rightIndex {
        let leftIndexValue = nums[leftIndex]
        let rightIndexValue = nums[rightIndex]
        if leftIndexValue + rightIndexValue == sum {
            pairs.append([leftIndexValue, rightIndexValue])
            leftIndex += 1
            rightIndex -= 1
        }
        else if leftIndexValue + rightIndexValue < sum {
            // Shift the left index to right by 1
            leftIndex += 1
        }
        else {
            // Shift the right index to left by 1
            rightIndex -= 1
        }
    }
    return pairs
}

Calling the above function sumPairs([-3,-2,-1,0,1,2,3], matching: 0) should return three pairs of integers [[-3,3], [-2,2], [-1,1]]

Example 2

Create a function that takes a sorted array as input and returns count of unique values in input.

func countUniqueValues(_ values: inout [Int]) -> Int {
    if values.isEmpty {
        // If the input array is empty there are no unique values
        return 0
    }
    var index1 = 0
    for index2 in 1..<values.count {
        if values[index1] != values[index2] {
            index1 += 1
            values[index1] = values[index2]
        }
    }
    
    return index1 + 1
}

Let’s now see the second two pointer technique in action.

Example 1

Detecting cycle in a linked list — The idea here will be to use a slow and fast pointer. Fast pointer will move twice as quickly as slow pointer and cycle will be detected if at some point both slow and fast pointer point to same node.

func detectCycle<Element>(_ head: Node<Element>) -> Bool {
    var slowNode: Node<Element>? = head
    var fastNode = head.next
    while slowNode?.next != nil && fastNode?.next != nil {
        if slowNode === fastNode! {
            return true
        }
        slowNode = slowNode?.next
        fastNode = fastNode?.next?.next
    }
    return false
}