Identifying two pointer reduction

Some problems may not fit the template for the direct application of the two-pointer pattern, but we may be able to reduce them to problems that fit the template and can be solved by directly applying the two-pointer technique. These are generally medium or hard problems as the reduction may not always be obvious, and we need to make sure the solution to the reduced problem is also the solution to the original problem.

We need to make some critical observations to determine whether the reduction is possible; asking yourself the following questions will help you determine whether a problem can be reduced to another problem solvable by directly applying a two-pointer pattern.

Example

To better understand the two-pointer reduction pattern, let's consider an example problem and see how we can reduce it to the two-pointer pattern.

Problem statement: We are given an array `arr` of integers and an integer value `target`. Find and return two elements in the array whose sum equals `target`, if they exist.

Consider the given array and target sum 13; two pairs exist in the array with the given sum.

Brute force solution

The brute-force solution to this problem is to use nested loops to pick every item in the array and check its sum with all the other items. If the sum of any two items equals the target, we return them. Otherwise, we return an empty array.

The implementation of the brute force solution is given as follows.

Though the solution is correct, it requires nested loops, which have a runtime complexity of O(N^2) in any case, which is not very efficient. Let's now see if this problem can be reduced to a two-pointer.

Two pointer reduction solution

Let's ask ourselves the questions we listed above to identify if we can reduce this problem to the two-pointer pattern problem. 

The critical observation here is that the order of items in the array does not matter, and sorting the array establishes some special relationship between items when traversed from both ends. Exploring further the answers to the above questions, we can reduce the problem to a two-pointer pattern problem as follows.

We sort the array and then iterate from both ends using left and right and calculate the sum = arr[left] + arr[right] at each step. If the sum is less than target, all values before right will only decrease the sum further due to the array's sorted order, so we can increase left to increase sum. Similarly, if the sum is greater than target, all values after left will only increase the sum further, so we decrease right to decrease sum. At any point, if sum equals target, we return the values. We will prove the correctness of this solution later in the lesson.

The sorted order of the array allows us to discard values whose sum with other values in the array will always be either greater or less than the target. This reduces the problem to a problem solvable by direct application of the two-pointer pattern. We traverse from both ends, operate on the data items, and close the gap between left and right in each iteration. Let's look at an example to understand this better.

The implementation of the two-pointer solution is given below.

The process above summarizes how we can identify a problem that can be reduced to a generic two-pointer pattern problem and solve it using the implementation we learned earlier.

Proof of correctness

The two pointer solution works by discarding one item in each iteration that can never be paired with any other item in the array to make the sum equal to target. We start with left = 0 and right = n -1 where n is the size of the array.

Consider that the sum = arr[left] + arr[right] is less than target in the first iteration. Since arr[right] is the maximum item in the array, we can be sure that no other item can be added to arr[left] to get a greater sum. This means all pairs in the array containing arr[left] are smaller than target. Another way to look at it is that we paired all items in the array with arr[left] and found the sum to be less than target.

We discard the items at arr[left] by incrementing left.

Now consider the sum = arr[left] + arr[right] is greater than target the remaining array. This would mean all pairs in the remaining array with arr[right] in it have a sum greater than target as arr[left] is the minimum of all remaining items.

However, in this iteration, we only considered the pairs of arr[right] with the remaining items in the array and not the discarded item arr[0]. This is sufficient because we already considered all pairs of the previously discarded items, including the ones with arr[right], before discarding them.

This means that considering all pairs in the remaining array that has arr[right] in it is sufficient to decide if arr[right] should be discarded or not. Since sum = arr[left] + arr[right] is greater than sum, we can discard by decreasing right.

As evident from the explanation above, we discard an item from the array only after considering its pairs with all other items in the array and validating that none of the pairs have sum equals target. This invariant is maintained throughout the iterations until we reach left and right such that sum = arr[left] + arr[right] equals target or all items are discarded if no solution exists.

Example problems

Most problems that fall under this category are medium or hard problems as reduction is not always obvious, and proving that the solution of the reduced problem is also the solution of the original problem can be difficult. Below is a list of problems that fall under the two-pointer reduction pattern.

• Two sum
• Target limited two sum
• Duplicate aware two sum
• Largest container

We will now solve these problems to get a better understanding of the two-pointer reduction pattern.