Skip to main content

Fixed Window

while expand

Naïve Sum/Average​

Max Sum Subarray of size K​

Easy·
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·
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·
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·
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·
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·
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·
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·
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·
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·
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·
4 Approaches · 2 patterns
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·
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·
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·
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·
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·
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·
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·
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·
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·
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·
3 Approaches · 2 patterns
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·
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·
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·
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·
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·
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·
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·
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 Approaches
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·
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·
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·
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·
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·
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