“Magic” Solution to LeetCode Problems: Sliding Window Algorithm

First, you can check out this article to see how sliding window algorithm looks like:

Leetcode Pattern 2 | Sliding Windows for Strings

So, basically, sliding window comes in very handy for string problem. While it works as a “magic” for subarray problems too. Here I give a subarray problem’s definition:

Subarray problems normally requires you to find consecutive subarray in a given array. The key words are “maximum/minimum/number of all satisfied subarries”. Common questions:

• Return the length of the subarray with the maximum sum/product
• Return the maximum/minimum length/number of subarries whose sum/product equals to K.
• Their brute force complexity is O(n³).

Normally, to solve these problems, different types require different math formula and dynamic programming to solve it. Good news: In practical, all of these problems can be solved using two or three pointers (which is also sliding window algorithm).

Example using Two Pointers Sliding Window Algorithm

53. Maximum Subarray
 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
 the contiguous subarray [4,-1,2,1] has the largest sum = 6.

The solution: for this problem, we need to figure out when we need to “slide” the window. Analyze the problem:

window     i       j    nums[j]       window_sum
           0       0       -2        -2  move i by one    
           1       1        1         1
           1       2        -3       -2 move i by one
           2       3        4            1
           2       4        -1        -2 move i
                   5        2

The rule is we keep shrink the window if the window value is negative:

from sys import maxsize
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        i, j = 0, 0 #i<=j
        maxValue = -maxsize
        window_sum = 0
        while j < len(nums):
            window_sum += nums[j]
            j += 1
            maxValue = max(maxValue, window_sum)
            while i<j and window_sum < 0: #use while to shrink the window
                window_sum -= nums[i]
                i += 1                           
        return maxValue

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

The sliding window solution is:

class Solution:
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums)==1:
            return 1
        i,j = 0,0
        max_length = 0
        while j < len(nums):
            j += 1 #slide the window
            max_length = max(max_length, j-i)
            # when condition violated, reset the window
            if j<len(nums) and nums[j-1]>=nums[j]:
                i = j
                         
        return max_length

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

The sliding window solution will only take O(n).

def minSubArrayLen(self, s, nums):
            """
            :type s: int
            :type nums: List[int]
            :rtype: int
            """
            i,j = 0,0
            preSum =0
            min_length = len(nums)+1
            while j < len(nums):          
                preSum += nums[j]
                j+=1
                #shrink the sliding window size
                while i < j and preSum >= s:
                    min_length = min(min_length, j-i)
                    preSum -= nums[i] #shrink
                    i += 1
            return min_length if min_length< len(nums)+1 else 0

Example using Three Pointers Sliding Window Algorithm

930. Binary Subarrays With Sum

In an array A of 0s and 1s, how many non-empty subarrays have sum S?
Example 1:
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
Note:
A.length <= 30000
 0 <= S <= A.length
 A[i] is either 0 or 1.

For example in the following problem, if we want to use two pointers to solve the problem, we would find we miss the case; like in the example $1, 0, 1, 0, 1$, when $j = 5$, $i = 1$, the sum is $2$, but the algorithm would miss the case of $i = 2$, which has the same sum value.

To solve this problem, we keep another index $i_hi$, in addition to the moving rule of $i$, it also moves if the sum is satisfied and that value is $0$. This is actually a Three pointer algorithm, it is also a mutant sliding window algorithm.

def numSubarraysWithSum(self, A, S):
        i_lo, i_hi, j = 0, 0, 0 #i_lo <= j
        sum_lo = sum_hi = 0
        ans = 0
        while j < len(A):
            # Maintain i_lo, sum_lo:
            # While the sum is too big, i_lo += 1
            sum_lo += A[j]
            while i_lo < j and sum_lo > S:
                sum_lo -= A[i_lo]
                i_lo += 1
# Maintain i_hi, sum_hi:
            # While the sum is too big, or equal and we can move, i_hi += 1
            sum_hi += A[j]
            while i_hi < j and (
                    sum_hi > S or sum_hi == S and not A[i_hi]):
                sum_hi -= A[i_hi]
                i_hi += 1
if sum_lo == S:
                ans += i_hi - i_lo + 1
            j += 1
return ans