Skip to main content

Return Count, Indices

Naive Sum/Average​

while expand + while shrink

Indexes of Subarray Sum​

Medium·
Solutions:
FIG. INDEXES SUBARRAY SUM● INTERACTIVE
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:
FIG. 2428 DISTINCT VALUES SUBARRAYS II● INTERACTIVE
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:
FIG. 3258 COUNT SUBSTRINGS THAT SATISFY K CONSTRAINT I● INTERACTIVE
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:
FIG. 1513 NUMBER OF SUBSTRINGS WITH ONLY 1S● INTERACTIVE
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:
FIG. 1759 COUNT NUMBER OF HOMOGENOUS SUBSTRINGS● INTERACTIVE
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:
FIG. 2743 COUNT SUBSTRINGS WITHOUT REPEATING CHARACTER● INTERACTIVE
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:
FIG. 713 SUBARRAY PRODUCT LESS THAN K● INTERACTIVE
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:
FIG. 2302 COUNT SUBARRAYS WITH SCORE LESS THAN K● INTERACTIVE
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:
FIG. 930 BINARY SUBARRAYS WITH SUM● INTERACTIVE
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:
FIG. 1248 COUNT NUMBER OF NICE SUBARRAYS● INTERACTIVE
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:
FIG. 1358 NUMBER OF SUBSTRINGS CONTAINING ALL THREE CHARACTERS● INTERACTIVE
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:
FIG. 2799 COUNT COMPLETE SUBARRAYS IN AN ARRAY● INTERACTIVE
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​

Hard·
Solutions:
FIG. 992 SUBARRAYS WITH K DIFFERENT INTEGERS● INTERACTIVE
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:
FIG. 2537 COUNT THE NUMBER OF GOOD SUBARRAYS● INTERACTIVE
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:
FIG. 2962 COUNT SUBARRAYS WHERE MAX ELEMENT APPEARS AT LEAST K TIMES● INTERACTIVE
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)