The two pointer algorithm

Question

I'm trying to understand the two pointer algorithm approach, so I've been reading this article

So here is the question. Suppose we have an array of N elements. And we want to find the largest contiguous sequence of elements in that array where the sum is less than or equal to M. We have to return the value that the sequence of elements sums up to.

So suppose we have an array of elements [2, 1, 3, 4, 5] and our M is 12. We would return 12 because 3, 4, and 5 sum up to 12. Here was the approach from the article

We introduce two pointers l, r denoting startIndex and endIndex of our contiguous subarray, with both of them at the tip of the array.
We now start extending our right pointer r provided sum[l,r] <= M Once, we reach at such a stage, we don't have any option but to move the left pointer as well and start decreasing the sum until we arrive at the situation where we can extend our right pointer again.
As and when we reach the point, where we need to shift the left pointer, we keep updating our maximum sum we have achieved so far.

And here was the C++ code.

#include <bits/stdc++.h>
#define lli long long
#define MAX 1000005

using namespace std;

lli A[MAX];

int main()
{
    int n;
    lli sum = 0;     
    cin >> n;

    for ( int i = 0; i < n; i++ ) cin >> A[i];

    int l = 0, r = 0;
    lli ans = 0;

    while ( l < n ) {
       while ( r < n && sum + A[r] <= M ) {
           sum += A[r];
           r++;
       }
       ans = max(ans, sum);
       sum -= A[l];
       l++;
    }

    cout << ans << endl;
    return 0;
}

But I don't understand why this approach works. We are not considering all possible contiguous sub sequences. As soon as the sum is exceeded, we take note of our current sub sequence length, compare it to see if it's larger than the previous one, and simply increment l and repeat the process.

I don't see how this yields the correct result.

You are forgetting that not only l is incremented, but also the value of the previous `L`-th element is being substraced from the sum. The sum then contains all remaining elements between new `L` and `R`, there is no need to recompute this sum (restarting the loop with `R = L`). I also think (did not read the article) that there is an implicit requirement of the elements being >= 0, so that the sum can only grow. — antipattern, Apr 06 '17 at 10:08

danbanica · Accepted Answer · 2017-04-06T18:33:54.923

The approach works because for each r pointer, the current l actually represents the furthest one to the left such that the sum is still below the threshold.

Therefore it is not necessary to look into all other sequences that end at the r pointer.

However, the approach is not valid if negative numbers would be allowed. In that case, a longer l - r sequence would not necessarily mean that the sum would increase.

score 2 · Answer 2 · answered Apr 06 '17 at 10:11

The algorithm works. It assumes all values in the array are positive (or 0), so for a fixed l, the best contiguous sequence starting at l can be found by the while loop, by adding positive or zero elements until the last r before your current sum reaches M.

By then you know that sequences starting at l and stopping before r are smaller than the current one, and that the ones stopping after r are just too big (>M). So you just compare the current sum to the previous best, and you move on to next value for l.

If the integers can be negative, you're right that this does not work.

The two pointer algorithm

2 Answers2

Linked