Sliding Window Fixed Size Basics¶

Table of Contents¶

1456. Maximum Number of Vowels in a Substring of Given Length¶

LeetCode | LeetCode CH (Medium)
Tags: string, sliding window

1456. Maximum Number of Vowels in a Substring of Given Length - Python Solution

# Sliding Window Fixed Size
def maxVowels1(s: str, k: int) -> int:
    res, cnt = 0, 0

    for idx, ch in enumerate(s):
        if ch in "aeiou":
            cnt += 1

        if idx < k - 1:
            continue

        res = max(res, cnt)

        if s[idx - k + 1] in "aeiou":
            cnt -= 1

    return res


# Sliding Window Fixed Size
def maxVowels2(s: str, k: int) -> int:
    vowels = set("aeiou")
    n = len(s)
    cnt, res = 0, 0

    for i in range(k):
        if s[i] in vowels:
            cnt += 1

    res = cnt

    for i in range(k, n):
        if s[i] in vowels:
            cnt += 1
        if s[i - k] in vowels:
            cnt -= 1
        res = max(res, cnt)

    return res


s = "abciiidef"
k = 3
print(maxVowels1(s, k))  # 3
print(maxVowels2(s, k))  # 3

643. Maximum Average Subarray I¶

LeetCode | LeetCode CH (Easy)
Tags: array, sliding window

643. Maximum Average Subarray I - Python Solution

from typing import List


# Sliding Window Fixed Size
def findMaxAverage1(nums: List[int], k: int) -> float:
    maxSum = float("-inf")
    cur = 0

    for idx, num in enumerate(nums):
        cur += num

        if idx < k - 1:
            continue

        maxSum = max(maxSum, cur)
        cur -= nums[idx - k + 1]

    return maxSum / k


# Sliding Window Fixed Size
def findMaxAverage2(nums: List[int], k: int) -> float:
    n = len(nums)
    if n == 1:
        return float(nums[0])

    cur = sum(nums[:k])

    maxSum = cur
    for i in range(k, n):
        cur += nums[i] - nums[i - k]
        maxSum = max(maxSum, cur)

    return maxSum / k


nums = [1, 12, -5, -6, 50, 3]
k = 4
print(findMaxAverage1(nums, k))  # 12.75
print(findMaxAverage2(nums, k))  # 12.75

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold¶

LeetCode | LeetCode CH (Medium)
Tags: array, sliding window

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold - Python Solution

from typing import List


# Sliding Window Fixed Size
def numOfSubarrays(arr: List[int], k: int, threshold: int) -> int:
    target = k * threshold
    res, cur = 0, 0

    for idx, num in enumerate(arr):
        cur += num

        if idx < k - 1:
            continue

        if cur >= target:
            res += 1

        cur -= arr[idx - k + 1]

    return res


arr = [2, 2, 2, 2, 5, 5, 5, 8]
k = 3
threshold = 4
print(numOfSubarrays(arr, k, threshold))  # 3

2090. K Radius Subarray Averages¶

LeetCode | LeetCode CH (Medium)
Tags: array, sliding window

2090. K Radius Subarray Averages - Python Solution

from typing import List


# Sliding Window Fixed Size
def getAverages(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    res = [-1 for _ in range(n)]
    size = 2 * k + 1

    if size > n:
        return res
    if k == 0:
        return nums

    cur = 0
    for idx, num in enumerate(nums):
        cur += num

        if idx < 2 * k:
            continue

        res[idx - k] = cur // size
        cur -= nums[idx - 2 * k]

    return res


nums = [7, 4, 3, 9, 1, 8, 5, 2, 6]
k = 3
print(getAverages(nums, k))
# [-1, -1, -1, 5, 4, 4, -1, -1, -1]

2379. Minimum Recolors to Get K Consecutive Black Blocks¶

LeetCode | LeetCode CH (Easy)
Tags: string, sliding window

2379. Minimum Recolors to Get K Consecutive Black Blocks - Python Solution

# Sliding Window Fixed Size
def minimumRecolors(blocks: str, k: int) -> int:
    cnt, res = 0, float("inf")

    for idx, block in enumerate(blocks):
        if block == "W":
            cnt += 1

        if idx < k - 1:
            continue

        res = min(res, cnt)

        if blocks[idx - k + 1] == "W":
            cnt -= 1

    return res


blocks = "WBBWWBBWBW"
k = 7
print(minimumRecolors(blocks, k))  # 3

2841. Maximum Sum of Almost Unique Subarray¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sliding window

2841. Maximum Sum of Almost Unique Subarray - Python Solution

from collections import defaultdict
from typing import List


# Sliding Window Fixed Size
def maxSum(nums: List[int], m: int, k: int) -> int:
    counts = defaultdict(int)
    cur, res = 0, 0

    for idx, num in enumerate(nums):
        counts[num] += 1
        cur += num

        if idx < k - 1:
            continue

        if len(counts) >= m:
            res = max(res, cur)

        first = idx - k + 1
        cur -= nums[first]
        counts[nums[first]] -= 1
        if counts[nums[first]] == 0:
            del counts[nums[first]]

    return res


nums = [2, 6, 7, 3, 1, 7]
m = 3
k = 4
print(maxSum(nums, m, k))  # 18

2461. Maximum Sum of Distinct Subarrays With Length K¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sliding window

2461. Maximum Sum of Distinct Subarrays With Length K - Python Solution

from collections import defaultdict
from typing import List


# Sliding Window Fixed Size
def maximumSubarraySum(nums: List[int], k: int) -> int:
    counts = defaultdict(int)
    res = 0
    cur = 0

    for idx, num in enumerate(nums):
        counts[num] += 1
        cur += num

        if idx < k - 1:
            continue

        if len(counts) == k:
            res = max(res, cur)

        first = idx - k + 1
        cur -= nums[first]
        counts[nums[first]] -= 1
        if counts[nums[first]] == 0:
            del counts[nums[first]]

    return res


nums = [1, 5, 4, 2, 9, 9, 9]
k = 3
print(maximumSubarraySum(nums, k))  # 15

1423. Maximum Points You Can Obtain from Cards¶

LeetCode | LeetCode CH (Medium)
Tags: array, sliding window, prefix sum

1423. Maximum Points You Can Obtain from Cards - Python Solution

from typing import List


# Sliding Window Fixed Size
def maxScore(cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    j = n - k
    total = sum(cardPoints)

    if j == 0:
        return total

    curSum, minSum = 0, float("inf")

    for idx, point in enumerate(cardPoints):
        curSum += point

        if idx < j - 1:
            continue

        minSum = min(minSum, curSum)
        curSum -= cardPoints[idx - j + 1]

    return total - minSum


cardPoints = [1, 2, 3, 4, 5, 6, 1]
k = 3
print(maxScore(cardPoints, k))  # 12

1052. Grumpy Bookstore Owner¶

LeetCode | LeetCode CH (Medium)
Tags: array, sliding window
Hint: Maximize the number of unsatisfied customers in the fixed window of minutes.

1052. Grumpy Bookstore Owner - Python Solution

from typing import List


# Sliding Window Fixed Size
def maxSatisfied(customers: List[int], grumpy: List[int], minutes: int) -> int:
    n = len(customers)
    k = minutes
    if k >= n:
        return sum(customers)

    total_satisfied = sum(customers[i] for i in range(n) if not grumpy[i])

    cur, maxGrumpy = 0, 0

    for idx, customer in enumerate(customers):
        cur += customer if grumpy[idx] else 0

        if idx < k - 1:
            continue

        maxGrumpy = max(maxGrumpy, cur)

        cur -= customers[idx - k + 1] if grumpy[idx - k + 1] else 0

    return total_satisfied + maxGrumpy


customers = [1, 0, 1, 2, 1, 1, 7, 5]
grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
minutes = 3
print(maxSatisfied(customers, grumpy, minutes))  # 16

1652. Defuse the Bomb¶

LeetCode | LeetCode CH (Easy)
Tags: array, sliding window
How to deal with the circular array?
- Trick: mod (index % length)

1652. Defuse the Bomb - Python Solution

from typing import List


# Sliding Window Fixed Size
def decrypt(code: List[int], k: int) -> List[int]:
    n = len(code)
    res = [0 for _ in range(n)]
    if k == 0:
        return res

    left, right = (1, k) if k > 0 else (n + k, n - 1)

    curSum = 0
    for i in range(left, right + 1):
        curSum += code[i % n]

    for i in range(n):
        res[i] = curSum

        curSum -= code[left % n]
        left += 1
        right += 1
        curSum += code[right % n]

    return res


code = [2, 4, 9, 3]
k = -2
print(decrypt(code, k))  # [12, 5, 6, 13]

1176. Diet Plan Performance¶

LeetCode | LeetCode CH (Easy)
Tags: array, sliding window

1100. Find K-Length Substrings With No Repeated Characters¶

LeetCode | LeetCode CH (Medium)
Tags: hash table, string, sliding window

1852. Distinct Numbers in Each Subarray¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sliding window

1151. Minimum Swaps to Group All 1's Together¶

LeetCode | LeetCode CH (Medium)
Tags: array, sliding window

1151. Minimum Swaps to Group All 1's Together - Python Solution

from typing import List


def minSwaps(data: List[int]) -> int:
    n = len(data)
    total = sum(data)

    if total == 0 or total == 1 or total == n:
        return 0

    max_count = 0
    cur = 0
    left = 0

    for right in range(n):
        cur += data[right]

        if right - left + 1 > total:
            cur -= data[left]
            left += 1

        max_count = max(max_count, cur)

    return total - max_count


data = [1, 0, 1, 0, 1]
print(minSwaps(data))  # 1

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sliding window