Skip to main content

Return Count, Indices

Naive Sum/Average​

while expand + while shrink

Indexes of Subarray Sum​

Medium·
Explanation

Find a contiguous subarray whose sum equals a given target s. The window expands to accumulate a greater total and shrinks to shed excess value.

Edge case: if s is zero, check for the presence of a zero in the array directly.

Analysis
Time
O(N)
  • Each element is considered at most twice.
Space
O(1)
  • A fixed number of variables.
FIG. INDEXES SUBARRAY SUM● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Count subarrays with at most k distinct values. The atMost(k) helper expands the right edge, shrinks from the left whenever the distinct count exceeds k, and adds right - left (the number of valid subarrays ending at right) at every step.

Analysis
Time
O(n)
  • n is the length of s - left and right each advance at most n times inside atMost, so every element enters and leaves the window once.
Space
O(k)
  • counter is shrunk whenever its distinct count exceeds k, so it holds at most k distinct elements.
FIG. 2428 DISTINCT VALUES SUBARRAYS II● 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 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·
Explanation

A substring satisfies the k-constraint when its number of 0s is at most k or its number of 1s is at most k. A substring violates it only when both counts exceed k, and that violation never disappears as the window grows, so the valid substrings form a contiguous at most window.

atMost(k) expands right, then shrinks from the left while isValid() is false (both zeros > k and ones > k). Each step adds right - left, the number of valid substrings ending at right.

Analysis
Time
O(N)
  • Each character enters and leaves the window once across the single pass.
Space
O(1)
  • Only two running counts (zeros, ones) are tracked.
FIG. 3258 COUNT SUBSTRINGS THAT SATISFY K CONSTRAINT I● INTERACTIVE
visualization loads as you reach it
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·
Explanation

A substring of only '1's is one that contains exactly zero '0' characters. That makes it a degenerate exactly-k case with k = 0: since atMost(-1) = 0, exactly(0) = atMost(0), so the helper returns the answer directly.

atMost(0) is a standard sliding window: expand right, and while the window holds more than 0 zeroes, shrink from the left. Each step contributes right - left substrings. Take the result mod 10**9 + 7.

Analysis
Time
O(N)
  • N is the length of s. left and right in atMost each advance at most N times, so the window scan is a single O(N) pass.
Space
O(1)
  • Only scalars (left, right, count, zeroes) are tracked - no structure scales with N.
FIG. 1513 NUMBER OF SUBSTRINGS WITH ONLY 1S● INTERACTIVE
visualization loads as you reach it
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·
Explanation

A homogenous substring contains only one unique character - that is at most 1 distinct character. This is the degenerate exactly-k case with k = 1: since atMost(0) = 0, exactly(1) = atMost(1), so the helper returns the answer directly.

atMost(k) is a standard sliding window over distinct count: expand right, and while the window holds more than k distinct characters, shrink from the left. Each step contributes right - left substrings. Take the result mod 10**9 + 7.

Analysis
Time
O(N)
  • atMost(1) runs once, and within it right and left each advance across s exactly once, so every character is added and removed from counter once.
Space
O(1)
  • counter holds one entry per distinct character seen, bounded by the fixed alphabet regardless of N.
FIG. 1759 COUNT NUMBER OF HOMOGENOUS SUBSTRINGS● 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 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·
2 Approachesclick to switch
Explanation

"Each character appears at most once" is already an at most constraint, so the answer is atMost(1) directly - no complement subtraction is needed (unlike the "at least k" problems in this section).

atMost(k) expands right, then shrinks from the left while the just-added character's frequency exceeds k. Each step contributes right - left valid substrings.

Analysis
Time
O(N)
  • Single pass through the string.
Space
O(26)
  • s consists of lowercase English letters.
FIG. 2743 COUNT SUBSTRINGS WITHOUT REPEATING CHARACTER● 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 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·
Explanation

Count the number of contiguous subarrays where the product of all elements is less than k. Using the fact that less than k equals at most k-1, we use an atMost helper.

For each valid window, the number of new subarrays introduced by adding the latest element is right - left.

Analysis
Time
O(N)
  • Single pass with the sliding window.
Space
O(1)
  • A minimal number of variables.
FIG. 713 SUBARRAY PRODUCT LESS THAN K● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Count contiguous subarrays where the score (sum * length) is less than k. Uses the same atMost pattern, with score = total * (right - left).

Analysis
Time
O(n)
  • Single pass through nums (length n); left and right each advance at most n steps.
Space
O(1)
  • A minimal number of variables.
FIG. 2302 COUNT SUBARRAYS WITH SCORE LESS THAN K● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Count contiguous subarrays within a binary array that sum to a given goal. Using: exactly(goal) = atMost(goal) - atMost(goal - 1).

Analysis
Time
O(2n)
  • atMost is called twice, and each call is a single O(n) sliding-window pass over nums - 2n.
Space
O(1)
  • Only left, right, total, and count are tracked per call.
FIG. 930 BINARY SUBARRAYS WITH SUM● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Count all subarrays that contain exactly k odd numbers. Using the equation: exactly(k) = atMost(k) - atMost(k - 1).

The atMost(k) helper counts subarrays with at most k odd numbers using a standard sliding window.

Analysis
Time
O(2n)
  • atMost(k) runs a sliding window where right and left each only advance forward across the array: O(n), where n = len(nums).
  • atMost(k) - atMost(k - 1) calls that same O(n) window twice, so total is O(2n).
Space
O(1)
  • Only scalars (left, right, odds, count) are tracked, no structure grows with n.
FIG. 1248 COUNT NUMBER OF NICE SUBARRAYS● INTERACTIVE
visualization loads as you reach it
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·
2 Approachesclick to switch
Explanation

Count substrings that contain at least one of each character 'a', 'b', and 'c'. With exactly 3 distinct characters required, this becomes atMost(3) - atMost(2), where atMost(k) counts substrings with at most k distinct characters.

Analysis
Time
O(2N)
  • atMost(k) is an O(n) sliding-window pass, and it's called twice - atMost(3) and atMost(2) - for 2n.
Space
O(1)
  • counter holds at most 3 distinct characters ('a', 'b', 'c'), independent of n.
FIG. 1358 NUMBER OF SUBSTRINGS CONTAINING ALL THREE 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 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·
2 Approachesclick to switch
Explanation

A "complete" subarray contains all k = len(set(nums)) distinct values - that is exactly k distinct values, since a window can never hold more. So this is an exactly-k problem: exactly(k) = atMost(k) - atMost(k - 1).

atMost(k) is a standard sliding window over distinct count: expand right, and while the window holds more than k distinct values, shrink from the left. Each step contributes right - left subarrays.

Analysis
Time
O(2N)
  • Two passes through the array, one for each call to atMost.
Space
O(K)
  • The counter's size is bounded by k, the number of unique elements.
FIG. 2799 COUNT COMPLETE SUBARRAYS IN AN ARRAY● 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 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·
Explanation

Count subarrays with exactly k different integers. Using: exactly(k) = atMost(k) - atMost(k - 1).

The atMost(k) helper counts subarrays with at most k distinct integers.

Analysis
Time
O(2N)
  • Two passes through the array.
Space
O(K)
  • The counter holds up to k distinct elements.
FIG. 992 SUBARRAYS WITH K DIFFERENT INTEGERS● 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 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·
Explanation

A subarray is "good" if it has at least k pairs of equal elements. Counting "at least" directly is awkward, so flip it: count subarrays with at most k - 1 pairs and subtract from the total number of subarrays.

atMost(k) is a standard sliding window. When nums[right] enters, it forms one new pair with every equal element already inside the window - that is exactly the current count of nums[right] (read before incrementing). Shrink from the left while count > k. Every step, each window ending at right contributes right - left new subarrays.

The total subarray count is n * (n + 1) / 2, so the answer is total - atMost(k - 1).

Analysis
Time
O(N)
  • Single pass through the array.
Space
O(N)
  • The counter could contain an entry for every unique element.
FIG. 2537 COUNT THE NUMBER OF GOOD SUBARRAYS● INTERACTIVE
visualization loads as you reach it
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·
Explanation

We want subarrays where the maximum element appears at least k times. "At least" is awkward to count directly, so flip it: count subarrays where the max appears at most k - 1 times and subtract from the total number of subarrays.

atMost(k) is a standard sliding window. Expand right, and whenever the window holds more than k copies of max_element, shrink from the left until it is valid again. Every step, each window ending at right contributes right - left subarrays.

The total subarray count is n * (n + 1) / 2, so the answer is total - atMost(k - 1).

Analysis
Time
O(N)
  • Single pass through the array.
Space
O(N)
  • The counter tracks element frequencies.
FIG. 2962 COUNT SUBARRAYS WHERE MAX ELEMENT APPEARS AT LEAST K TIMES● INTERACTIVE
visualization loads as you reach it
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)