Skip to content

#4 Two Pointer technique

This pattern is commonly used to solve array problems very efficiently. Whenever an array question deals with finding two numbers in an array that satisfy a certain condition, either directly or indirectly, a two-pointer should be the first strategy that comes to mind.

Consider the classic two-sum problem, which asks you to find which of two elements in an array adds to another number. although there may be many solutions, it only asks for one. Let’s say we have an array [13,9,4,7,8].

Brute force solution would be to use bubble sort to find the occurrence which would need O(n^2). With a two-pointer, we could bring the time complexity to O(n).

The above problem doesn’t require sorting but let’s try this out with sorting and pointer at the same time.

So once the array is sorted it would look like this [4,7,8,9,13].

Now we place one pointer at the start and the other at the end, because the array is sorted, this corresponds to the smallest and largest numbers, respectively. With each step, we calculate the sum of the 2 numbers being pointed.

If the sum is less than the target, we want to increase the left pointer by 1 position because moving right would further reduce the sum. instead, if the sum is greater than the target then we would move the right pointer to left. Once, the solution is found we could break from the loop.

Two pointer is not limited to putting pointers at both the end

  • two pointers begin on the same side.
  • two pointers begin on opposite sides.
  • two pointers are separated by a fixed distance b/w them.
  • one pointer moves at a different pace than the other.

Let’s look at a similar but more complex problem. consider the following arrangement of vertical sticks, whose lengths are written below them you need to find the two sticks which contain max water b/w them

If we would think a bit we could make this out as an array with the following values [1,8,9,4,11,15,3,5] where the position of the stick is index and height is the value.

The distance b/w each stick is one unit, what is the maximum amount of water one could hold b/w two sticks. so you need to calculate the area.

Note: we shouldn’t think about sorting the sticks as distance is affected.

Let’s place 2 pointers at both ends and check the area store it as a variable. Now how do we move, we are trying to find the max area so it would be wise to move from the left as out of the 2 pointers left has the smallest value. so our strategy would be to move away from smaller sizes to reach the solution.

Sample Problems to test this out:

  • Identify palindromes within strings. For example, ‘abcdedc’ has the palindrome ‘cdedc’.
  • Find three numbers in an array that sum to zero. For instance, the solution for [-3, 2, 1, 7, 9] would be -3, 2, and 1.
  • Remove duplicates from an array. Convert [1, 1, 1, 4, 4, 5, 5, 5] into [1, 4, 5].
  • Merge two sorted lists. Convert [1, 3, 4, 6] and [2, 4, 7, 7] into [1, 2, 3, 4, 6, 7, 7].

Linked List -two pointer template:

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

This is a reproduction work from the article

Medium

Leetcode

Published inData Structures

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *