Skip to main content

Fixed Window

while expand

Naïve Sum/Average​

Max Sum Subarray of size K​

Easy·
Explanation

The objective is to find the maximum sum of all contiguous subarrays of length K in a given array. This problem can be efficiently solved by employing the sliding window technique to maintain the sum of elements within the current window, subsequently finding the maximum sum.

Expansion:

  • Incrementally add each element's value to a running total as the right pointer advances, until the window reaches the desired size K.
  • This phase accumulates the initial sum required to compute the first potential maximum sum.

Logic:

  • Compare the current window's sum with the maximum sum recorded so far and update the maximum sum if the current window's sum is greater.

Shrinking:

  • Before advancing the window, subtract the element at the left edge of the window from the total sum.
  • Increment the left pointer to slide the window one position to the right, preparing for the next window's sum calculation.
Analysis
Time
O(N)
  • N is the total number of elements in the array.
  • The algorithm ensures each element is added and subtracted exactly once, resulting in linear time complexity.
Space
O(1)
  • The space complexity is constant as the solution utilizes a fixed number of variables, irrespective of the input array's size.
FIG. MAX SUM SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxSubarraySum(self, arr, k):
n = len(arr)
left = right = 0
total = maxi = 0
while right < n:
# Expansion
while right < n and right - left < k:
total += arr[right]
right += 1
# Logic
maxi = max(maxi, total)
# Shrinking
total -= arr[left]
left += 1
return maxi

643. Maximum Average Subarray I​

Easy·
Explanation

The goal is to find the maximum average value of all contiguous subarrays of length k. The sliding window technique maintains the running sum of the current window, then calculates its average -- avoiding recomputation across overlapping windows.

Expansion:

  • Iterate through the array using a right pointer, adding each element's value to the total sum until the window reaches size k.
  • This step builds up the initial sum required to calculate the first average.

Logic:

  • Calculate the average of the current window by dividing the total sum by k.
  • Update maxi if the current window's average is higher.

Shrinking:

  • Before moving the window forward, subtract the element at the left edge from the total sum.
  • Increment the left pointer to slide the window one position to the right.
Analysis
Time
O(N)
  • N is the number of elements in the input array.
  • Each element is processed exactly once, making the algorithm linear time.
Space
O(1)
  • Only a fixed number of variables are used, independent of the input array size.
FIG. 643 MAXIMUM AVERAGE SUBARRAY I● INTERACTIVE
visualization loads as you reach it
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
n = len(nums)
left = right = 0
maxi = -float("inf") # Since negative numbers are allowed in the array
total = 0
while right < n:
# Expansion
while right < n and right - left < k:
total += nums[right]
right += 1
# Logic
maxi = max(maxi, total / k)
# Shrinking
total -= nums[left]
left += 1
return maxi

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

Medium·
Explanation

The challenge is to count contiguous subarrays of length k whose average is greater than or equal to a given threshold. The sliding window technique maintains the running sum to evaluate each window's average in O(1) per step.

Expansion:

  • Iterate through the array using a right pointer, adding each element's value to a running total until the window attains size k.
  • This step accumulates the sum needed to evaluate the first average.

Logic:

  • isAboveThreshold() determines if the current window's average meets or exceeds threshold.
  • If it does, increment count.

Shrinking:

  • Before advancing the window, subtract the leftmost element's value from the total sum.
  • Increment the left pointer to shift the window one position to the right.
Analysis
Time
O(N)
  • N is the number of elements in the input array.
  • Each element is added and removed from the window exactly once.
Space
O(1)
  • Only a fixed number of variables are used regardless of input size.
FIG. 1343 NUMBER OF SUB ARRAYS OF SIZE K AND AVERAGE GREATER THAN OR EQUAL TO THRESHOLD● INTERACTIVE
visualization loads as you reach it
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
n = len(arr)
left = right = 0
total = count = 0
 
isAboveThreshold = lambda total: total / k >= threshold
 
while right < n:
# Expansion
while right < n and right - left < k:
total += arr[right]
right += 1
# Logic
count += isAboveThreshold(total)
# Shrinking
total -= arr[left]
left += 1
return count

2090. K Radius Subarray Averages​

Medium·
Explanation

For each index i, the result is the integer average of the 2*k+1 elements centered at i. If fewer than k elements exist on either side, result stays -1. A fixed window of size w = 2*k+1 slides across nums, writing the floor-average to the center position on every valid window.

Expansion:

  • Advance right until the window reaches size w, accumulating the running total.

Logic:

  • If right - left == w, the window is full. Compute result[left + k] = total // w.

Shrinking:

  • Drop nums[left] from total and advance left to slide the window forward.
Analysis
Time
O(N)
  • N is the number of elements in nums.
  • Each element is added to and removed from the window exactly once.
Space
O(N)
  • The result array has the same length as nums.
FIG. 2090 K RADIUS SUBARRAY AVERAGES● INTERACTIVE
visualization loads as you reach it
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
w = 2 * k + 1 # window size
left = right = 0
result = [-1] * n
total = 0
 
getCenter = lambda left, right: left + k
getAvg = lambda total: total // w
 
while right < n:
# Expansion
while right < n and right - left < w:
total += nums[right]
right += 1
# Logic
if right - left == w:
result[getCenter(left, right)] = getAvg(total)
# Shrinking
total -= nums[left]
left += 1
return result

1423. Maximum Points You Can Obtain from Cards​

Medium·
Explanation

Choosing k cards from either end is equivalent to leaving a contiguous subarray of size n - k in the middle. Finding the maximum score from the ends becomes finding the minimum sum of any window of size w = n - k, then subtracting that from the total sum.

Maximum Points You Can Obtain from Cards

Expansion:

  • Advance right until the window reaches size w, accumulating total.

Logic:

  • mini = min(mini, total) -- track the smallest window sum seen so far.

Shrinking:

  • Drop cardPoints[left] from total and advance left, sliding the window forward.

The answer is arr_total - mini.

Analysis
Time
O(2N)
  • N is the total number of cards.
  • arr_total = sum(cardPoints) is one O(N) pass, then the sliding window makes a second O(N) pass, adding and removing each card exactly once - two distinct O(N) passes, 2N.
Space
O(1)
  • Only a fixed number of variables are used regardless of input size.
FIG. 1423 MAXIMUM POINTS YOU CAN OBTAIN FROM CARDS● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
w = n - k # We need to minimize sum of window with size n-k
left = right = 0
total = 0
mini = float("inf")
arr_total = sum(cardPoints)
 
if k >= n:
return arr_total
 
while right < n:
# Expansion
while right < n and right - left < w:
total += cardPoints[right]
right += 1
# Logic
mini = min(mini, total)
# Shrinking
total -= cardPoints[left]
left += 1
return arr_total - mini

1176. Diet Plan Performance​

Easy·
Explanation

A fixed window of size k slides across calories, keeping a running total. After each window fills, a compare lambda scores it against [lower, upper] and adds +1, 0, or -1 to points. The window then shrinks by one from the left.

With calories=[2,6,4,1,1], k=2, lower=3, upper=5:

  • [2,6] → total 8 > 5 → +1 (exceed)
  • [6,4] → total 10 > 5 → +1 (exceed)
  • [4,1] → total 5 ∈ [3,5] → 0 (in range)
  • [1,1] → total 2 < 3 → -1 (deficit)

Result: points = 1

Analysis
Time
O(N)
  • N is the length of calories (5 in the example above).
  • Each element is added once when right expands into it and removed once when left shrinks past it -- calories[0]=2 enters at step 1, leaves at step 5.
Space
O(1)
  • Only scalar variables left, right, total, points are kept -- no auxiliary array regardless of input size.
FIG. 1176 DIET PLAN PERFORMANCE● INTERACTIVE
visualization loads as you reach it
class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
n = len(calories)
left = right = 0
total = points = 0
 
getPerformance = lambda total: (total > upper) - (total < lower)
while right < n:
# Expansion
while right < n and right - left < k:
total += calories[right]
right += 1
# Logic
points += getPerformance(total)
# Shrinking
total -= calories[left]
left += 1
return points

1052. Grumpy Bookstore Owner​

Medium·
Explanation

total starts as the sum of all customers during non-grumpy minutes -- these are always satisfied regardless of the technique. The sliding window of size minutes moves across the array; within it, grumpy minutes contribute their customers via getGrumpyScore, temporarily boosting total. maxi tracks the best combined score seen as the window slides.

Expansion:

  • Advance right until the window reaches minutes in width, adding getGrumpyScore(right) = customers[right] × grumpy[right] to total. Non-grumpy minutes contribute 0 (already in the base).

Logic:

  • maxi = max(maxi, total) -- record the highest total achievable with the window at this position.

Shrinking:

  • Remove the leftmost element's grumpy bonus (getGrumpyScore(left)) before advancing left. If grumpy[left] = 0, this is 0 and total is unchanged.
Analysis
Time
O(2N)
  • N is the number of minutes (length of customers / grumpy).
  • The initial base total is computed in one O(N) pass over zip(customers, grumpy), then the sliding window makes a second O(N) pass, adding and removing each element exactly once - two distinct O(N) passes, 2N.
Space
O(1)
  • Only a fixed number of scalar variables are used regardless of input size.
FIG. 1052 GRUMPY BOOKSTORE OWNER● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxSatisfied(
self, customers: List[int], grumpy: List[int], minutes: int
) -> int:
n = len(customers)
left = right = 0
# Calculate already satisfied customers, ignoring grumpy periods
total = sum(i * (not j) for i, j in zip(customers, grumpy))
maxi = 0
 
getGrumpyScore = lambda idx: customers[idx] * grumpy[idx]
 
while right < n:
# Expansion
while right < n and right - left < minutes:
# Expansion: Add customers affected by grumpiness within the window
total += getGrumpyScore(right)
right += 1
# Logic
maxi = max(maxi, total)
# Shrinking
total -= getGrumpyScore(left)
left += 1
return maxi

1652. Defuse the Bomb​

Easy·
Explanation

The bomb is a circular array: replacing each code[i] with the sum of the next k (or previous |k|) elements. Because the array is circular, indices wrap around using right % n. A single fixed window of size |k| slides across the extended range [0, n + |k| - 1), keeping a running total.

negative distinguishes the two directions. getPosition maps the current window back to the result index being filled: for forward k, the target is the element just before the window ((left-1) % n); for backward k, it's the element just after the window (right % n).

Expansion:

  • Advance right until the window reaches size |k|, accumulating total using code[right % n] to handle the circular wrap.

Logic:

  • result[getPosition()] = total -- write the current window sum into the correct result index.

Shrinking:

  • Subtract code[left] from total and advance left to slide the window one step forward.
Analysis
Time
O(N)
  • N is the length of code.
  • The outer loop runs exactly N times (one window position per result element). Each element is added once during expansion and removed once during shrinking.
Space
O(N)
  • The result array has the same length as code. All other variables are scalar.
FIG. 1652 DEFUSE THE BOMB● INTERACTIVE
visualization loads as you reach it
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
left = right = 0
negative, k = k < 0, abs(k)
total = 0
result = [0] * n
 
getPosition = lambda: right % n if negative else (left - 1) % n
while right < n + k - 1:
# Expansion
while right < n + k - 1 and right - left < k:
total += code[right % n]
right += 1
# Logic
result[getPosition()] = total
# Shrinking
total -= code[left]
left += 1
return result

Hashmap​

187. Repeated DNA Sequences​

Medium·
Explanation

A fixed window of size k = 10 slides over s. The window expands by advancing right until right - left == 10, then substring = s[left:right] is extracted and looked up in counter. When a sequence's count reaches exactly 2 it is added to result -- subsequent occurrences are silently skipped because the condition checks == 2 not >= 2. left increments to slide the window one position forward.

Expansion:

  • Advance right until right - left == k. No element value is read during expansion -- the window boundary is all that matters.

Logic:

  • Extract substring = s[left:right], increment counter[substring], and append to result only when the count becomes exactly 2.

Shrinking:

  • Increment left to slide the window forward, discarding the leftmost character.
Analysis
Time
O(N)
  • N is the length of s.
  • Each character is entered and exited the window exactly once. The substring slice s[left:right] costs O(k) = O(10) = O(1) per window, so the total is O(N).
Space
O(N)
  • counter may hold up to N - k + 1 distinct substrings of length k. Each key is O(k) = O(10) bytes, giving O(N) overall.
FIG. 187 REPEATED DNA SEQUENCES● INTERACTIVE
visualization loads as you reach it
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
k = 10
left = right = 0
counter = collections.Counter()
result = []
while right < n:
# Expansion
while right < n and right - left < k:
right += 1
# Logic
substring = s[left:right]
counter[substring] += 1
if counter[substring] == 2:
result.append(substring)
# Shrinking
left += 1
return result

Hashmap - Duplicate Elements​

219. Contains Duplicate II​

Easy·
Explanation

containsDuplicatesInK is the reusable primitive: a fixed-window sliding window that returns True as soon as any value appears more than once within a window of size k. The check fires inside the expansion loop -- counter[arr[right]] is incremented first, then immediately tested, so the algorithm short-circuits the moment a duplicate is confirmed.

containsNearbyDuplicate adapts it to LC 219 by adjusting k = k + 1 before the call. The +1 accounts for the inclusive bound -- abs(i - j) <= k allows indices exactly k apart, which requires a window of size k + 1.

Expansion:

  • Increment counter[arr[right]], then check if it exceeds 1 before advancing right.

Logic (inline):

  • if counter[arr[right]] > 1: return True -- fires as soon as any value is seen twice within the window.

Shrinking:

  • Decrement counter[arr[left]] and advance left to slide the window forward.
Analysis
Time
O(n)
  • n is the length of nums (arr inside containsDuplicatesInK).
  • Each element enters the counter once in the expansion loop and exits once in the shrinking step, so total work is O(n).
Space
O(k)
  • The counter holds at most k + 1 entries at any time -- one per element in the current window.
FIG. 219 CONTAINS DUPLICATE II● INTERACTIVE
visualization loads as you reach it
class Solution:
def containsDuplicatesInK(self, arr: List[int], k: int) -> bool:
n = len(arr)
left = right = 0
counter = collections.Counter()
while right < n:
# Expansion
while right < n and right - left < k:
counter[arr[right]] += 1
# Logic
if counter[arr[right]] > 1:
return True
right += 1
# Shrinking
counter[arr[left]] -= 1
left += 1
return False
 
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
k = k + 1 # since there is an '=' in abs(i - j) <= k
return self.containsDuplicatesInK(nums, k)

217. Contains Duplicate​

Easy·
Explanation

Reuses containsDuplicatesInK with k = len(nums) so the window covers the entire array. Any duplicate anywhere in the array triggers an early return.

Analysis
Time
O(N)
  • Each element is added to and removed from the counter at most once as the window slides.
Space
O(N)
  • The counter stores at most N distinct elements.
FIG. 217 CONTAINS DUPLICATE● INTERACTIVE
visualization loads as you reach it
class Solution:
def containsDuplicatesInK(self, arr: List[int], k: int) -> bool:
n = len(arr)
left = right = 0
counter = collections.Counter()
while right < n:
# Expansion
while right < n and right - left < k:
counter[arr[right]] += 1
# Logic
if counter[arr[right]] > 1:
return True
right += 1
# Shrinking
counter[arr[left]] -= 1
left += 1
return False
 
def containsDuplicate(self, nums: List[int]) -> bool:
k = len(nums) # since entire array is considered
return self.containsDuplicatesInK(nums, k)

Hashmap - Unique/Distinct Elements​

1876. Substrings of Size Three with Distinct Characters​

Easy·
Explanation

Count all substrings of length 3 that contain distinct characters. A fixed window of size k = 3 slides across the string, using a custom Counter that tracks the number of distinct keys in O(1) via __setitem__.

Custom Counter:

  • self.distinct is maintained incrementally: incremented when a key transitions from ≤0 → >0 (new distinct character appears), decremented when it transitions from >0 → ≤0 (character leaves the window). All other transitions leave distinct unchanged.
  • This means counter.distinct_count() is always the count of keys with a non-zero value - no del needed on shrink.

Expansion:

  • Advance right, incrementing counter[s[right]] until the window reaches size k.

Logic:

  • isGoodSubstring checks if counter.distinct_count() == k. If so, increment good_substrings.

Shrinking:

  • Decrement counter[s[left]]. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(N)
  • Each character is processed at most twice (once when entering and once when leaving the window).
Space
O(1)
  • The hashmap's size is constrained by the window size (k = 3).
FIG. 1876 SUBSTRINGS OF SIZE THREE WITH DISTINCT CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def countGoodSubstrings(self, s: str) -> int:
n = len(s)
k = 3 # Fixed window size for substrings of length three
left = right = 0
counter = Counter()
good_substrings = 0
 
# Lambda function to check if the window has distinct characters
isGoodSubstring = lambda: counter.distinct_count() == k
 
while right < n:
# Expansion: Update the character frequency in the window
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
 
# Logic: If all characters in the window are distinct, increment ans
good_substrings += isGoodSubstring()
# Shrinking: Move the window forward by adjusting character frequencies
counter[s[left]] -= 1
left += 1
return good_substrings

1852. Distinct Numbers in Each Subarray​

Medium·
Explanation

Calculate the number of distinct integers in every subarray of size k. A fixed window slides across nums, using a custom Counter that tracks distinct key count in O(1) via __setitem__. The number of unique elements (counter.distinct_count()) is appended to result for each window position.

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions. Negative values do not count, so counter.distinct_count() is always the count of keys with strictly positive frequency - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[nums[right]] until the window reaches size k.

Logic:

  • Append counter.distinct_count() to result.

Shrinking:

  • Decrement counter[nums[left]]. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(N)
  • Each element enters and exits the window exactly once.
Space
O(k)
  • The hashmap holds at most k distinct elements.
FIG. 1852 DISTINCT NUMBERS IN EACH SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
result = []
counter = Counter()
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
right += 1
# Logic
result.append(counter.distinct_count())
# Shrinking
counter[nums[left]] -= 1
left += 1
return result

2107. Number of Unique Flavors After Sharing K Candies​

Medium·
Explanation

Determine the maximum number of unique candy flavors remaining after giving away exactly k consecutive candies. A custom Counter is initialized with all of candies, then the sliding window of size k represents the shared portion - decrement as candies enter the window, increment as they leave.

Custom Counter:

  • Initialized with Counter(candies) so all flavors start with their full frequencies.
  • self.distinct tracks the number of keys with strictly positive count, updated automatically on ≤0 ↔ >0 transitions in __setitem__. No explicit del is ever needed.

Expansion:

  • Decrement counter[candies[right]] as each candy enters the sharing window. The 1 → 0 transition automatically reduces counter.distinct_count().

Logic:

  • counter.distinct_count() is the number of unique flavors the keeper retains. Track the maximum.

Shrinking:

  • Increment counter[candies[left]] as each candy leaves the sharing window. The 0 → 1 transition automatically increases counter.distinct_count().
Analysis
Time
O(N)
  • Single pass through the candies array with counter modifications.
Space
O(N)
  • The counter may contain every unique candy flavor.
FIG. 2107 NUMBER OF UNIQUE FLAVORS AFTER SHARING K CANDIES● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def shareCandies(self, candies: List[int], k: int) -> int:
n = len(candies)
left = right = 0
counter = Counter(candies)
maxi = 0
 
if k == 0:
return counter.distinct_count()
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[candies[right]] -= 1
right += 1
# Logic
maxi = max(maxi, counter.distinct_count())
# Shrinking
counter[candies[left]] += 1
left += 1
return maxi

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

Medium·
Explanation

Count all k-length substrings of s that consist entirely of unique characters. A fixed window of size k slides across the string using a custom Counter that tracks distinct key count in O(1) via __setitem__. A substring is valid when counter.distinct_count() == k.

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions, so counter.distinct_count() is always the count of keys with strictly positive frequency - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[s[right]] until the window reaches size k.

Logic:

  • isDistinct checks if counter.distinct_count() == k. If so, increment ans.

Shrinking:

  • Decrement counter[s[left]]. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(n)
  • Each of the n characters in s is added to and removed from counter once as right and left each sweep across the string.
Space
O(k)
  • The hashmap holds at most k entries.
FIG. 1100 FIND K LENGTH SUBSTRINGS WITH NO REPEATED CHARACTERS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
counter = Counter()
ans = 0
 
isDistinct = lambda: counter.distinct_count() == k
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# Logic
ans += isDistinct()
# Shrinking
counter[s[left]] -= 1
left += 1
return ans

Substrings of length k with k-1 distinct elements​

Medium·
Explanation

Count all substrings of length k that contain exactly k - 1 distinct characters - meaning exactly one character appears twice in the window. A custom Counter tracks distinct key count in O(1) via __setitem__. A window is valid when counter.distinct_count() == k - 1.

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions, so counter.distinct_count() always reflects strictly positive keys - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[s[right]] until the window reaches size k.

Logic:

  • Check if counter.distinct_count() == k - 1. If so, increment ans.

Shrinking:

  • Decrement counter[s[left]]. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(n)
  • right advances through s once in the expansion loop and left advances once per outer iteration in the shrinking step, each doing O(1) counter work (__setitem__), so total is O(n), where n = len(s).
Space
O(k)
  • counter.counter holds at most k characters, one per element in the current window of size k.
FIG. SUBSTRINGS K 1 DISTINCT● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def substrCount(self, s, k):
n = len(s)
left = right = 0
counter = Counter()
ans = 0
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# Logic
ans += counter.distinct_count() == k - 1
# Shrinking
counter[s[left]] -= 1
left += 1
return ans

2461. Maximum Sum of Distinct Subarrays With Length K​

Medium·
Explanation

Find the maximum sum among all subarrays of size k whose elements are all distinct. A fixed window slides across nums, maintaining a running total of the window's sum and a custom Counter that tracks distinct key count in O(1) via __setitem__. A window of size k has all-distinct elements exactly when counter.distinct_count() == k.

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions, so counter.distinct_count() always reflects strictly positive keys - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[nums[right]] and adding to total until the window reaches size k.

Logic:

  • If isUnique() (all k elements distinct), update maxi = max(maxi, total).

Shrinking:

  • Decrement counter[nums[left]] and subtract from total. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(n)
  • n is the length of nums - left and right each advance at most n times across the run, so every element enters and exits the window exactly once.
Space
O(k)
  • counter holds at most k distinct elements, since the window never exceeds size k.
FIG. 2461 MAXIMUM SUM OF DISTINCT SUBARRAYS WITH LENGTH K● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
left = right = 0
counter = Counter()
maxi = total = 0
 
# Lambda function to check if the window has distinct characters
isUnique = lambda: counter.distinct_count() == k
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
total += nums[right]
right += 1
# Logic
if isUnique():
maxi = max(maxi, total)
# Shrinking
counter[nums[left]] -= 1
total -= nums[left]
left += 1
return maxi

2841. Maximum Sum of Almost Unique Subarray​

Medium·
Explanation

Find the maximum sum among all subarrays of size k that are almost unique - containing at least m distinct elements. A fixed window slides across nums, maintaining a running total of the window's sum and a custom Counter that tracks distinct key count in O(1) via __setitem__. A window qualifies when counter.distinct_count() >= m.

This is the >= m relaxation of 2461. Maximum Sum of Distinct Subarrays With Length K, which demands all k elements be distinct (== k).

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions, so counter.distinct_count() always reflects strictly positive keys - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[nums[right]] and adding to total until the window reaches size k.

Logic:

  • If isAlmostUnique() (at least m distinct elements), update maxi = max(maxi, total).

Shrinking:

  • Decrement counter[nums[left]] and subtract from total. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(N)
  • Each element enters and exits the window exactly once.
Space
O(k)
  • The hashmap holds at most k distinct elements.
FIG. 2841 MAXIMUM SUM OF ALMOST UNIQUE SUBARRAY● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
n = len(nums)
left = right = 0
counter = Counter()
maxi = total = 0
 
# Lambda function to check if the window has distinct characters
isAlmostUnique = lambda: counter.distinct_count() >= m
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[nums[right]] += 1
total += nums[right]
right += 1
# Logic
if isAlmostUnique():
maxi = max(maxi, total)
# Shrinking
counter[nums[left]] -= 1
total -= nums[left]
left += 1
return maxi

1297. Maximum Number of Occurrences of a Substring​

Medium·
Explanation

Return the maximum number of occurrences of any substring of s that has at most maxLetters distinct characters and a length between minSize and maxSize.

Key insight - maxSize is a red herring; only minSize matters. We never need to look at substrings longer than minSize. Here is why, in two steps:

  1. A longer valid substring can never out-count its shorter slices. Take any valid substring t of length L where minSize < L <= maxSize. Slide a window of size minSize inside t: every such slice t' is also valid (it is shorter, so it has ≤ maxLetters distinct characters - shrinking a window can only lose distinct characters, never gain them) and it is contained in t. Every time t appears in s, that same slice t' appears too - so count(t') ≥ count(t). A longer substring can therefore never beat the best minSize substring.

  2. Shorter than minSize is disallowed, so minSize is exactly the sweet spot: short enough to maximize repeats, long enough to be legal. We fix k = minSize and ignore maxSize entirely.

Worked example. s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4.

  • The length-4 substring "aaba" is valid (2 distinct: a,b) and occurs once.
  • Its length-3 prefix "aab" is also valid and occurs twice (positions 0 and 6).
  • So the longer window "aaba" (count 1) is strictly dominated by the shorter "aab" (count 2). Scanning only k = minSize = 3 windows finds the answer 2 without ever materializing a length-4 window.

A custom Counter tracks distinct character count in O(1) via __setitem__. A defaultdict records how many times each length-k substring appears.

Custom Counter:

  • self.distinct increments on ≤0 → >0 transitions and decrements on >0 → ≤0 transitions, so counter.distinct_count() always reflects strictly positive keys - no explicit del needed.

Expansion:

  • Advance right, incrementing counter[s[right]] until the window reaches size k.

Logic:

  • If counter.distinct_count() <= maxLetters, record the substring s[left:right] in substrings and update maxi.

Shrinking:

  • Decrement counter[s[left]]. The __setitem__ hook handles the 1 → 0 transition automatically.
Analysis
Time
O(N·k)
  • Each of the N windows slices a length-k substring (s[left:right]) and hashes it into the map.
Space
O(N·k)
  • The substrings map can hold up to N distinct length-k keys.
FIG. 1297 MAXIMUM NUMBER OF OCCURRENCES OF A SUBSTRING● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n = len(s)
k = minSize
left = right = 0
substrings = collections.defaultdict(int)
maxi = 0
counter = Counter()
while right < n:
while right < n and right - left < k:
counter[s[right]] += 1
right += 1
# print(left, right, counter.distinct_count())
if counter.distinct_count() <= maxLetters:
substrings[s[left:right]] += 1
maxi = max(maxi, substrings[s[left:right]])
counter[s[left]] -= 1
left += 1
return maxi

Hashmap - Anagrams/Permutations​

438. Find All Anagrams in a String​

Medium·
Explanation

Find all start indices of p's anagrams in s. A single custom Counter is initialized with p's character frequencies. The sliding window of size k = len(p) decrements the counter as chars enter and increments as they leave. When counter.distinct_count() == 0, all of p's frequency needs are exactly satisfied - the window is an anagram.

Custom Counter:

  • self.distinct tracks the count of keys with positive (unsatisfied) frequency. Keys going negative (char in window but not in p, or over-represented) do not affect distinct. An anagram occurs when counter.distinct_count() == 0 - no unsatisfied needs remain.

Expansion:

  • Decrement counter[s[right]] as each char enters the window, consuming from p's frequency pool.

Logic:

  • isAnagram checks if counter.distinct_count() == 0. If so, append left to ans.

Shrinking:

  • Increment counter[s[left]] as the leftmost char leaves the window, returning it to the pool.
Analysis
Time
O(n)
  • Each character of s (length n) is processed once by right, and once more by left - counter lookups/updates are O(26) = O(1) for the lowercase alphabet.
Space
O(1)
  • counter is bounded by the alphabet size (26 lowercase letters), independent of n.
FIG. 438 FIND ALL ANAGRAMS IN A STRING● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
 
isAnagram = lambda: counter.distinct_count() == 0
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if isAnagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans

242. Valid Anagram​

Easy·
Explanation

Two strings s and t are anagrams if s contains an anagram of t spanning its entire length. Reuse findAnagrams(s, t) -- if it returns [0], the entire string s is an anagram of t.

Analysis
Time
O(n)
  • findAnagrams scans through s (length n) once with a sliding window matching t's character frequency.
Space
O(1)
  • Fixed-size data structures for character frequency tracking.
FIG. 242 VALID ANAGRAM● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
 
isAnagram = lambda: counter.distinct_count() == 0
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if isAnagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans
 
def isAnagram(self, s: str, t: str) -> bool:
return len(s) == len(t) and self.findAnagrams(s, t) == [0]

567. Permutation in String​

Medium·
Explanation

Determine if s1 is a permutation of any substring in s2. This is searching for an anagram of s1 within s2 -- directly addressed by findAnagrams. If the result is non-empty, a permutation exists.

Analysis
Time
O(N)
  • findAnagrams iterates through s2 with a sliding window of size len(s1).
Space
O(1)
  • Fixed-size structures for character frequency tracking.
FIG. 567 PERMUTATION IN STRING● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n = len(s)
k = len(p)
left = right = 0
counter = Counter(p)
ans = []
 
is_anagram = lambda: counter.distinct_count() == 0
 
while right < n:
# Expansion
while right < n and right - left < k:
counter[s[right]] -= 1
right += 1
# Logic
if is_anagram():
ans.append(left)
# Shrinking
counter[s[left]] += 1
left += 1
return ans
 
def checkInclusion(self, s1: str, s2: str) -> bool:
return self.findAnagrams(s2, s1) != []

Count​

2379. Minimum Recolors to Get K Consecutive Black Blocks​

Easy·
Explanation

Find the minimum number of white blocks ('W') that need to be recolored to achieve k consecutive black blocks. A fixed window of size k slides across blocks, counting white blocks within each window. The minimum white count across all windows equals the minimum recolors needed.

Expansion:

  • Advance right, incrementing whites for each 'W' until the window reaches size k.

Logic:

  • mini = min(mini, whites) -- track the fewest white blocks in any window.

Shrinking:

  • Decrement whites if the leftmost block is 'W', then advance left.
Analysis
Time
O(N)
  • right and left each advance across blocks once, adding and removing each of the N blocks exactly once.
Space
O(1)
  • Only left, right, mini, and whites are tracked, regardless of N.
FIG. 2379 MINIMUM RECOLORS TO GET K CONSECUTIVE BLACK BLOCKS● INTERACTIVE
visualization loads as you reach it
class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
n = len(blocks)
left = right = 0
mini = n
whites = 0
 
isWhite = lambda i: blocks[i] == "W"
 
while right < n:
# Expansion
while right < n and right - left < k:
whites += isWhite(right)
right += 1
# Logic
mini = min(mini, whites)
# Shrinking
whites -= isWhite(left)
left += 1
return mini

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

Medium·
Explanation

Find the maximum number of vowels in any substring of length k. A fixed window slides across s, counting vowels within each window.

Expansion:

  • Advance right, incrementing count for each vowel until the window reaches size k.

Logic:

  • maxi = max(maxi, count) -- track the highest vowel count.

Shrinking:

  • Decrement count if the leftmost character is a vowel, then advance left.
Analysis
Time
O(n)
  • Single pass through the string of length n with constant-time operations per character.
Space
O(1)
  • Fixed-size vowel set and scalar variables.
FIG. 1456 MAXIMUM NUMBER OF VOWELS IN A SUBSTRING OF GIVEN LENGTH● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxVowels(self, s: str, k: int) -> int:
n = len(s)
left = right = 0
maxi = count = 0
vowels = set("aeiou")
 
isVowel = lambda i: s[i] in vowels
 
while right < n:
# Expansion
while right < n and right - left < k:
count += isVowel(right)
right += 1
# Logic
maxi = max(maxi, count)
# Shrinking
count -= isVowel(left)
left += 1
return maxi

Count - Math​

1550. Three Consecutive Odds​

Easy·
Explanation

Determine if arr contains three consecutive odd numbers. A fixed window of size k = 3 slides across the array, maintaining a count of odd numbers. If the count equals k, three consecutive odds are found.

Expansion:

  • Advance right, incrementing odds for each odd number until the window reaches size 3.

Logic:

  • If odds == k, return True.

Shrinking:

  • Decrement odds if the leftmost number is odd, then advance left.
Analysis
Time
O(n)
  • n is the length of arr - left and right each advance at most n times across the run, so the array is scanned once.
Space
O(1)
  • Only left, right, and odds are tracked, regardless of array length.
FIG. 1550 THREE CONSECUTIVE ODDS● INTERACTIVE
visualization loads as you reach it
class Solution:
def threeConsecutiveOdds(self, arr: List[int]) -> bool:
n, k = len(arr), 3
left = right = 0
odds = 0
 
isOdd = lambda i: arr[i] % 2
 
while right < n:
# Expansion
while right < n and right - left < k:
odds += isOdd(right)
right += 1
# Logic
if odds == k:
return True
# Shrinking
odds -= isOdd(left)
left += 1
return False

2269. Find the K-Beauty of a Number​

Easy·
Explanation

Count how many substrings of length k within num are divisors of num. A fixed window of size k slides across the digits, building the sub-number by appending digits during expansion and trimming via modulo during shrinking. Digits are extracted by converting num to a digits list using [int(d) for d in str(num)].

Expansion:

  • Append digits[right] to sub_num by computing sub_num = sub_num * 10 + digits[right].

Logic:

  • isDivisible checks if sub_num != 0 and num % sub_num == 0. If so, increment ans.

Shrinking:

  • sub_num = sub_num % (10 ** (k - 1)) removes the leftmost digit.
Analysis
Time
O(N)
  • N is the number of digits in num. Each digit is processed once.
Space
O(1)
  • Digits are extracted directly via arithmetic; no array allocation needed.
FIG. 2269 FIND THE K BEAUTY OF A NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def divisorSubstrings(self, num: int, k: int) -> int:
n = int(math.log10(num)) + 1
left = right = 0
ans = sub_num = 0
 
isDivisible = lambda: int(num) % sub_num == 0 if sub_num != 0 else 0
 
while right < n:
# Expansion
while right < n and right - left < k:
power = 10 ** (n - right - 1)
digit = (num // power) % 10
sub_num = sub_num * 10 + digit
right += 1
# Logic
ans += isDivisible()
# Shrinking
sub_num = sub_num % (10 ** (k - 1))
left += 1
return ans

Count - Swaps​

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

Medium·
Explanation

Find the minimum swaps to group all 1's together. The window size k equals the total count of 1's in the array. The minimum number of zeros within any window of that size equals the minimum swaps needed, since each zero represents a swap.

Expansion:

  • Advance right, counting zeros until the window reaches size k.

Logic:

  • mini = min(mini, zeros) -- the fewest zeros in any window is the answer.

Shrinking:

  • Decrement zeros if the leftmost element is 0, then advance left.
Analysis
Time
O(2n)
  • data.count(1) makes one O(n) pass to find k.
  • The while right < n loop makes a second O(n) pass, since left and right each advance at most n times - n + n collapses to 2n.
Space
O(1)
  • Constant space for tracking zeroes, mini, and the window boundaries.
FIG. 1151 MINIMUM SWAPS TO GROUP ALL 1S TOGETHER● INTERACTIVE
visualization loads as you reach it
class Solution:
def minSwaps(self, data: List[int]) -> int:
n, k = len(data), data.count(1)
left = right = zeroes = 0
mini = n
 
if k == 0:
return 0
 
isZero = lambda i: data[i] == 0
 
while right < n:
# Expansion
while right < n and right - left < k:
zeroes += isZero(right)
right += 1
# Logic
mini = min(mini, zeroes)
# Shrinking
zeroes -= isZero(left)
left += 1
return mini

2134. Minimum Swaps to Group All 1's Together II​

Medium·
Explanation

Extends "1151. Minimum Swaps to Group All 1's Together" to a circular array. n is set to 2 * len(nums) − 1 so right traverses all cyclic starting positions; isZero(i) wraps via nums[i % len(nums)].

Expansion:

  • Advance right, counting zeroes via isZero(right) (wraps with %) until the window reaches size k.

Logic:

  • mini = min(mini, zeroes) - minimum zeroes across all circular windows.

Shrinking:

  • Decrement zeroes via isZero(left), then advance left.
Analysis
Time
O(n)
  • n = 2 * len(nums) - 1, the number of circular starting positions. right advances from 0 to n in the expansion loop and left trails it in the shrink step, so each index is visited once - O(n), still linear in len(nums).
Space
O(1)
  • Only the scalars left, right, zeroes, and mini are tracked; nothing scales with n.
FIG. 2134 MINIMUM SWAPS TO GROUP ALL 1S TOGETHER II● INTERACTIVE
visualization loads as you reach it
class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums) * 2 - 1
k = nums.count(1)
left = right = zeroes = 0
mini = n
 
if k == 0:
return 0
 
isZero = lambda i: nums[i % len(nums)] == 0
 
while right < n:
# Expansion
while right < n and right - left < k:
zeroes += isZero(right)
right += 1
# Logic
mini = min(mini, zeroes)
# Shrinking
zeroes -= isZero(left)
left += 1
return mini

Heap​

239. Sliding Window Maximum​

Hard·
2 Approachesclick to switch
Explanation

Find the maximum value in each sliding window of size k. A max heap stores elements as (value, index), so the heap top is always the largest value. Stale entries that have fallen outside the window are lazily discarded from the top.

Expansion:

  • While the window has fewer than k elements, push (nums[right], right) onto the heap and advance right.

Logic:

  • result.append(heap[0][0]) - the heap top is the current window's maximum (after stale entries are purged).

Shrinking:

  • Advance left, then pop from the top while heap[0][1] < left (the maximum has left the window).
Analysis
Time
O(N log N)
  • Each of the N elements is pushed onto heap exactly once via heappush_max, and popped at most once via heappop_max; but stale entries buried below the top are only removed once they bubble up to become the max, so heap can hold up to N entries, making each push/pop O(log N).
Space
O(N)
  • heap can grow to hold up to N entries, since a stale (out-of-window) entry is only cleaned up once it reaches the top; result holds N - k + 1 values, which does not exceed N.
FIG. 239 SLIDING WINDOW MAXIMUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
heap = [] # Max heap
result = []
 
while right < n:
# Expansion: Add new elements to the heap
while right < n and right - left < k:
heapq.heappush_max(heap, (nums[right], right))
right += 1
# Logic: Append the current maximum to ans
result.append(heap[0][0])
left += 1
# Shrinking: Ensure the top of the heap is within the current window
while heap and heap[0][1] < left:
heapq.heappop_max(heap)
return result

Deque​

First negative in every window of size k​

Medium·
Explanation

For each window of size k, report the first negative integer, or 0 if the window has none. A deque holds (index, value) pairs for the negatives currently inside the window, in order of arrival, so negatives[0] is always the earliest negative still in the window.

Expansion:

  • Advance right until the window reaches size k, appending (right, arr[right]) to the deque whenever arr[right] < 0.

Logic:

  • negatives[0][1] is the first negative in the window; append it to result, or 0 if the deque is empty.

Shrinking:

  • If the front's index equals left, that negative is leaving the window - pop it from the front. Increment left.
Analysis
Time
O(n)
  • n = len(arr). Each index is appended to and popped from negatives at most once, and right/left each advance across the array once - a single O(n) pass.
Space
O(k + n)
  • negatives holds at most k entries, one per negative currently in the window.
  • result holds one entry per window, n - k + 1 in total - O(n).
FIG. FIRST NEG INT● INTERACTIVE
visualization loads as you reach it
import collections
 
 
class Solution:
def firstNegInt(self, arr, k):
n = len(arr)
left = right = 0
negatives = collections.deque()
result = []
while right < n:
while right < n and right - left < k:
if arr[right] < 0:
negatives.append((right, arr[right]))
right += 1
result.append(negatives[0][1] if negatives else 0)
if negatives and negatives[0][0] == left:
negatives.popleft()
left += 1
return result

Sorting​

1984. Minimum Difference Between Highest and Lowest of K Scores​

Easy·
Explanation

Find the minimum difference between the highest and lowest scores in any subset of k scores. After sorting, the problem reduces to finding the smallest window of size k where nums[right-1] - nums[left] is minimized.

Expansion:

  • Advance right until the window reaches size k. No running total needed since the array is sorted.

Logic:

  • mini = min(mini, nums[right - 1] - nums[left]) -- the difference between the window's endpoints.

Shrinking:

  • Advance left to slide the window forward.
Analysis
Time
O(n + n log n)
  • A single O(n) sliding-window pass, plus O(n log n) to sort nums first - n + n log n.
Space
O(sort)
  • left, right, and mini are scalars; the only space beyond the input is the sort's own working memory.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 1984 MINIMUM DIFFERENCE BETWEEN HIGHEST AND LOWEST OF K SCORES● INTERACTIVE
visualization loads as you reach it
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
left = right = 0
mini = float("inf")
 
while right < n:
# Expansion
while right < n and right - left < k:
right += 1
# Logic
mini = min(mini, nums[right - 1] - nums[left])
# Shrinking
left += 1
return mini

Bit Manipulation​

3023. Find Pattern in Infinite Stream I​

Medium·
Explanation

Find the starting index of a binary pattern within an infinite stream of bits. The pattern is converted to an integer pattern_num. A sliding window of bit-length k maintains the current sequence as an integer stream_num, built by left-shifting and appending each new bit. mask = 1 << (k - 1) is precomputed to isolate the most significant bit of the window.

Expansion:

  • stream_num = stream_num << 1 | stream.next() -- shift left and append the next bit until the window reaches k bits.

Logic:

  • If stream_num == pattern_num, return left as the starting index.

Shrinking:

  • Remove the most significant bit: stream_num = (stream_num | mask) ^ mask. This sidesteps Python's two's complement behavior compared to & ~mask.
Analysis
Time
O(N)
  • Linear in the number of bits read until the pattern is found.
Space
O(1)
  • Constant number of integer variables.
FIG. 3023 FIND PATTERN IN INFINITE STREAM I● INTERACTIVE
visualization loads as you reach it
# Definition for an infinite stream.
# class InfiniteStream:
# def next(self) -> int:
# pass
class Solution:
def findPattern(
self, stream: Optional["InfiniteStream"], pattern: List[int]
) -> int:
k = len(pattern)
left = right = 0
pattern_num = 0
for num in pattern:
pattern_num = pattern_num << 1 | num
stream_num = 0
mask = 1 << (k - 1)
while True:
# Expansion
while right - left < k:
stream_num = stream_num << 1 | stream.next()
right += 1
# Logic
if pattern_num == stream_num:
return left
# Shrinking: Trim the left most (most significant) bit
# stream_num = stream_num & ~(mask) # Approach 1 - industry standard
# Approach 2 - sidesteps Python's negative number/two's complement behavior
stream_num = (stream_num | mask) ^ mask
left += 1
return 0

3037. Find Pattern in Infinite Stream II​

Hard·
Explanation

Same solution as "3023. Find Pattern in Infinite Stream I" but with a larger constraint: 1 <= pattern.length <= 10000 instead of 1 <= pattern.length <= 100. mask = 1 << (k - 1) is precomputed before the loop, and stream_num = (stream_num | mask) ^ mask sidesteps Python's two's complement behavior compared to & ~mask.

Analysis
Time
O(k + n)
  • Building pattern_num is a single O(k) pass over pattern (k = len(pattern)).
  • The window then reads at most O(n) elements from stream before finding the match, each processed in O(1) via the mask.
Space
O(1)
  • Only scalar bitmask variables (pattern_num, stream_num, mask) are tracked; no structure scales with k or n.
FIG. 3037 FIND PATTERN IN INFINITE STREAM II● INTERACTIVE
visualization loads as you reach it
# Definition for an infinite stream.
# class InfiniteStream:
# def next(self) -> int:
# pass
class Solution:
def findPattern(
self, stream: Optional["InfiniteStream"], pattern: List[int]
) -> int:
k = len(pattern)
left = right = 0
pattern_num = 0
for num in pattern:
pattern_num = pattern_num << 1 | num
stream_num = 0
mask = 1 << (k - 1)
while True:
# Expansion
while right - left < k:
stream_num = stream_num << 1 | stream.next()
right += 1
# Logic
if pattern_num == stream_num:
return left
# Shrinking: Trim the left most (most significant) bit
# stream_num = stream_num & ~(mask) # Approach 1 - industry standard
# Approach 2 - sidesteps Python's negative number/two's complement behavior
stream_num = (stream_num | mask) ^ mask
left += 1
return 0

Miscellaneous​

30. Substring with Concatenation of All Words​

Hard·
Explanation

Find all starting indices in s where a substring is the exact concatenation of all words. The window size is k = len(words) * word_len. A needed counter tracks word frequencies. The window expands by examining word-length segments and shrinks by word-length steps.

Multiple starting offsets (0 to word_len - 1) are tried to cover all possible alignments.

Expansion:

  • Extract word = s[right:right+word_len], decrement its count in needed. Remove the entry if it reaches zero.

Logic:

  • If needed is empty, all words are matched. Append left to ans.

Shrinking:

  • Re-add the leftmost word to needed and advance left by word_len.
Analysis
Time
O(w * (M + n))
  • w is the length of each word. For each of the w starting offsets, building Counter(words) costs O(M) (M = total characters across all words), and sliding left/right across s (length n) in w-sized steps costs O(n).
Space
O(M + n)
  • counter holds entries proportional to total word length M, and result could hold up to n indices.
FIG. 30 SUBSTRING WITH CONCATENATION OF ALL WORDS● INTERACTIVE
visualization loads as you reach it
class Counter:
def __init__(self, iterable=""):
self.counter = {}
self.distinct = 0
for item in iterable:
self[item] += 1
 
def __getitem__(self, key):
return self.counter.get(key, 0)
 
def __setitem__(self, key, value):
old_value = self.counter.get(key, 0)
self.counter[key] = value
if old_value > 0 and value <= 0:
self.distinct -= 1
elif old_value <= 0 and value > 0:
self.distinct += 1
 
def distinct_count(self):
return self.distinct
 
 
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
n = len(s)
w = len(words[0])
k = w * len(words)
result = []
for i in range(w):
left = right = i
counter = Counter(words)
while right < n:
while right < n and right - left < k:
counter[s[right : right + w]] -= 1
right += w
if counter.distinct_count() == 0:
result.append(left)
counter[s[left : left + w]] += 1
left += w
return result