Sliding Window Explained

Preface

After a couple of years of my crusades on various FAANG and near FAANG companies (though this terminology makes less and less sense), endless interview loops (sometimes at night), I've gathered a fine database of knowledge that I'd like to give back to the dev community.

Though an interview process is something I'm tired of reading about, it's still part of the game, so sorting things through for future reference is another justification to write all of this for me.

So not going into details about interview process (about it and offers received later). I'll try to publish various kinds of coding problems I encountered during my interview ride.

Sliding window

Introduction

Here we go, probably the most popular and boring one, but still quite tricky!

The sliding window algorithm is generally used on problems that look for max, min, or any other target value in a contiguous sequence within an array. It is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

How to identify?

• The problem will involve a data structure that is ordered and iterable like an array or a string.
• You are looking for some subrange in that array/string, like a longest, shortest or target value.
• There is an apparent naive or brute force solution that runs in O(N), O(2^N) or some other large time complexity.

But the biggest matter you are looking for is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

Characteristics of the problems that can be solved by two pointers. The summary is simple:

1. If a wider scope of the sliding window is valid, the narrower scope of that wider scope is validmush hold.
2. If a narrower scope of the sliding window is invalid, the wider scope of that narrower scope is invalidmush hold.

Approaches

The window represents the current section of the string/array that you are looking at and usually there is some information stored along with it in the form of constants. At the very least it will have 2 pointers, one indicating the index corresponding beginning of the window, and one indicating the end of the window.

Basic pattern:

The basic pattern which is used for questions with single array/string input, where dynamic frequency map can be calculated on the fly.

Example problem:

Fruits into baskets

1. Create frequency map of fruit types.
2. Increment character/number frequency with end pointer. In this case we increase number of fruits of particular type.
3. Check a condition. Here if no more than two baskets has been filled.
4. Remove element with start pointer if it's frequency is 0. Yep we can remove empty basket out of the map.
5. Calculate length or target value. Obviously number of trees here.

public static int findLength(char[] arr) {  if (arr.length == 0) return 0;    Map<Character, Integer> map = new HashMap<>();  int start = 0, end = 0, len = 0;  while (end < arr.length) {      // adding fruit in here      map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);      end++;      while (map.size() > 2) {          // removing fruit from basket          map.put(arr[start], map.getOrDefault(arr[start], 0) - 1);          if (map.get(arr[start]) == 0) {              map.remove(arr[start]);          }          start++;      }      // max number of trees consumed      len = Math.max(len, end - start);  }  return len;    }

The frequency map pattern is used mostly when you have 2 inputs, for instance, string and array of patterns. Example:

Permutation in a String

In this case frequency map need to be build upfront.
Here steps written in a more general way, so you'd be able to apply them to any problem.

1. Create frequency map.
2. Calculate conditional input frequency.
3. Initialise target count.
4. Decrement character/number frequency with end pointer.
5. Check the count of remaining distinct values in frequency map.
6. Check your condition.
7. Increment character/number frequency with start pointer.
8. If value at start pointer is equal to 1 in frequency map increment counter.

With frequency map:

boolean findPermutation(String str, String pattern) {    if (str == null || pattern == null) return false;    Map<Character, Integer> map = new HashMap<>();    for (char c : pattern.toCharArray()) {        map.put(c, map.getOrDefault(c, 0) + 1);    }    int start = 0, end = 0, count = map.size();    while (end < str.length()) {        char endChar = str.charAt(end++);        if (map.containsKey(endChar) && count >= 0) {            map.put(endChar, map.get(endChar) - 1);            if (map.get(endChar) == 0) {                count--;            }        }        while (count == 0) {            if (end - start == pattern.length()) {                return true;            }            char startChar = str.charAt(start++);            if (map.containsKey(startChar)) {                map.put(startChar, map.get(startChar) + 1);                if (map.get(startChar) == 1) {                    count++;                }            }        }    }    return false;}

Number of subarrays with K Distinct Characters:

Haven't found same problem on leetcode. But it's easy to realise from the title: you're given an array and the goal is to find number of subarrays with K (given number) of distinct characters.

Input: s = "[1,2,1,2,3]", k = 2
Output: 7
Explanation: [[1,2], [1,2,1], [1,2,1,2], [2,1], [2,1,2],[1,2] , [2,3], [2,3]]

This one is much tricked and requires you to apply few small tricks.

1. The trick is atMostK(A, K) - atMostK(A, K - 1) . So we can say that number of subarrays with K distinct is number of subarrays with AT MOST K distinct - number of subarrays with AT MOST K - 1 distinct.Because in sliding window we explore all windows up to k.
2. count += end - start gives us all subarrays in the window. Because every time when we add a number we add window_size subarrays.[1,2,3] [1] | [1,2] [2] | [1,2,3] [2,3] [3] - window_size subarrays every time.

 public int subarraysWithKDistinct(int[] A, int K) {        **return atMostK(A, K) - atMostK(A, K - 1);**    }    int atMostK(int[] arr, int k) {        if (k == 0) return 0;        Map<Integer, Integer> map = new HashMap<>();        int start = 0, end = 0, count = 0;        while (end < arr.length) {            map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);            end++;            while (map.size() > k) {                map.put(arr[start], map.getOrDefault(arr[start], 0) - 1);                if (map.get(arr[start]) == 0) {                    map.remove(arr[start]);                }                start++;            }            count += end - start; // trick here : we can add all subarrays between end and start        }        return count;    }

Complexities

In most of the time they sliding window problems can be solved in O(N) time and O(1) space complexity.

For basic approach without additional input : O(N) time and O(1) space.

For frequency map approach: O(N) or O(N + M) time and O(M) space where M is amount of additional input data.