Return Count,Indices

Prospect

• https://leetcode.com/problems/number-of-equal-count-substrings

• 1. Count Vowel Substrings of a String

Naive Sum/Average

while expand + while shrink

Indexes of Subarray Sum (Medium)

Solution

This problem requires identifying a contiguous subarray within an array arr whose sum equals a given target s. The solution utilizes a sliding window approach to dynamically adjust the considered subarray, increasing its size to accumulate a greater total or decreasing it to shed excess value, aiming to match the target sum exactly.

An edge case is handled upfront: if the target sum s is zero, the solution checks for the presence of a zero in the array and returns its position as both the start and end of the subarray. If no such subarray exists, it returns -1.

Expansion:

• The window expands by incrementing the right pointer, increasing total with each included element, until total is greater than or equal to s.

Shrinking:

• If total exceeds s, the window shrinks from the left by incrementing the left pointer and decrementing total accordingly, attempting to reduce the total sum without falling below the target.

Logic:

• If at any point total equals s, the current window (delimited by left and right) represents a valid subarray. The function then returns the 1-based indices of the start and end of this subarray.

The function subArraySum iterates through arr, adjusting the window size as described, and returns the positions of the start and end of the subarray meeting the target sum, if such a subarray exists.

Analysis

Time Complexity: O(N)

• The sliding window approach ensures that each element of arr is considered at most twice (once when added to total and once when removed), leading to linear time complexity over the array length n.

Space Complexity: O(1)

• Constant space is utilized, as the solution employs a fixed number of variables (left, right, total) to manage the window’s boundaries and compute the total sum within it, independent of the input array’s size.

Python

def subArraySum(self, arr, n, s):
    left = right = 0
    total = 0
    if s == 0:
        if 0 in arr:
            ind = arr.index(0)
            return [ind + 1, ind + 1]
        else:
            return [-1]
    while right < n:
        while right < n and total < s:
            total += arr[right]
            right += 1
        while left < right and total > s:
            total -= arr[left]
            left += 1
        if total == s:
            return [left + 1, right]
    return [left + 1, right] if total == s else [-1]

---

Longest Substring | Depends on prev

while expand + rapid shrink

1759. Count Number of Homogenous Substrings (Medium)

Solution

This problem requires counting the total number of homogenous substrings within a given string s. A homogenous substring is defined as a substring containing only one unique character. The solution employs a sliding window approach, leveraging the mathematical concept of natural sum to calculate the number of possible substrings efficiently.

The sliding window dynamically adjusts to encompass sequences of identical characters. For each such sequence, the number of possible homogenous substrings is determined by the formula for the sum of the first n natural numbers, natural_sum = lambda i: i * (i + 1) // 2, where i is the length of the sequence.

Expansion:

• The window expands by moving the right pointer forward as long as the current character matches the previous one (prev), effectively capturing a homogenous sequence.

Logic:

• Upon encountering a different character or reaching the end of s, calculate the total number of homogenous substrings within the current window using the natural_sum formula and add this to count.

Shrinking:

• Adjust prev to the current character at right, and set left to start from the current right, preparing for the next sequence. Increment right by 1 to avoid infinite loops and ensure progress through s.

An edge case is handled if the last character sequence is homogenous but not counted in the main loop. The solution then returns count modulo 10**9 + 7, as per the problem’s requirement to manage potentially large numbers.

The function countHomogenous computes the total number of homogenous substrings in s, adhering to the constraints and efficiently utilizing the sliding window methodology.

Analysis

Time Complexity: O(N)

• A single pass through the string s is conducted with the sliding window, where each character contributes to at most one sequence calculation. The approach ensures linear time complexity.

Space Complexity: O(1)

• The solution employs a constant amount of space, utilizing a few variables (left, right, count, and prev) to track the progress and compute the total count of substrings.

Python

def countHomogenous(self, s: str) -> int:
    n = len(s)
    left = right = 0
    count = 0
    prev = None

    # Function to calculate the sum of the first n natural numbers
    natural_sum = lambda i: i * (i + 1) // 2

    while right < n:
        # Expansion: Include elements as long as they form a homogenous sequence
        while right < n and s[right] == prev:
            prev = s[right]
            right += 1
        # Logic: Update the count with the total number of homogenous substrings
        count += natural_sum(right - left)
        # Shrinking: Adjust for the next sequence
        prev = s[right] if right < n else None
        left = right
        right += 1

    # Edge case for last single length subsequence
    if prev is not None:
        count += 1

    # Ensure the count is modulo 10**9 + 7
    return count % (10**9 + 7)

1513. Number of Substrings With Only 1s (Medium)

Solution

The challenge is to count the total number of substrings that contain only ‘1’s within a given binary string s. This can be efficiently achieved using a sliding window approach, similar to the methodology applied for counting homogenous substrings, but specifically tailored to identify sequences of ‘1’s.

The solution iterates through s, dynamically adjusting a window to capture sequences of ‘1’s and utilizing the mathematical concept of natural sum to calculate the number of possible substrings for each sequence.

Expansion:

• The window expands by moving the right pointer forward as long as the current character matches the previous one (prev), focusing on sequences of ‘1’s.

Logic:

• Upon encountering a character different from ‘1’ or reaching the end of s, calculate the total number of substrings within the current window of ‘1’s using the natural_sum formula and add this to count.

Shrinking:

• Adjust prev to the current character at right, and set left to start from the current right, preparing for the next sequence. Increment right by 1 to ensure the algorithm progresses and avoids an infinite loop.

The function numSub computes the total number of substrings consisting solely of ‘1’s in s, efficiently utilizing the sliding window technique and the natural sum calculation.

Analysis

Time Complexity: O(N)

• The algorithm performs a single pass through the string s, with each character contributing to at most one sequence calculation. This approach ensures linear time complexity.

Space Complexity: O(1)

• Constant space is required for the solution, as it uses only a few variables (left, right, prev, and count) to manage the window’s boundaries and compute the total count of substrings.

Python

def numSub(self, s: str) -> int:
    n = len(s)
    left = right = 0
    prev = None
    count = 0

    # Function to calculate the sum of the first n natural numbers
    natural_sum = lambda i: i * (i + 1) // 2

    while right < n:
        # Expansion
        while right < n and s[right] == prev:
            prev = s[right]
            right += 1
        # Logic
        if prev == "1":
            count += natural_sum(right - left)
        # Shrinking
        prev = s[right] if right < n else None
        left = right
        right += 1

    # Edge case for last single length subsequence
    if prev is not None:
        count += 1
    return count

---

Less Than K (using atMost)

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

while shrink

713. Subarray Product Less Than K (Medium)

Solution

Well, using the fact that less than k is equal to at most k-1, we can proceed with the solution.

The problem involves counting the number of contiguous subarrays where the product of all the elements in the subarray is less than a given target k. This is addressed using a sliding window approach, focusing on dynamically adjusting the window to include as many elements as possible without exceeding the product threshold.

The primary mechanism for solving this problem is encapsulated in the atMost function, which calculates the number of subarrays with a product strictly less than k.

Expansion:

• The window expands by moving the right pointer forward, multiplying prod by each new element. This continues until the product exceeds k, indicating the need to shrink the window.

Shrinking:

• If prod exceeds or equals k, the window shrinks from the left by incrementing the left pointer and dividing prod by the removed element, attempting to bring the product back under the threshold.

Logic:

• For each valid window, increment count by the number of new subarrays introduced by adding the latest element, which is given by right - left. This captures all unique subarrays ending at the current right index that meet the product condition.

The function numSubarrayProductLessThanK employs the atMost helper with k - 1 to adhere strictly to the “less than” condition, returning the total count of valid subarrays.

Analysis

Time Complexity: O(N)

• The algorithm iterates through the array nums once with the sliding window, expanding and shrinking based on the product of elements within the window. This ensures linear time complexity relative to the length of nums.

Space Complexity: O(1)

• Constant space is utilized, as the solution employs a minimal number of variables (left, right, prod, count) to manage the window’s boundaries and compute the cumulative product within it.

Python

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)

Solution

This problem aims to count the number of contiguous subarrays in an array nums where the score of each subarray is less than a given k. The score of a subarray is defined as the sum of its elements multiplied by the length of the subarray. A sliding window approach is employed to dynamically adjust the considered subarray, increasing its size to accumulate a greater total or decreasing it to reduce the score, aiming to keep the score below the threshold k.

The solution involves a helper function atMost, which calculates the number of subarrays with a score strictly less than k.

Expansion:

• The window expands by incrementing the right pointer, increasing total with each included element, until the score, calculated as total * (right - left), meets or exceeds k.

Shrinking:

• If the score exceeds or equals k, the window shrinks from the left by incrementing the left pointer and adjusting total accordingly, attempting to reduce the score without falling below the target.

Logic:

• After each potential expansion or necessary shrinking, the number of new subarrays introduced by adding the latest element, given by right - left, is added to count. This captures all unique subarrays ending at the current right index that meet the score condition.

The function countSubarrays utilizes the atMost helper with k - 1 to adhere strictly to the “less than” condition, returning the total count of valid subarrays.

Analysis

Time Complexity: O(N)

• The algorithm iterates through the array nums once with the sliding window, expanding and shrinking based on the score of elements within the window. This ensures linear time complexity relative to the length of nums.

Space Complexity: O(1)

• Constant space is utilized, as the solution employs a minimal number of variables (left, right, total, count) to manage the window’s boundaries and compute the cumulative total within it.

Python

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 (Medium)

Solution

The goal is to count all subarrays within nums that contain exactly k odd numbers. This challenge is efficiently tackled using a modified sliding window approach that counts subarrays with at most k odd numbers, then refines the count to those with exactly k by subtracting the number of subarrays with at most k - 1 odd numbers.

First you may have feeling of using sliding window. Then this idea gets stuck in the middle. This problem will be a very typical sliding window, if it asks the number of subarrays with at most goal. But, Just need one more step to reach the following equation: exactly(goal) = atMost(goal) - atMost(goal - 1)

The core idea revolves around a helper function atMost(k), which calculates the number of subarrays with at most k odd numbers. The difference between atMost(k) and atMost(k - 1) yields the count of subarrays with exactly k odd numbers.

Expansion:

• The window expands by moving the right pointer forward, incrementing the odds counter for each odd number encountered.

Shrinking:

• If the number of odd numbers within the window exceeds k, the window shrinks from the left by incrementing the left pointer and adjusting the odds counter accordingly.

Logic:

• For each valid window, increment count by the number of new subarrays introduced by including the latest element, given by right - left. This captures all unique subarrays ending at the current right index that meet the condition.

The function numberOfSubarrays computes the total count of “nice” subarrays by employing the atMost function, returning the difference between counts for k and k - 1 to isolate those with exactly k odd numbers.

Analysis

Time Complexity: O(2N)

• Employing the atMost function involves iterating through the array nums twice, once for each call. Each iteration consists of a single pass with a sliding window, maintaining linear time complexity relative to the length of nums.

Space Complexity: O(1)

• Constant space is used, as the solution leverages a fixed number of variables (left, right, odds, count) to manage the window’s boundaries and compute the cumulative count within it.

Python

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 (Hard)

Solution

The challenge is to count the number of subarrays within an array nums that contain exactly k different integers. This problem is addressed using a modified sliding window approach, focusing on calculating the number of subarrays with at most k different integers, then refining this count to those with exactly k by subtracting the count of subarrays with at most k - 1 different integers.

The core idea involves a helper function atMost(k), which calculates the number of subarrays with at most k different integers. The total count of subarrays with exactly k different integers is obtained by subtracting the count of subarrays with at most k - 1 different integers from those with at most k different integers.

Expansion:

• Expand the window by moving the right pointer forward, updating the counter for each new element included.

Shrinking:

• If the number of different integers within the window exceeds k, shrink the window from the left by decrementing the left pointer and adjusting the counter accordingly.

Logic:

• After ensuring the window contains at most k different integers, calculate the number of new subarrays introduced by including the latest element, given by right - left, and update count.

The function subarraysWithKDistinct employs the atMost function to compute the count of subarrays with exactly k different integers, returning the difference between counts for k and k - 1.

Analysis

Time Complexity: O(2N)

• The solution iterates through the array nums twice, once for each call to atMost. Each iteration involves a single pass through nums with a sliding window, ensuring linear time complexity relative to the length of nums.

Space Complexity: O(K)

• The space complexity is influenced by the counter, which tracks the frequency of elements within the window. In the worst case, the counter could contain an entry for every unique element up to k, indicating the space requirement is proportional to the number of unique elements considered, capped at k.

Python

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 (Medium)

Solution

This problem seeks to count the number of contiguous subarrays within a binary array nums that sum to a given goal. First you may have feeling of using sliding window. Then this idea gets stuck in the middle. This problem will be a very typical sliding window, if it asks the number of subarrays with at most goal. But, Just need one more step to reach the following equation: exactly(goal) = atMost(goal) - atMost(goal - 1)

Expansion:

• The window expands by incrementing the right pointer, adding to total with each included element from nums, until total exceeds k.

Shrinking:

• If total surpasses k, the window shrinks from the left by incrementing the left pointer and adjusting total accordingly, seeking to reduce the total sum back below or equal to k.

Logic:

• For each window that does not exceed k, increment count by the number of new subarrays introduced by including the latest element, given by right - left. This captures all unique subarrays ending at the current right index that meet the sum condition.

The function numSubarraysWithSum computes the count of subarrays summing exactly to goal by employing the atMost function, returning the difference between the counts of subarrays with sums at most goal and those at most goal - 1.

Analysis

Time Complexity: O(N)

• The algorithm iterates through the array nums twice, once for each invocation of atMost. Each iteration involves a single pass through nums with a sliding window, ensuring linear time complexity relative to the length of nums.

Space Complexity: O(1)

• Constant space is utilized, as the solution employs a minimal number of variables (left, right, total, count) to manage the window’s boundaries and compute the cumulative total within it.

Python

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 (Medium)

atMostOptimized

Solution

The objective is to count the number of substrings within a given string s that contain exactly 3 unique characters. This is achieved by employing a modified sliding window approach that counts the number of substrings with at most 3 unique characters and subtracts from it the number of substrings with at most 2 unique characters.

The core logic is encapsulated in a helper function atMost(k), which calculates the number of substrings with at most k unique characters. The count of substrings with exactly 3 unique characters is then derived by subtracting the count of substrings with at most 2 unique characters from those with at most 3 unique characters.

Expansion:

• Expand the window by incrementing the right pointer, updating the counter for each new element included from s.

Shrinking:

• If the number of unique characters within the window exceeds k, shrink the window from the left by decrementing the left pointer and adjusting the counter accordingly.

Logic:

• After ensuring the window contains at most k unique characters, calculate the number of new subarrays introduced by including the latest element, given by right - left, and update count.

The function numberOfSubstrings computes the total count of substrings containing exactly 3 unique characters by employing the atMost function, returning the difference between counts for k = 3 and k = 2.

Analysis

Time Complexity: O(2N)

• Iterating through the string s twice, once for each call to atMost. Each iteration involves a single pass through s with a sliding window, ensuring linear time complexity relative to the length of s.

Space Complexity: O(K)

• The space complexity is influenced by the counter, which tracks the frequency of characters within the window. In the worst case, the counter could contain an entry for every unique character up to k, indicating the space requirement is proportional to the number of unique characters considered, capped at k.

Python

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

    k = 3
    return atMost(k) - atMost(k - 1)

2799. Count Complete Subarrays in an Array (Medium)

atMostOptimized

Solution

This problem entails counting the number of subarrays within a given array nums where all elements occur the same number of times. The solution adopts a sliding window approach, utilizing a frequency counter (counter) to dynamically monitor the occurrences of each element within the current window and calculate the count of subarrays that meet the specified condition.

The strategy involves determining the number of subarrays with at most k unique elements by employing a helper function atMost(k), then adjusting this count to isolate subarrays where elements occur with complete uniformity.

Expansion:

• Increment the right pointer to include new elements in the window, updating the counter for each element’s frequency as it’s included.

Shrinking:

• If the window contains more than k unique elements, indicating that uniformity is not maintained, shrink the window from the left by decrementing the left pointer and adjusting the counter accordingly.

Logic:

• After ensuring the window contains at most k unique elements, calculate the number of new subarrays introduced by including the latest element, given by right - left, and update count.

The function countCompleteSubarrays computes the total count of complete subarrays by leveraging the atMost function with k set to the total number of unique elements in nums, effectively identifying the desired subarrays.

Analysis

Time Complexity: O(N)

• Utilizing the sliding window approach ensures a single pass through the array nums with the sliding window, expanding and shrinking based on the conditions. This guarantees linear time complexity relative to the length of nums.

Space Complexity: O(N)

• The space complexity is influenced by the counter, which tracks the frequency of elements within the window. In the worst case, the counter might contain an entry for every unique element in nums, indicating the space requirement is proportional to the size of the input array.

Python

def countCompleteSubarrays(self, nums: List[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

    k = len(set(nums))
    return atMost(k) - atMost(k - 1)

2743. Count Substrings Without Repeating Character (Medium)

atMostOptimized

Solution

The aim is to count the number of substrings within a given string s where each character appears exactly once. This problem is approached using a sliding window technique, complemented by a counter to track the frequency of each character within the current window.

A key part of the solution involves a helper function atMost(k), designed to count the number of substrings where each character’s frequency is at most k. Since the problem focuses on substrings without repeating characters, k is set to 1, implying each character may appear no more than once for a substring to be considered valid.

Expansion:

• The window expands by moving the right pointer forward, incrementing the counter for each character included from s.

Shrinking:

• If any character’s frequency exceeds k, the window shrinks from the left by decrementing the left pointer and adjusting the counter accordingly, ensuring all characters within the window adhere to the frequency constraint.

Logic:

• The number of valid substrings ending at the current right index is given by right - left, capturing all unique subarrays that meet the condition within the current window.

The function numberOfSpecialSubstrings employs the atMost(1) logic to compute the total count of valid substrings, directly returning this count as the solution. atMost(0) will always return 0.

Analysis

Time Complexity: O(N)

• Employing the sliding window with the atMost function involves iterating through the string s once, with each character being evaluated for inclusion in a valid substring. The linear scan, combined with efficient window adjustments, ensures linear time complexity relative to the length of s.

Space Complexity: O(26)

• s consists of lowercase English letters

Python

def numberOfSpecialSubstrings(self, s: str) -> int:
    def atMost(k):
        n = len(s)
        left = right = 0
        count = 0
        counter = collections.Counter()

        all_under_k = lambda: all(i <= k for i in counter.values())

        while right < n:
            # Expansion
            counter[s[right]] += 1
            right += 1
            # Shrinking
            while left < right and not all_under_k():
                counter[s[left]] -= 1
                if counter[s[left]] == 0:
                    counter.pop(s[left])
                left += 1
            # Logic
            count += right - left
        return count

    # return atMost(1) - atMost(0) # atMost(0) is 0
    return atMost(1)

Exactly K (without atMost)

2537. Count the Number of Good Subarrays (Medium)

Solution

This problem asks to count the number of “good” subarrays within an integer array nums where each good subarray contains at least k pairs of equal elements. The solution employs a sliding window approach alongside a frequency counter (counter) to dynamically track the pairs within each potential subarray and a pair counting formula to efficiently calculate the number of valid pairs as the window expands and shrinks.

Pair can be calculated using the combination formula: \(nC2 = \frac{n \times (n-1)}{2}\), and when a count of a number increases, remove the older calculated pair \((i-1)C2\) and add the new count pairs \((i)C2\).

Expansion:

• Increment the right pointer, thereby expanding the window to include new elements from nums. Update the counter with the frequency of the newly included element and adjust the total pair count (pairs) based on this frequency.

Shrinking:

• When the pair count within the window meets or exceeds k, indicating a potential “good” subarray, the window attempts to shrink from the left by decrementing the left pointer, updating the counter and accordingly adjusting the pairs.

Logic:

• Each time the shrinking condition is triggered (pair count within the window is at least k), increment count by n - right + 1 to account for all subarrays starting at the current left and extending to the right end of the array nums that meet the goodness criteria.

The function countGood iterates through nums, adjusting the window as described, and returns count, representing the total number of good subarrays found.

Analysis

Time Complexity: O(N)

• The algorithm performs a single pass through the array nums with the sliding window, ensuring linear time complexity relative to the length of nums. Each expansion and shrinkage involves constant-time operations for updating the counter and calculating the pairs.

Space Complexity: O(N)

• The space complexity is determined by the counter, which tracks the frequency of elements within the window. In the worst case, the counter could contain an entry for every unique element in nums, indicating the space requirement is proportional to the number of unique elements, capped at N.

Python

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  # Formula for nCr (r=2) (combination)
    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 (Medium)

Solution

This problem asks to count the number of subarrays within an array nums where the maximum element in the array appears at least k times. The solution employs a sliding window approach, complemented by a frequency counter (counter), to dynamically track the counts of elements within the current window and identify valid subarrays according to the specified condition.

An initial determination of the maximum element in nums (max_ele) allows the solution to focus on tracking the frequency of this specific element within varying window sizes.

Expansion:

• Increment the right pointer, thereby including new elements in the window. Update the counter with the frequency of the newly included element.

Shrinking:

• If the frequency of max_ele within the window reaches or exceeds k, indicating a potentially valid subarray, the window attempts to shrink from the left. This involves decrementing the left pointer and adjusting the counter accordingly.

Logic:

• For each configuration where max_ele’s frequency is at least k, calculate the number of possible subarrays extending to the end of nums from the current window. This is determined by n - right + 1, which represents all possible subarrays starting within the window and extending to the end of nums.

The function countSubarrays iterates through nums, adjusting the window size as described, and returns count, representing the total number of valid subarrays found.

Analysis

Time Complexity: O(N)

• Iterating through the array nums once with the sliding window, expanding and shrinking based on the frequency condition, ensures linear time complexity relative to the length of nums.

Space Complexity: O(N)

• The space complexity is influenced by the counter, which tracks the frequency of elements within the window. In the worst case, the counter could contain an entry for every element in nums, indicating the space requirement is proportional to the size of the input array.

Python

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