Return Count, Indices
Naive Sum/Average
while expand + while shrink
Indexes of Subarray Sum
Medium·
Solutions:
Visualize
class Solution:
def subarraySum(self, arr, target):
n = len(arr)
left = right = 0
total = 0
isUnderTarget = lambda: total < target
while right < n:
# Expansion
while right < n and isUnderTarget():
total += arr[right]
right += 1
# Shrinking
while left < right and not isUnderTarget():
# Logic
if total == target:
return [left + 1, right]
total -= arr[left]
left += 1
return [-1]
At Most K
while shrink
Distinct Values Subarrays II
Medium·
Solutions:
Visualize
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 atMostKDistinct(self, s: str, k: int) -> int:
def atMost(k):
n = len(s)
left = right = 0
counter = Counter()
result = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
result += right - left
return result
return atMost(k)
3258. Count Substrings That Satisfy K-Constraint I
Easy·
Solutions:
Visualize
class Solution:
def countKConstraintSubstrings(self, s: str, k: int) -> int:
def atMost(k):
n = len(s)
left = right = 0
zeros = ones = 0
result = 0
isZero = lambda i: s[i] == "0"
isValid = lambda: zeros <= k or ones <= k
while right < n:
# Expansion
zeros += isZero(right)
ones += not isZero(right)
right += 1
# Shrinking
while left < right and not isValid():
zeros -= isZero(left)
ones -= not isZero(left)
left += 1
# Logic
print(left, right, result)
result += right - left
return result
return atMost(k)
Less Than K (using atMost)
Idea: LessThan(k) = AtMost(k - 1)
while shrink
1513. Number of Substrings With Only 1s
Medium·
Solutions:
Visualize
class Solution:
def numSub(self, s: str) -> int:
def atMost(k):
n = len(s)
left = right = 0
count = 0
zeroes = 0
while right < n:
# Expansion
zeroes += s[right] == "0"
right += 1
# Shrinking
while left < right and zeroes > k:
zeroes -= s[left] == "0"
left += 1
# Logic
count += right - left
return count
return atMost(0) % (10**9 + 7)
1759. Count Number of Homogenous Substrings
Medium·
Solutions:
Visualize
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 countHomogenous(self, s: str) -> int:
def atMost(k):
n = len(s)
left = right = 0
count = 0
counter = Counter()
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
count += right - left
return count
return atMost(1) % (10**9 + 7)
2743. Count Substrings Without Repeating Character
Medium·
Solutions:
Visualize
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 numberOfSpecialSubstrings(self, s: str) -> int:
def atMost(k):
n = len(s)
left = right = 0
counter = Counter()
result = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter[s[right - 1]] > k:
counter[s[left]] -= 1
left += 1
# Logic
result += right - left
return result
return atMost(1)
713. Subarray Product Less Than K
Medium·
Solutions:
Visualize
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
prod = 1
count = 0
while right < n:
# Expansion
prod *= nums[right]
right += 1
# Shrinking
while left < right and prod > k:
prod //= nums[left]
left += 1
# Logic
count += right - left
return count
return atMost(k - 1)
2302. Count Subarrays With Score Less Than K
Hard·
Solutions:
Visualize
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
total = 0
count = 0
score = lambda: total * (right - left)
while right < n:
# Expansion
total += nums[right]
right += 1
# Shrinking
while left < right and score() > k:
total -= nums[left]
left += 1
# Logic
count += right - left
return count
return atMost(k - 1)
Exactly K (using atMost)
Idea: Exactly(k) = AtMost(k) - AtMost(k - 1)
while shrink
930. Binary Subarrays With Sum
Medium·
Solutions:
Visualize
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
total = count = 0
while right < n:
# Expansion
total += nums[right]
right += 1
# Shrinking
while left < right and total > k:
total -= nums[left]
left += 1
# Logic
count += right - left
return count
return atMost(goal) - atMost(goal - 1)
1248. Count Number of Nice Subarrays
Medium·
Solutions:
Visualize
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
odds = count = 0
isOdd = lambda i: int(nums[i] % 2 == 1)
while right < n:
# Expansion
odds += isOdd(right)
right += 1
# Shrinking
while left < right and odds > k:
odds -= isOdd(left)
left += 1
# Logic
count += right - left
return count
return atMost(k) - atMost(k - 1)
1358. Number of Substrings Containing All Three Characters
Medium·
Solutions:
Visualize
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 numberOfSubstrings(self, s: str) -> int:
def atMost(k):
n = len(s)
left = right = 0
counter = Counter()
count = 0
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[s[left]] -= 1
left += 1
# Logic
count += right - left
return count
k = 3
return atMost(k) - atMost(k - 1)
2799. Count Complete Subarrays in an Array
Medium·
Solutions:
Visualize
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 countCompleteSubarrays(self, nums: List[int]) -> int:
def atMost(k):
n = len(nums)
left = right = 0
counter = Counter()
count = 0
while right < n:
# Expansion
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[nums[left]] -= 1
left += 1
# Logic
count += right - left
return count
k = len(set(nums))
return atMost(k) - atMost(k - 1)
992. Subarrays with K Different Integers
Solutions:
Visualize
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 subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
counter = Counter()
count = 0
while right < n:
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and counter.distinct_count() > k:
counter[nums[left]] -= 1
left += 1
# Logic
count += right - left
return count
return atMost(k) - atMost(k - 1)
At Least K (using atMost)
Idea: AtLeast(k) = Total - AtMost(k - 1)
while shrink
2537. Count the Number of Good Subarrays
Medium·
Solutions:
Visualize
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
def atMost(k):
left = right = 0
counter = collections.Counter()
result = count = 0
while right < n:
# Expansion
count += counter[nums[right]]
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and count > k:
counter[nums[left]] -= 1
count -= counter[nums[left]]
left += 1
# Logic
result += right - left
return result
n = len(nums)
total_subarrays = (n * (n + 1)) // 2
return total_subarrays - atMost(k - 1)
2962. Count Subarrays Where Max Element Appears at Least K Times
Medium·
Solutions:
Visualize
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
def atMost(k):
left = right = 0
counter = collections.Counter()
result = 0
max_element = max(nums)
while right < n:
# Expansion
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and counter[max_element] > k:
counter[nums[left]] -= 1
left += 1
# Logic
result += right - left
return result
n = len(nums)
total_subarrays = (n * (n + 1)) // 2
return total_subarrays - atMost(k - 1)