Understanding the two pointer pattern

To perform any operation on the data items of an array, we either need to know their index in advance or traverse the array using loops. An array is generally only traversed in one direction at a time, either from the start to the end or the other way around, depending on the problem we are trying to solve. However, some problems require traversing the array in both directions simultaneously, and we often resort to nested loops for such cases, which are inefficient.

For some of these problems, we can use the two-pointer traversal technique to traverse an array simultaneously from both ends. This enables us to solve such problems in linear time and a single pass, which would otherwise require inefficient nested loops.

In this course, we will learn more about the two-pointer technique and how to identify a problem as a two-pointer pattern problem.

Two-pointer technique

The two-pointer technique uses two variables, left and right initialized with 0 and n-1, respectively, where n is the size of the array. These two variables serve as indices (pointers) that traverse the array simultaneously from both ends until they meet in the middle. As we traverse the array, we apply the operations to the data items at those indices to solve the problem. At the end of each iteration, we increase and/or decrease left and right by some steps dictated by the problem to close the gap between them.

Algorithm

The algorithm given below outlines the generic two-pointer traversal technique.

• Step 1: Initialize two variables `left` and `right` to values dictated by the problem such that `left` < `right`
• Step 2: Loop while `left` < `right` and do the following
  • Step 2.1: Do some operations using `arr[left]` and `arr[right]` as dictated by the problem
  • Step 2.2: Increment `left` by some steps if it should be increased
  • Step 2.3: Decrement `right` by some steps if it should be decreased

Implementation

Given below is the generic code implementation of the two-pointer technique on an array arr of size n using variables left and right as index variables (pointers).

The generic implementation uses helper functions incrementLeft, decrementRight, leftStep, and rightStep, but in most cases, these have a very simple implementation and can be implemented inline where they are used.

Complexity Analysis

The algorithm's time and space complexity is easy to understand. The two pointers simultaneously traverse the array from both ends and meet in the middle, effectively performing a full array traversal. So, the time complexity is linear O(N) in any case where N is the size of the array.

Since we do not create any new data structure, the space complexity in any case is constant O(1). 

Best Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Applications

Many array problems may be classified as two-pointer pattern problems, but how to apply the two-pointer technique to solve them may not be obvious. A problem may be solved by directly applying the two-pointer technique or reducing it to an equivalent two-pointer pattern problem. Sometimes, the problem may comprise one or more subproblems that can be solved using the two-pointer technique. We further classify the two-pointer pattern problems as follows

1. Direct application
2. Reduction
3. Subproblems

Later in the course, we will examine techniques for identifying all categories of the two-pointer pattern problems.