Two Pointer and sliding window pattern

Two-pointer and sliding window patterns

Pattern 1: Constant window(Like window = 4 or some Integer value)

//fixed window tempate
//example: Maximum Number of Vowels in a Substring of Given Length

    public int maxVowels(String s, int k) {
        int left =0,right = 0;
        int count=0;//intial no. of wowel count
        int max = 0;//max count among all
        while(right<s.length()){
            //get all the wowel, in substring of size k-1 (window size which is fixed)
            if(right-left+1<k){
                if(isVowel(s.charAt(right++))) count++;
            }
            else{
                //update the wowel count for substring of size k

                if(isVowel(s.charAt(right))) count++;
                 //update the max wowel count
                max = Math.max(max, count);
                //remove the left index char out of the window, and it it is wowel decrement the wowel count
                if(isVowel(s.charAt(left))) count--;
                //increment both left and right //this way the window will remain consistent with size k
                left++;
                right++;
            }
        }
        return max;

    }
    public boolean isVowel(char c){
        return c=='a' || c=='e'|| c == 'i' || c == 'o' || c=='u';
    }

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.

//variable window tempate
public T variableWindowMethod(/*int arr[] or String s*/){
    int left = 0, right =0;
    int n = //arr.length() || s.length()
    T result;

    while(right<n){

        //do some operation on right pointer element in the arr

        //if or while depending on the use case
        while(/*some condition */){

            //do some operation on the stored or processed element which is present at index left

            //keep incrementing the left pointer
            left++;
        }

        //this part will be the window we are looking for i.e the valid window satisfying the condition

        //do some operation here like updating the result 

        //increment the right pointer
        right++;
    }
    return result;
}

Example: longest substring without repeating characters
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int hash[] = new int[256];// size of all the ascii characters
        Arrays.fill(hash,-1); // -1 to indicate these indexes don't have any character visited already
        int left =0,right =0;
        int max = 0;
        while(right<s.length()){
            char  c = s.charAt(right);
            if(hash[c]!=-1){// means the character has been seen in the past
                if(hash[c]>=left){// if the index of the character seen in the past is after the left pointer, then left pointer should be updated, to avoid duplicate in the window of substring
                    left  = hash[c] + 1;// has to be 1 index after the index of last seen duplicate character
                }
            }
            max = Integer.max(max, right-left+1);// keep track of mas window substring
            hash[c]  = right;// update the character last seen index in hash
            right++;
        }
        return max;
    }
}

• 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)$.
• 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

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++;
        }

    }
}

read more about various example of the above mentioned pattern(s)