Sliding Window

In this article, I will outline the various tricks that can be employed when looking at a sliding window problem.

Think of a sliding window as an imaginary ruler along a number line which slides across the number line to fit in some numbers and remove certain other numbers as we move ahead.

The advantage of employing a sliding window as a tool in solving algorithmic problems is that it might simplify an existing solution and improve the time complexity of the solution.

Pattern 1: When the size of the sliding window is fixed

Some leetcode problems fall in this pattern whereby the size of the sliding window is fixed and the window moves along the length of the array. The problems are :

• https://leetcode.com/problems/diet-plan-performance/
• https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters
• https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together

The sample template which would be useful to solve the above three problems are :

windowSize - a variable that defines the size of the window
arr - array consisting the list of numbers
Element - represent the element of the array - it might be an integer, string, character (based on the array type)
for(int i = 0; i < arr.length; i++) {
  Element element = arr[i];
  if( i > windowSize - 1) { 
    // perform a series of actions as required by the problem.
    // remove the first element of the window which has been visited 
    // so that we could move ahead in the array without affecting      
    // the window size
  }
}

Problem 1 : https://leetcode.com/problems/diet-plan-performance/

public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        if(k > calories.length)
            return 0;
        int points = 0, sumCal = 0;
        for(int j = 0; j < calories.length; j++) {
            sumCal += calories[j];
            if(j >= k-1) {
                if(j > k-1) {
                    sumCal -= calories[j - k];
                }
                points += sumCal < lower ? -1 : 
                          ((sumCal > upper) ? 1 : 0);    
            }
        }
        return points;
    }

As we can see, we have followed the template to sum up the calories as we go and add in points based on the window size. The window size remains constant as we go further in the array.

Problem 2 : https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters

public int numKLenSubstrNoRepeats(String S, int K) {
        int count = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
            if(i >= K-1) {
                if(i > K-1) {
                    char chNew = S.charAt(i-K);
                    map.put(chNew, map.get(chNew) - 1);
                    if(map.get(chNew) == 0)
                        map.remove(chNew);
                    if(map.size() == K)
                        count++;
                }
                else if(map.size() == K)
                    count++;
            }
        }
        return count;
    }

For this problem, the basic template remains the same, but we have looped in another data structure (hashMap) to help us solve the problem.

Problem 3 : https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together

public int minSwaps(int[] data) {
        if(data.length <= 2)
            return 0;
        int numOnes = 0;
        for(int i = 0; i < data.length; i++) {
            numOnes += data[i];
        }
        int maxOnes = 0, tempOnes = 0;
        for(int i = 0; i < data.length; i++) {
            tempOnes += data[i];
            if(i >= numOnes - 1) {
                if(i > numOnes - 1) 
                    tempOnes -= data[i - numOnes];
                maxOnes = Math.max(maxOnes, tempOnes);
            }
        }
        return numOnes - maxOnes;
 }

Again, this follows the same template as well. Except, for this problem, we do an initial pre-processing to evaluate the total number of 1’s in the current array.