Return Count, Indices

Naive Sum/Average

while expand + while shrink

Indexes of Subarray Sum

Medium·

Indexes of Subarray Sum

Sliding Window

O(2N) timeO(1) aux

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·

Distinct Values Subarrays II

Sliding Window

O(2N) timeO(k) aux

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·

3258Count Substrings That Satisfy K-Constraint I

Sliding Window

O(2N) timeO(1) aux

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·

1513Number of Substrings With Only 1s

Sliding Window

O(2N) timeO(1) aux

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·

1759Count Number of Homogenous Substrings

Sliding Window

O(2N) timeO(2) aux

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·

2743Count Substrings Without Repeating Character

2 Approaches

At Most

O(2N) timeO(26) aux

Optimized

O(2N) timeO(26) aux

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·

713Subarray Product Less Than K

Sliding Window

O(2N) timeO(1) aux

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·

2302Count Subarrays With Score Less Than K

Sliding Window

O(2N) timeO(1) aux

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·

Subarray Sums I

E

930Binary Subarrays With Sum

Sliding Window

O(2N) timeO(1) aux

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·

1248Count Number of Nice Subarrays

Sliding Window

O(2N) timeO(1) aux

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·

1358Number of Substrings Containing All Three Characters

2 Approaches

At Most

O(2N) timeO(3) aux

Optimized

O(2N) timeO(1) aux

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·

2799Count Complete Subarrays in an Array

2 Approaches

At Most

O(2N) timeO(K) aux

Optimized

O(2N) timeO(K) aux

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·

Subarrays with K Distinct Integers

M

992Subarrays with K Different Integers

Sliding Window

O(2N) timeO(K) aux

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·

2537Count the Number of Good Subarrays

Sliding Window

O(2N) timeO(N) aux

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·

2962Count Subarrays Where Max Element Appears at Least K Times

Sliding Window

O(2N) timeO(N) aux

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)

---