Two Pointer Algorithm

Two Pointer algorithm are typically used for searching pair elements in the sorted array. The two Pointer algorithm is an efficient method to search pairs in sorted array. Because Time Complexity of searching pair elements in array using Naive approach(To process one element per loop) depends on their size. But, Two pointer algorithm is able to process two elements per loop.

How to use

1. Each pointer starts at the beginning index and end index of the data structure.
2. Iterate until the met condition or both pointers are met.

Two-Pointer Algorithm

To learn with problem

I’ll solve the problem “Two Sum II — Input Array Is Sorted” in Leetcode for learning this algorithm. To explain this problem simplify, We have to find the pair which can be the target number when they are added up. The array is also already sorted. (ascending-order)

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Let’s create two pointers as follow the code.

class Solution {
    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var pointer_1 = 0
        var pointer_2 = numbers.lastIndex
    }
}

We need to create loop that can iterate until met condition or both pointers are met.

class Solution {
    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var pointer_1 = 0
        var pointer_2 = numbers.lastIndex

        while (pointer_1 < pointer_2) {
            // TODO (Finding fairs which meets condition)
        }
        // not found
        return intArrayOf(-1, -1)
    }
}

We need to find pairs that can satisfy the conditions, so we need to write logic to move the pointer based on each condition. The logic follows as direction.

1. If the sum is smaller than the target number, then pointer_1 moves forward.
2. If the sum is bigger than the target number, then pointer_2 moves9 backward.
3. If the sum is equal to the target number, then return intArray that consists of pointer_1 and pointer_2.

The above direction basically describe how to work this algorithm. Now, We can write the code follow the direction.

class Solution {
    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var pointer_1 = 0
        var pointer_2 = numbers.lastIndex

        while (pointer_1 < pointer_2) {
            val sum = numbers[pointer_1] + numbers[pointer_2]

            when {
                sum == target -> return intArrayOf(pointer_1 + 1, pointer_2 + 1)
                sum < target -> pointer_1++
                sum > target -> pointer_2--
            }
        }
        return intArrayOf(-1, -1)
    }
}

Finally, We solved this problem! Let’s calculate Time complexity and Space Complexity.

Calculate Time Complexity and Space Complexity

The Big-O Time Complexity is O(N) because we need to find all elements in worst case. In this situation, pointer_1 always stops starting points and pointer_2 moves until meets pointer_1.

The Big-O Space Complexity is O(1) because we don’t need any data structure which can store elements. We just use two pointers that indicate the address of memory.