Sliding window

Posted on Edited on In , Views:

Intro

Window Sliding Technique is a computational technique that aims to reduce the use of nested loops and replace it with a single loop, thereby reducing the time complexity.

[Leetcode 3] Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

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

Example 3:

1
2
3
4
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.

Constraints:

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
            
        longestLen = 0
        left, currLen = 0, 0
        idxMap = {}
        for right in range(len(s)):
            c = s[right]
            if c not in idxMap:
                # extend right pointer
                idxMap[c] = right
                
                # calculate current length
                currLen += 1
            else:
                # calculate longest length
                longestLen = max(longestLen, currLen)

                # reset left pointer
                if left <= idxMap[c]:
                    left = idxMap[c] + 1

                # update index for the duplicate item
                idxMap[c] = right

                # reset current length
                currLen = right - left + 1

        return max(longestLen, currLen)

[Leetcode 42] Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

1
2
3
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

1
2
3
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    # e.g.
    # height:  3 2 4, water trapped: (3 - 2) = 1
    #              |
    #          |   |
    #          | | |
    #          | | |
    # The water to be trapped is determined by the lower bar
    # height:  3 2 1 4, water trapped: (3 - 2) + (3 - 1) = 3
    #                |
    #          |     |
    #          | |   |
    #          | | | |
    def trap(self, height: List[int]) -> int:
        ans = 0
        leftMax, rightMax = 0, 0
        i, j = 0, len(height) - 1

        while i <= j:
            leftMax = max(leftMax, height[i])
            rightMax = max(rightMax, height[j])

            # trapped water determined by highest bar
            if leftMax < rightMax:
                ans += leftMax - height[i]
                i += 1
            else:
                ans += rightMax - height[j]
                j -= 1

        return ans

[Leetcode 209] Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

1
2
3
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

1
2
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

1
2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

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)).

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def minSubArrayLen_bf(self, target: int, nums: List[int]) -> int:
        minLen = len(nums) + 1

        for i in range(len(nums)):
            currSum = 0
            for j in range(i, len(nums)):
                currSum += nums[j]
                if currSum >= target:
                    minLen = min(minLen, j - i + 1)

        return minLen if minLen < len(nums) + 1 else 0

    # sliding window(with two pointers)
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minLen = len(nums) + 1  # length of min subarray
        left = 0  # left pointer
        currSum = 0  # sum of the current window
        currLen = 0  # window length

        # right pointer
        for right in range(len(nums)):
            # extend the current window until the sum is >= target
            currSum += nums[right]

            while currSum >= target:
                currLen = right - left + 1 
                minLen = min(minLen, currLen) 

                # shink the window from left side
                currSum -= nums[left]
                left += 1

        return minLen if minLen < len(nums) + 1 else 0

[Leetcode 1004] Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

Example 1:

1
2
3
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]

Example 2:

1
2
3
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    # e.g. [1 1 1 0 0 0 1 1 1 1 0], k = 2
    #       ^         ^             l = 0, r = 5, k = -1 keep moving right pointer until k < 0
    #         ^       ^             l = 1, r = 5, k = -1 increment k if nums[left]==0, and move left pointer forward 
    #           ^       ^           l = 2, r = 6, k = -1
    #             ^       ^         l = 3, r = 7, k = -1
    #               ^       ^       l = 4, r = 8, k = 0
    #               ^         ^     l = 4, r = 9, k = 0
    #                 ^          ^  l = 5, r = 10,k = -1
    # result = r - l + 1 = 10 - 5 + 1 = 6
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = r = 0

        for r in range(len(nums)):
            # use flip opportunity if the right side of window is 0
            if nums[r] == 0:
                k -= 1
            
            if k < 0:
                # recover the flip opportunity if the left side is 0
                if nums[l] == 0:
                    k += 1
                
                # shrink the window from left side
                l += 1
            #print(l,r,k)
         
        return r - l + 1

[Leetcode 1456] Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.

Example 1:

1
2
3
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

1
2
3
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

1
2
3
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a','e','i','o','u'}
        maxLen = 0
        count = 0
        for i in range(len(s)):
            # first window with size k
            if i < k :
                if s[i] in vowels:
                    count += 1
            # moving out of window
            else:
                # calculate max length from previous window 
                maxLen = max(maxLen, count)

                # recalculate for the current new window
                if s[i - k] in vowels:
                    count -= 1
                if s[i] in vowels:
                    count += 1

        # calculate the last window
        maxLen = max(maxLen, count)

        return maxLen

[Leetcode 1493] Longest Subarray of 1’s After Deleting One Element

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array. Return 0 if there is no such subarray.

Example 1:

1
2
3
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

1
2
3
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

1
2
3
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        l = r = 0
        zeros = 0
        longest = 0

        for r in range(len(nums)):
            # count zeros
            if nums[r] == 0:
                zeros += 1

            # move left pointer forward until one zero left
            while zeros > 1:
                if nums[l] == 0:
                    zeros -= 1

                l += 1

            # calcualte longest subarray between left and right
            longest = max(longest, r - l + 1 - zeros)

        # note that both 0 and 1 can be deleted
        return  longest - 1 if longest == len(nums) else longest