Sliding window monotonic queue:

209. Minimum Size Subarray Sum

Minimum Size Subarray Sum - LeetCode

Binary search , O(nlogn), 128 ms.

class Solution:
    def minSubArrayLen(self, K: int, A: List[int]) -> int:
        if not A:return 0
        dp = A[:]
        for i in range(1, len(A)):
            if dp[i-1]>0:
                dp[i] = dp[i-1]+A[i]
        if max(dp) <K:return 0
        import itertools
        cusum = list(itertools.accumulate([0]+A))
        def good(m):
            for i in range(len(A)):
                if i+m <=len(A) and cusum[i+m]-cusum[i]>=K:return True
            return False
            
        def binary():
            l, r = 1, len(A)
            while l<r:
                m = (l+r)//2
                if good(m):
                    r = m
                else:
                    l = m+1 
            return l
        return binary()

O(N) (80 ms)

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i, res = 0, float('inf')
        this_sum = 0
        for j, num in enumerate(nums):
            this_sum += num
            while this_sum >= s:
                res = min(res, j-i+1)
                this_sum -= nums[i]
                i += 1
        return res if res!=float('inf') else 0

Or

class Solution:
    def minSubArrayLen(self, s: int, A: List[int]) -> int:
        i, res = 0, len(A) + 1
        for j in range(len(A)):
            s -= A[j]
            while s <= 0:
                res = min(res, j - i + 1)
                s += A[i]
                i += 1
        return res % (len(A) + 1)

[Java/C++/Python] Sliding Window - LeetCode Discuss

862. Shortest Subarray with Sum at Least K

Negative value makes it harder than the above one. Also negative value makes the binary search impossible.

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

def shortestSubarray(self, A, K):
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

Or

class Solution:
    def shortestSubarray(self, A, K):
        d = collections.deque([0])
        res = float('inf')
        cusum = list(itertools.accumulate([0]+A))
        for i, a in enumerate(A):
            while d and cusum[i+1] - cusum[d[0]] >= K:
                res = min(res, i + 1 - d.popleft())
            while d and cusum[i+1] <= cusum[d[-1]]:
                d.pop()
            d.append(i + 1)
        return -1 if res == float('inf') else res

“Same idea, this is my thinking process to improve the O(N²) solution to O(N).

public int shortestSubarray(int[] A, int K) {
        int[] presum = new int[A.length+1];
        int res = A.length+1;
        for(int i=1;i<presum.length;i++){
            presum[i] = presum[i-1]+A[i-1];
            for(int j=i-1;j>=0;j--){
                if(presum[i]-presum[j]>=K)
                    res = Math.min(res, i-j);
            }
        }
        return res == (A.length+1)?-1: res;
    }

This is a O(n²) solution ( Time Limit Exceeded ).

If we have an array prefix sum array like [0,1,2,3,4,10,7,4,5,14,16,……. ], K=11
The best answer is: length=2 (i=8, j=10).

For the subarray [4,10,7,4], do we need the first three elements 4,10,7? We don’t, if we have presum[j]-10>=K, presum[j]-4(later one) is also larger than K and has a shorter length. Therefore, the elements we want to use in the inner loop are actually like [0,1,2,3,**4(later one),**5,14,16, ……]. When we visit later 4 in the outer loop, we can remove previous elements that are larger than 4. What we get will be a ascent array.

The first answer we found will be length=6 (i=3, j=9). After we find this answer, do we still need the elements 0,1,2? We don’t. Since the next answer must be shorter than this one, we don’t need to compare later element with these elements. Now, the array will be [3, 4, 5, 14, 16, …..]

Then, when we visit 16 in the outer loop. And we will sequentially visit and remove 3,4 in the inner loop. Finally, we get the best answer (i=8, j=10).

Okay, there are two steps we need to reduce redundant calculations.

1. Remove previous elements that are larger than the current one ( second while loop ).
2. If we find an answer (i, j), remove smaller elements than presum[i]. Since we have keep elements in ascent order with the first step, we can just remove previous elements before i ( fisrt while loop ).

Since we only need to remove head or tail elements, Deque will be a great data structure.

”

Reference :

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C++JavaPython-O(N)-Using-Deque/150644

Another nice explanation can be found here:

Python Simple & Readable // AC Heapq Solution w/ Detailed Explanation - LeetCode Discuss

It also has some relationship to Monotonic Queue.

A summary about Monotonic Queue can be found here

Monotonic Queue

The following question can be solved by monotonic queue:

• LC84. Largest Rectangle in Histogram
• LC239. Sliding Window Maximum
• LC739. Daily Temperatures
• LC862. Shortest Subarray with Sum at Least K
• LC901. Online Stock Span
• LC907. Sum of Subarray Minimums

76. Minimum Window Substring

Minimum Window Substring - LeetCode

https://leetcode.com/problems/minimum-window-substring/discuss/226911/Python-two-pointer-sliding-window-with-explanation

The idea is we use a variable-length sliding window which is gradually applied across the string. We use two pointers: start and end to mark the sliding window. We start by fixing the start pointer and moving the end pointer to the right. The way we determine the current window is a valid one is by checking if all the target letters have been found in the current window. If we are in a valid sliding window, we first make note of the sliding window of the most minimum length we have seen so far. Next we try to contract the sliding window by moving the start pointer. If the sliding window continues to be valid, we note the new minimum sliding window. If it becomes invalid (all letters of the target have been bypassed), we break out of the inner loop and go back to moving the end pointer to the right.

class Solution():
    def minWindow(self, search_str: str, target: str) -> str:
        target_cnt = collections.Counter(target)
        start, end, min_window = 0, 0, ""
        to_be_found = len(target)        
        for end in range(len(search_str)):
   # If we see a target letter, decrease the total target letter count
            if target_cnt[search_str[end]] > 0:
                to_be_found -= 1
                
            # Decrease the letter count for the current letter
   # If the letter is not a target letter, the count just becomes -ve
            target_cnt[search_str[end]] -= 1
            
   # If all letters in the target are found:
            while to_be_found == 0:
                window_len = end - start + 1
                if not min_window or window_len < len(min_window):
     # Note the new minimum window
                    min_window = search_str[start : end + 1]
                    
    # Increase the letter count of the current letter
                target_cnt[search_str[start]] += 1
                
    # If all target letters have been seen and now, a target letter is seen with count > 0
    # Increase the target length to be found. This will break out of the loop
                if target_cnt[search_str[start]] > 0:
                    to_be_found += 1
                    
                start += 1
                
        return min_window

for this test case,

“ADOBECODEBANC”
“ABC”

we will have an output like this

0 5 Counter({'A': 0, 'B': 0, 'C': 0, 'D': -1, 'O': -1, 'E': -1})
1 10 Counter({'A': 0, 'C': 0, 'B': -1, 'D': -2, 'O': -2, 'E': -2})
2 10 Counter({'A': 0, 'C': 0, 'B': -1, 'D': -1, 'O': -2, 'E': -2})
3 10 Counter({'A': 0, 'C': 0, 'B': -1, 'D': -1, 'O': -1, 'E': -2})
4 10 Counter({'A': 0, 'B': 0, 'C': 0, 'D': -1, 'O': -1, 'E': -2})
5 10 Counter({'A': 0, 'B': 0, 'C': 0, 'D': -1, 'O': -1, 'E': -1})
6 12 Counter({'A': 0, 'B': 0, 'C': 0, 'D': -1, 'O': -1, 'E': -1, 'N': -1})
7 12 Counter({'A': 0, 'B': 0, 'C': 0, 'O': 0, 'D': -1, 'E': -1, 'N': -1})
8 12 Counter({'A': 0, 'B': 0, 'C': 0, 'D': 0, 'O': 0, 'E': -1, 'N': -1})
9 12 Counter({'A': 0, 'B': 0, 'C': 0, 'D': 0, 'O': 0, 'E': 0, 'N': -1})

The code for is here:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target_cnt = collections.Counter(t)
        to_be_found = len(t)
        i, j = 0, len(s)-1
        min_win = ""
        for j in range(len(s)):
            if target_cnt[s[j]]>0:to_be_found -= 1
            target_cnt[s[j]] -=1
            while to_be_found==0:
                #print(i, j, target_cnt)
                if not min_win or j-i+1<len(min_win):
                    min_win = s[i:j+1]
                target_cnt[s[i]]+=1
                if target_cnt[s[i]]>0:to_be_found +=1
                i+=1
        return min_win

We can change the logic a little bit to make it more natural by changing to_be_found to found

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target_cnt = collections.Counter(t)
        i, j, found = 0, len(s)-1, 0
        min_win = ""
        for j in range(len(s)):
            if target_cnt[s[j]]>0:found += 1
            target_cnt[s[j]] -=1
            while found==len(t):
                #print(i, j, target_cnt)
                if not min_win or j-i+1<len(min_win):
                    min_win = s[i:j+1]
                target_cnt[s[i]]+=1
                if target_cnt[s[i]]>0:found -=1
                i+=1
        return min_win

Actually we even don’t need initialize j. So the code can be written as:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target_cnt = collections.Counter(t)
        i, found = 0, 0
        min_win = ""
        for j in range(len(s)):
            if target_cnt[s[j]]>0:found += 1
            target_cnt[s[j]] -=1
            while found==len(t):
                #print(i, j, target_cnt)
                if not min_win or j-i+1<len(min_win):
                    min_win = s[i:j+1]
                target_cnt[s[i]]+=1
                if target_cnt[s[i]]>0:found -=1
                i+=1
        return min_win