Sliding Window - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

---

Applications of Sliding Window

• window of size k
  
• Shortest/longest Subarray with xxx
  
• continuous subarrays or substrings

How to Implement Sliding Window

• expand (end pointer) the window until it meets the criteria
  
• reset value when it violates
  
• shrink (start pointer) to make it smallest
  
• maintain states when expand and shrink: put in a map/set
  
• use together with queue or monotone queue

Implementation Detail

• ans += right - left + 1;

Multiple List

• LeetCode 632 - Smallest Range (shortest range in k-sorted lists)
  • PriorityQueue: track min and max during merge
    
  • sliding window: o(nlogn) - not best
• LeetCode 3 - Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {
     if (s.length()==0) return 0;
     HashMap<Character, Integer> map = new HashMap<Character, Integer>();
     int max=0;
     for (int i=0, j=0; i<s.length(); ++i){
         if (map.containsKey(s.charAt(i))){
             j = Math.max(j,map.get(s.charAt(i))+1);
         }
         map.put(s.charAt(i),i);
         max = Math.max(max,i-j+1);
     }
     return max;
 }

• Find zeroes to be flipped so that number of consecutive 1’s is maximized
  • follow up

  public int lengthOfLongestSubstringKDistinct(String str, int k) {
    if (str == null || str.isEmpty() || k == 0) {
        return 0;
    }
    TreeMap<Integer, Character> lastOccurrence = new TreeMap<>();
    Map<Character, Integer> inWindow = new HashMap<>();
    int j = 0;
    int max = 1;
    for (int i = 0; i < str.length(); i++) {
        char in = str.charAt(i);
        while (inWindow.size() == k && !inWindow.containsKey(in)) {
            int first = lastOccurrence.firstKey();
            char out = lastOccurrence.get(first);
            inWindow.remove(out);
            lastOccurrence.remove(first);
            j = first + 1;
        }
        //update or add in's position in both maps
        if (inWindow.containsKey(in)) {
            lastOccurrence.remove(inWindow.get(in));
        }
        inWindow.put(in, i);
        lastOccurrence.put(i, in);
        max = Math.max(max, i - j + 1);
    }
    return max;
  }

• LeetCode 340 - Longest Substring with At Most K Distinct Characters
  
• Sum of minimum and maximum elements of all subarrays of size k
  • remove numbers out of range k
    
  • remove numbers in k range as they are useless
• LeetCode 67 - Minimum Window Substring
  • expand (end pointer) the window until it meets the criteria
    
  • shrink (start pointer) to make it smallest
• LeetCode 424 - Longest Repeating Character Replacement
  
• LeetCode 1004 - Max Consecutive Ones III
  
• LeetCode 904 - Fruit Into Baskets
  • Map stores value to count
    
  • Map store last index of value
• LeetCode 438 - Find All Anagrams in a String

public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> map = counter(p);
    int match = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) == 0) {
                match++;
            }
        }
        if (i >= p.length()) {
            c = s.charAt(i - p.length());
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
                if (map.get(c) == 1) {
                    match--;
                }
            }
        }
        if (match == map.size()) {
            result.add(i - p.length() + 1);
        }
    }
    return result;
}

Window class

• LeetCode 992 - Subarrays with K Different Integers
  • Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
    
  • exactly -> at most
    
  • sliding window, two pointers
    
  • window class, maintain 2 sliding windows with same end element

  public int subarraysWithKDistinct(int[] A, int K) {
  Window window1 = new Window();
  Window window2 = new Window();
  int ans = 0, left1 = 0, left2 = 0;
  for (int right = 0; right < A.length; ++right) {
    int x = A[right];
    window1.add(x);
    window2.add(x);
    while (window1.different() > K)
      window1.remove(A[left1++]);
    while (window2.different() >= K)
      window2.remove(A[left2++]);
    ans += left2 - left1;
  }
  return ans;
  }

  Jumping Window + Fixed Size

• LeetCode 683 - K Empty Slots
  • sliding window: find a match when i reaches end of current window
    
  • [O(kn) brute force]
    
  • TreeSet: lower/higher
    
  • Bucket

  public int kEmptySlots(int[] flowers, int k) {
    int[] days = new int[flowers.length];
    for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
    int left = 0, right = k + 1, result = Integer.MAX_VALUE;
    for (int i = 0; right < days.length; i++) {
        if (days[i] < days[left] || days[i] <= days[right]) {
            if (i == right)
                result = Math.min(result, Math.max(days[left], days[right]));
            left = i;
            right = k + 1 + i;
        }
    }
    return (result == Integer.MAX_VALUE) ? -1 : result;
  }