Skip to main content

Fixed Window

while expand

Naïve Sum/Average​

Max Sum Subarray of size K​

Max Sum Subarray of size K

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

643. Maximum Average Subarray I

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

2090. K Radius Subarray Averages

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

1176. Diet Plan Performance

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

1052. Grumpy Bookstore Owner

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

1652. Defuse the Bomb

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

187. Repeated DNA Sequences

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

219. Contains Duplicate II

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

217. Contains Duplicate

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

1852. Distinct Numbers in Each Subarray

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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

Hashmap - Anagrams/Permutations​

438. Find All Anagrams in a String​

438. Find All Anagrams in a String

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

242. Valid Anagram

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

567. Permutation in String

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

1550. Three Consecutive Odds

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

2269. Find the K-Beauty of a Number

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

239. Sliding Window Maximum

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
heap = [] # Max heap: elements stored as (-value, index)
result = []
 
while right < n:
# Expansion: Add new elements to the heap
while right < n and right - left < k:
heapq.heappush(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(heap)
return result

Sorting​

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

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

3023. Find Pattern in Infinite Stream I

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

# 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​

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

# 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​

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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