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 example: sum

• Approaches:
  • Brute Force: Generate all possible subarrays and choose the max length subarray with sum
• 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 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
  • Find subarray where sum

Pattern 4: Find the shortest/minimum window

Different approaches for pattern 2:
Example: Largest subarray with sum

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) 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 k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



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 ( 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 (


        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum