Two-pointer and sliding window patterns
Pattern 1: Constant window(Like window = 4 or some Integer value)
For example given an array of (-ve and +ve) integers find the max sum for the contiguous window of size k.
Pattern 2:(Variable window size) Largest subarray/substring with <condition> example: sum <=k.
- Approaches:
- Brute Force:
Generate all possible subarrays and choose the max length subarray
with
sum <=k(this will have time complexity of $O(n^2)$.
- Brute Force:
Generate all possible subarrays and choose the max length subarray
with
- Betten/Optimal:
Make use of two pointer and sliding window to reduce the time complexity to
O(n)
Pattern 3: No of subarray/substring where <condition> like sum=k.
This is very difficult to solve because it becomes difficult when to expand (right++) or when to shrink(left++).
This problem can be solved using Pattern 2
For solving problems like finding the number of substrings where sum =k.
-
This can be broken down to
- Find subarrays where
sum<=k----X - Find subarray where sum<=k-1----Y
then the result will be
X-Y= answer
- Find subarrays where
Pattern 4: Find the shortest/minimum window <condition>
Different approaches for pattern 2:
Example: Largest subarray with sum<=k
public class Sample{
public static void main(String args[]){
n = 10;
int arr[] = new int[n];
//Brute force approach for finding the longest subarray with sum <=k
//tc : O(n^2)
int maxlen=0;
for(int i =0;i<arr.length;i++){
int sum =0;
for(int j = i+1;j<arr.length;j++){
sum+=arr[j];
if(sum<=k){
maxLen = Integer.max(maxLen, j-i+1);
}
else if(sum > k) break; /// optimization if the sum is greater than the k, what is the point in going forward?
}
}
Better approach using the two pointers and the sliding window
//O(n+n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
int left = 0;
int right =0;
int sum = 0;
int maxLen = 0;
while(right<arr.length){
sum+=arr[right];
while(sum > k){
sum = sum-arr[left];
left++;
}
if(sum <=k){
maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
// left and right in a different variable
}
right++;
}
Optimal approach:
We know that if we find the subarray we store its length in maxLen, but while adding arr[right] if the sum becomes more than the k then currently we are shrinking left by doing sum = sum-arr[left] and doing left++.
We know that the current Max length is maxLen, if we keep on shrinking the left index we might get another subarray satisfying the condition (<=k) but the length might be less than the current maxLen then we will not update the maxLen till we find another subarray satisfying the condition and also having len > maxLen, then only maxLen will be updated.
An optimal approach will be to only shrink the left as long as the subarray length is more than the maxLen when the subarray is not satisfying the condition (<=k)int left = 0.
int right =0;
int sum = 0;
int maxLen = 0;
while(right<arr.length){
sum+=arr[right];
if(sum > k){// this will ensure that the left is incremented one by one (not till the sum<=k because this might reduce the length i.e right-left+1 which will not be taken into consideration)
sum = sum-arr[left];
left++;
}
if(sum <=k){
maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
// left and right in a different variable
}
right++;
}
}
}
Top comments (0)