Array Two pointers

This blog explains the underlying algorithm behind the Array Two Pointer approach and covers a few questions from LeetCode that could be solved using the same. I hope this blog is helpful for those who are preparing for their technical rounds.

With no more delay, let us start with the topic.

Two Pointers

At times we come across questions in which:

1. We are given an array, and
2. Either we need to find a subarray,
3. Or, we need to find a pair that fulfills some condition.

In such situations, we prefer using the two pointer approach. The figure given below provides two instances where Two pointers are used:

Instances where we use the Two pointer approach

So, what exactly is the Two Pointer approach? As relevant from the examples given above, the use of 2 pointers gives the approach its name — the Two Pointer approach. In the Two Pointer approach, we use 2 pointers and move them efficiently over the array to find the desired solution.

However, there is still some mist that needs to be cleared: What does ‘efficiently’ mean? —In most cases, both the pointers travel over the array to visit every element exactly once. In other words, every element is visited twice, once by each of the pointers.

Thus, the two-pointer approach's time complexity, in most cases, turns out to be O(n).

To help us understand how the approach works, let us run through an example.

Example

Let's assume that we have an array = [1,2,3,4,5,6], and we need to find a subarray with sum = 9. Thus, we have been given the following data:

• Array = [1,2,3,4,5,6]
• Desired = 9

Let us start with the approach. We will initialize 2 pointers — ‘beg’ and ‘ed.’ ‘beg’ stands for ‘beginning’ and ‘ed’ stands for ‘end.’ As the name suggests, the ‘beg’ and ‘ed’ pointers will be used to mark the beginning and the end of the subarray respectively.

We start by placing ‘beg’ and ‘ed’ on the left of the array. As shown in the figure below, the subarray consists of just 1 element with a value = 1. Thus, the sum of the subarray is 1.

In the above figure, since the sum is less than the desired value, i.e., 9, we decide to expand the subarray. We expand the subarray because we want to increase the sum of all the elements within the subarray.

To expand, we do the following:

• Move the ‘ed’ pointer towards the right, i.e.(ed++)
• Add this new element to the sum i.e. sum += arr[ed]

After expanding, we get the following state:

In the figure above, the value of the sum is 3. Since sum < desired, we expand again.

After expanding, we get the following state:

In the figure above, the value of the sum is 6. Since sum < desired, we expand again.

After expanding, we get the following state:

In the figure above, the value of the sum is 10. Since the sum is greater than the desired value, i.e., 9, we decide to shrink the subarray. Shrinking the subarray will help us reduce the sum and increase the chances of finding the desired value.

To shrink, we do the following:

• Reduce sum by the value of the element that is being pointed by ‘beg’ i.e.
  sum -= arr[beg]
• Move the ‘beg’ pointer towards the right, i.e.(beg++)

After shrinking, we get the following state:

And at this point, we see that the sum's value is 9, which is equal to the desired value.

Thus, using the 2 pointer approach, we have successfully found the subarray that gives the desired sum of 9.

Things to consider while designing the 2 pointer approach:

The 4 design questions that one needs to think of while working on a 2 pointer approach are:

1. When to Expand/Shrink?
2. What will expansion/shrinking help us achieve?
3. How to expand/shrink?
4. Is the array in the correct order?

If we look at the example which we discussed and try to answer these questions; the solutions would be as follows:

1. When to Expand/Shrink?
   Expand when sum < desired.
   Shrink when sum > desired.
2. What will expansion/shrinking help us achieve?
   The expansion helps us increase the size of the subarray and the sum.
   Shrinking helps us decrease the size of the subarray and the sum.
3. How to expand/shrink?
   Expand by incrementing ed and then increasing the sum.
   Shrink by decreasing the sum and then incrementing beg.
4. Is the array in a proper format/order?
   If the array is in an incorrect format, then the answers to question 2 will be violated. In other words, if the array is improperly formatted, we will not be able to say with confidence that:
   i . Expansion increases the sum, and,
   ii. Shrinking decreases the sum

In our example, since we only have positive numbers, we know that

1. Expansion will make ed point to a new value that will be greater than 0. Since that value will be greater than 0, the value of sum will always increase on expansion.
2. Shrinking will remove the value from the subarray that was being pointed by beg. Since that value will be greater than 0, the value of sum will always decrease on shrinking.

This is pretty much what we need to keep in mind while solving a 2 pointer question. With this detail, let us try a few questions from LeetCode.

LeetCode Questions:

Question 1: Minimum Size Subarray Sum

Please read the question from the link given below and try to solve it on your own. Read the solution only when you are done trying.

Minimum Size Subarray Sum - LeetCode

I will not provide the solution as it is nicely explained in Approach #4 of the Solution section in the LeetCode. I will also suggest that you read the code from there as it is a well-framed code that saves you from thinking of various corner cases.

However, I will try to explain how one should think if they come across such a question.

Few things to note in the question:

1. We have been given an array, and each element of the array is a positive number.
2. We have to find a subarray of minimal length.
3. Such that the sum of the subarray is ≥ s

This means that we have to find a subarray that fulfills the condition that sum ≥ s. This is a clear indication that we should use a 2 pointer approach.

In fact, this question is pretty much similar to the example we discussed above. If we try to answer the 4 design questions that we saw above, the only difference we would see is in answer to the first question, i.e. :

1. When to Expand/Shrink?
   Expand when sum < desired.
   Shrink when sum ≥ desired. (Notice the difference)

Except that, everything else remains the same.

Side question 1: For this LeetCode question, do you think that the array is in the correct format/order?
Hint: Can you say with confidence that the sum increases on expanding and decreases on shrinking?
Ans: Yes, since all the values are positive, the sum increases on expanding and decreases on shrinking. Therefore, the array is in the correct format/order.

Side question 2: If the array had negative values, do you think that the array would have been in the correct format/order?
Ans: NO, then, the array would not have been in the correct order. We might expand the array to include a negative value that might reduce the sum. Thus, on expansion, the sum would reduce, and thus we can conclude that the array would be improperly formatted.

Question 2: K-diff Pairs in an Array

This question can be solved using approaches that are better than the 2 pointer approach. However, since we have discussed the 2 pointer approach, I will try to solve it using a 2 pointer approach. Following is the link to the question:

K-diff Pairs in an Array - LeetCode

Few things to note:

1. Given an array of integers
2. Find Unique pairs,
3. Such that the gap between the pairs is k

We see that we have been given an array, and we need to find a pair. This is another indication that we can use the 2 pointer approach.

We will think of a solution in which the first pointer will refer to the first value of the pair, and the second pointer will refer to the second value of the pair. The gap for us will be defined as: Gap = |arr[ed]-arr[beg]|

Please refer to the figure below for a better understanding:

Hypothetical Snapshot of the array and pointers during execution

Now, let us try to formulate the 4 design questions:

1. When to Expand/Shrink?
   Expand when gap < desired
   Shrink when gap ≥ desired
2. What will expansion/shrinking help us achieve?
   Expansion either increases the gap or keeps it the same.
   Shrinking either decreases the gap or keeps it the same.
3. How to expand/shrink?
   Expand by incrementing ed
   Shrink by incrementing beg
4. Is the array in a proper format/order?
   Let us imagine that while executing our algorithm, we come across a hypothetical situation like the one shown in the figure below:

Hypothetical Snapshot of the array and pointers during execution

If we come across such a situation, then on expanding, we will increment ed. This will cause ed to point to a smaller value than it was pointing before. As a result, the gap will reduce. For clarity, look at the figure below:

Gap decreases on Expansion—a violation of Design Question #2.

Or, if we shrink, beg will start pointing to a value greater than it was pointing before, and the gap will increase. For clarity, look at the figure below:

Gap increases on Shrinking — a violation of Design Question #2.

This means that the current array violates the second design question. Therefore, the format/order of the array is incorrect.

In such cases, we sort the array to bring it into the correct format.

After sorting the array in the ascending order, we can say that the array's order is correct and the answer to the second design question is not violated. This can be better understood by looking at the figure given below:

In the figure given above, we can observe that:

1. On Expansion, ed will start pointing to a value that is greater or equal to the value that it was pointing to. Thus, the gap will increase or remain the same on expansion.
2. On Shrinking, beg will start pointing to a value that is greater or equal to the value that it was pointing to. Thus, the gap will decrease or remain the same on expansion.

As of now, we have taken care of almost everything, except one: “We have not talked about handling the uniqueness of the pair.” Well, let us try to come up with an algorithm and see how we will manage that case:

Algorithm for k-diff pairs.

Let us take an example array = [1,1,1,2,3] and k = 1 and work through it to find out the solution. The figure below uses this example to explain the algorithm. In the figure, on the top left, we see the initial state of the pointers and the array. The arrows show the step of the algorithm (the figure of which is given above). These steps change the state of the array and the pointers to a new state.

Please take some time to go through the figure given below and understand the approach.

k-diff pairs 2 pointer demonstration

As we can see in the image above, the unique pairs are being handled on their own. This is happening because of step 4a of the algorithm. It checks that if the previous value pointed by beg is the same as the current value, then the valid pair for that value has already been calculated, and there is no need to calculate the pairs for it once again.

Time Complexity: Due to sorting, the overall time complexity of the algorithm is O(nlogn). However, the complexity of just the Two-pointer Approach is O(n) since both the pointers — beg and ed — traverse the array just once.

Code: Refer to this link for the code.

The code above will help in understanding the solution. However, in the above code, the right pointer (or ed) is initialized as right = left + 1. In our case, we have defined it as ed = max(ed, beg + 1). Both the solutions would work, but it will be a great exercise to analyze them further.

What I feel: If I consider an example where arr = [1,1,1,2,3,5,6] and k = 4, I find a few redundant operations that can be avoided if we use
ed = max(ed, beg + 1). However, if it is not the case, please let me know. I really appreciate any help you can provide. 😃

Conclusion

In this blog, we have tried to understand the way to approach questions related to 2 pointers. With more practice, the reader will successfully recognize a Two Pointer question and think through the 4 design questions to come up with an algorithm for solving the problem. This technique of thinking through the 4 design questions is not a standard. This is something that I follow when I am trying to solve such questions. Feel free to come up with your own way of approaching the question.