Clever Geek Handbook

Two Pointer Algorithm

I am trying to understand two approaches of the pointer algorithm, so I was reading this article

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

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

  • We introduce two pointers l

    , r

    denoting the startIndex and endIndex of our adjacent subarray, both of which are at the top of the array.
  • Now we start to expand our right pointer r

    , provided sum[l,r] <= M

    Once we reach that stage, we have no choice, but to move the left pointer and start decreasing the amount to, we come to a situation where we can expand our right pointer again.
  • As and when we reach the point where we need to move the left pointer, we keep updating our maximum amount that we have reached so far.

And here is 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 do not consider all possible contiguous subsequences. Once the amount is exceeded, we will account for our current subsequence length, compare it to see if it is larger than the previous one, and just increase l

and repeat the process.

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

+3


source to share


2 answers


The approach works because, for each pointer, the r

current is l

actually the farthest to the left, so the sum is still below the threshold.

Therefore, there is no need to consider all other sequences that end with a pointer r

.



However, the approach is invalid if negative numbers are allowed. In this case, the longer the sequence l

- r

does not necessarily mean that the amount will increase.

+4


source


The algorithm works. All values ​​in the array are assumed to be positive (or 0), so for a fixed l, the best contiguous sequence starting with l can be found with a while loop, by adding positive or zero elements up to the last r until your current sum of M.

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



If integers can be negative, you are correct that it doesn't work.

+2


source






More articles:


All Articles