Sliding Window II

This article is continuation of the previous article about sliding windows I which talks about fixed length sliding window. In this aritcle will look for problems which can be solved using variable length sliding window. Variable length sliding window problems are more tricky to detect. Sometimes a problem will mention a window which makes it easier, but sometimes that conclusion needs to be done by analyzing and running examples in the problem. There are quadratic number O(N^2) of variable length windows in an array i.e. if two end points are choosen out of N numbers, N choose 2 which would be N(N-1)/2 which would be O(N^2) in number. Iterating over each sub problem will give another O(N) complexity. So usually brute force algorithms of variable length sliding windows are usually O(N^3) complexity. The O(N^3) complexity can be easily brought down by a factor O(N) by accumulating the result as the window size is increased from [i..j] to [i..j+1], but there are still O(N^2) such windows so such algorithms will still be O(N^2).

In some problems where there is an invariant (example sum less than k) which needs to be true over the sub-array, in such problems an increment of the right side of the window may make invariant as false, which needs to be again made true by moving the left side of the window. So with two pointer approach only windows where the invarint is true are considered, decreasing the problem runtime to O(N) in such problems.

Problem:

Given a list of positive numbers, find number of sub-arrays with sum equal to k.

Example: [1, 4, 1, 3, 5, 1, 3, 2], k = 5

result: 4  
subarrays: [1, 4], [4, 1], [5], [3, 2]

General Template:

def countSubArrayWithSumk(nums: List[int], k: int) -> int:
    # Intialize
    count = 0
    n, s = len(nums), 0
    left = 0 # Left pointer to the window
    # Iterate over each window, by incrementing right side of the window.
    for i in range(n): # i points to the right of the window
        s += nums[i] # Add element to the right of the window
        # Increment left side of the window, if the invariant is no true any more
        while left <= i and s > k: # Invariant if the window has sum > k, than remove elements from left.
            s -= nums[left] # Pop element from the left
            left += 1 # Increment left pointer
        if s == k: # Check if the window sum == k
            count += 1 # Increment counter if the sum matches the description
    return count

An important point to remember when applying variable length sliding window pattern is:

Adding an element to the right side window accumulates/increases the stored result in the window.
Removing an element from the left side of the window de-accumulates/decreases the stored result in the window.
An invariant can be defined which can help to slide the window across the array.

These three conditions are important to meet the invariant supporting the sliding of the window in the array. For example if the given numbers are both positive and negative and window uses a sum function then adding number to the window can both increase/decrease the total of the window. In such cases sliding window pattern won’t work in the problem as the invariant used to slide the window will not work. Whereas if there are just positive numbers then adding a number to the window only increases the total in the window and at some point the invariant will be not valid which moves the left pointer to make invariant true again.

So it is very critical to define what would be the accumulation function and invariant supporting the sliding of the window.

Next article will be discussing some such problems and apply the template to the problems.

Example Problems:

Longest substring with at most two distict characters Medium

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.
Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    mp = defaultdict(int)
    left, sol, n = 0, 0, len(s)
    for i in range(n):
        mp[s[i]] += 1 # Add current element to the right side of the window
        while left <= i and len(mp) > 2: # Invariant if window size is greater than 2 remove elements from left
            mp[s[left]] -= 1   # Remove left element from the window
            if mp[s[left]] == 0: # Once left element is removed, check if value is zero delete it
                del mp[s[left]]
            left += 1 # Move the left side of the window
        sol = max(sol, i - left + 1) # Update the global solution, with current length
    return sol

Longest substring without repeated characters Medium

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

This problem also is very similar to the previous problem, only change is the invariant when the size of the map is smaller than the length of the substring it means that the substring doesn’t have app distinct characters.

def lengthOfLongestSubstring(s: str) -> int:
    mp, n, left = defaultdict(int), len(s), 0
    sol = 0
    for i in range(n):
        mp[s[i]] += 1
        #Invariant if map contains no repeated character of the current element.
        while left <= i and mp[s[i]] > 1: # Invariant here can also len(mp) < i - left + 1 as repeated characters size of map will be smaller than size of substring.
            mp[s[left]] -= 1
            if mp[s[left]] == 0:
                del mp[s[left]]
            left += 1  
        sol = max(sol, i - left + 1)
    return sol

Further Optimization can be done to move the left pointer directly to the last known index of the current index if it is greater than the left previous left pointer. This optimization is quite specfic to this problem.

def lengthOfLongestSubstring(s: str) -> int:
    mp, n, left = defaultdict(int), len(s), 0
    sol = 0
    for i in range(n):
        if s[i] in mp:
            left = max(left, mp[s[i]] + 1) # Left window will move directly to s[i] + 1 if it is later than the left pointer.
        mp[s[i]] = i
        sol = max(sol, i - left + 1)
    return sol