Skip to main content

Return Count, Indices

Naive Sum/Average​

while expand + while shrink

Indexes of Subarray Sum​

Indexes of Subarray Sum

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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]

Longest Substring - Depends on prev​

while expand + rapid shrink

1759. Count Number of Homogenous Substrings​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def countHomogenous(self, s: str) -> int:
n = len(s)
left = right = 0
count = 0
prev = None
 
isHomogeneous = lambda i: s[i] == prev
naturalSum = lambda i: i * (i + 1) // 2
 
while right < n:
# Expansion
while right < n and isHomogeneous(right):
prev = s[right]
right += 1
# Logic
count += naturalSum(right - left)
# Shrinking
prev = s[right] if right < n else None
left = right
 
return count % (10**9 + 7)

1513. Number of Substrings With Only 1s​

1513. Number of Substrings With Only 1s

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def numSub(self, s: str) -> int:
n = len(s)
left = right = 0
prev = None
result = 0
 
isHomogeneous = lambda i: prev == s[i]
naturalSum = lambda i: i * (i + 1) // 2
 
while right < n:
# Expansion
while right < n and isHomogeneous(right):
prev = s[right]
right += 1
# Logic
if prev == "1":
result += naturalSum(right - left)
# Shrinking
prev = s[right] if right < n else None
left = right
return result % (10**9 + 7)

Less Than K (using atMost)​

Idea: LessThan(k) = AtMost(k - 1)

while shrink

713. Subarray Product Less Than K​

713. Subarray Product Less Than K

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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​

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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

1248. Count Number of Nice Subarrays​

1248. Count Number of Nice Subarrays

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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)

992. Subarrays with K Different Integers​

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def atMost(k):
n = len(nums)
left = right = 0
counter = collections.Counter()
count = 0
while right < n:
# Expansion
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and len(counter) > k:
counter[nums[left]] -= 1
if counter[nums[left]] == 0:
counter.pop(nums[left])
left += 1
# Logic
count += right - left
return count
 
return atMost(k) - atMost(k - 1)

930. Binary Subarrays With Sum​

930. Binary Subarrays With Sum

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

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)

1358. Number of Substrings Containing All Three Characters​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def numberOfSubstrings(self, s: str) -> int:
n = len(s)
left = right = 0
hm = {i: 0 for i in "abc"}
ans = 0
while right < n:
# Expansion
hm[s[right]] += 1
right += 1
# Shrinking
while left < right and all(hm.values()):
# Logic
ans += n - right + 1
hm[s[left]] -= 1
left += 1
return ans

2799. Count Complete Subarrays in an Array​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
n = len(nums)
k = len(set(nums))
left = right = 0
counter = collections.Counter()
count = 0
 
while right < n:
# Expansion
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and len(counter) >= k:
# Logic
count += n - right + 1
counter[nums[left]] -= 1
if counter[nums[left]] == 0:
counter.pop(nums[left])
left += 1
return count

2743. Count Substrings Without Repeating Character​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def numberOfSpecialSubstrings(self, s: str) -> int:
n = len(s)
k = 1
left = right = 0
count = 0
counter = collections.Counter()
while right < n:
# Expansion
counter[s[right]] += 1
right += 1
# Shrinking
while left < right and counter[s[right - 1]] > k:
counter[s[left]] -= 1
if counter[s[left]] == 0:
counter.pop(s[left])
left += 1
# Logic
count += right - left
return count

Exactly K (without atMost)​

2537. Count the Number of Good Subarrays​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def countGood(self, nums: List[int], k: int) -> int:
n = len(nums)
left = right = 0
counter = collections.Counter()
pairs = ans = 0
 
pair_formula = lambda i: i * (i - 1) // 2
get_available_pairs = lambda i: pair_formula(i) - pair_formula(i - 1)
 
while right < n:
# Expansion
counter[nums[right]] += 1
pairs += get_available_pairs(counter[nums[right]])
right += 1
# Shrinking
while left < right and pairs >= k:
# Logic
ans += n - right + 1
pairs -= get_available_pairs(counter[nums[left]])
counter[nums[left]] -= 1
left += 1
 
return ans

2962. Count Subarrays Where Max Element Appears at Least K Times​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
left = right = 0
max_ele = max(nums)
counter = collections.Counter()
count = 0
while right < n:
# Expansion
counter[nums[right]] += 1
right += 1
# Shrinking
while left < right and counter[max_ele] >= k:
# Logic
count += n - right + 1
counter[nums[left]] -= 1
left += 1
return count