Well this is a very common topic specially in Codeforces. It's merely an algorithm rather I like to call it a technique and quite an useful one.
The CP3 ( Competitive Programming 3) states 4 variants of this technique.But before we look into those first lets take a look into an easier problem which will motivate towards the technique.
Suppose we have an array A of length upto 10^5. and we want to know if a pair of this array can make a certain value S.
Obviously we can iterate all possible pair. But that'a too timid and yield to a complexity of O(n^2).
So if we sort the array. Then take two pointer one left and right pointing to the first and last element of the array.if A[left] + A[right] > S , then we can say for sure we have to move the right pointer. because otherwise our purpose would not be served as A[left] < A[left+1]. But as
A[right]> A[right-1] , So we have to move the right pointer.
Similarly if at some point A[left] + A[ right] < S , then we have to move the left pointer. As we are seeking a larger value which can only be found if we move the left pointer.The code would look like this-
Variant - 00:
Find if there exists a pair whose sum is S.
bool two_pointer_variation_0(int sum)
{
int left=0,right=n-1;
while(left<right)
{
if(a[left]+a[right]==sum)
return 1;
else if(a[left]+a[right]>sum)
right--;
else
left++;
}
return 0;
}
#Variant-01:
Find the largest sum possible in an Array but not greater than M;
int left=0,right=0;
int sum=0;
int ans=0;
while(left<=right)
{
while(right<n && sum+a[right]<=M)
{
sum+=a[right];
right++;
}
ans= max(ans,sum);
sum-=a[left];
left++;
}
cout<< ans <<endl;
#Variant - 02: (cp3 variation 1)
Find the smallest sub array size so that the sum of sub array is greater than or equal to a certain value S;
int left=0,right=-1;
int ans=INF;
int temp_sum=0;
while(left<n)
{
right++;
temp_sum+=a[right];
if(temp_sum>=sum)
{
ans= min( ans , abs( right - left ) );
}
while(left<n && temp_sum-a[left]>=sum)
{
temp_sum-=a[left];
left++;
}
}
cout<< ans <<endl;
#Variant - 03 :
Find the largest sum possible in an array but not greater than M;
int left=0,right=0;
int sum=0;
int ans=0;
while(left<=right)
{
while(right<n && sum+a[right]<=M)
{
sum+=a[right];
right++;
}
ans= max(ans,sum);
sum-=a[left];
left++;
}
cout<< ans <<endl;
#Variant - 04 : ( cp3 variation - 03 )
find the maximum sum of a certain subarray with size k
cp3 variation 3
int left=0,right=0;
int sum=0;
int ans=0;
while(left<n)
{
while(right<n && right-left<k)
{
sum+=a[right];
right++;
}
if(right-left==k)
{
ans = max ( ans , sum );
}
sum -= a[left];
left++;
}
cout<< ans << endl;
#Variant - 05 : (cp3 variation -02 similar)
smallest sub array size so that the sub array contains at least k distinct
values;
set <int> s;
map <int, int> mp;
mp.clear();
s.clear();
int left=0,right=0;
int ans=INF;
while(left<n)
{
while(right<n && s.size()< k)
{
s.insert(a[right]);
mp[a[right]]++;
right++;
}
if(s.size()>=k)
{
ans = min( ans , abs( right - left ) );
debug( left , right )
}
if(mp[a[left]]==1)
s.erase(a[left]);
mp[a[left]]--;
left++;
}
cout<< ans << endl;
#Variant - 06 : ( cp3 variation -04 )
find the minimum element of each possible sub array with a size k
cp3 variation 4
deque<pii> window;
for(int i=0;i<n;i++)
{
while(!window.empty() && window.back().first>=a[i])
{
window.pop_back();
}
///this is to keep the array sorted
///window.front() is always the minimum element
window.push_back(MP(a[i],i));
///now use the second part to see if the front elemt is still inside the window or pop it otherwise
while(window.front().second<=i-k)
{
window.pop_front();
}
if(i+1>=k)
{
cout<< window.front().first <<endl;
}
}
References:
