We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Subarrays Where Max Element Appears at Least K Times

Number: 3213

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Meta, Apple, Adobe

Problem Description

Given an integer array and a positive integer k, count the number of contiguous subarrays (a “subarray”) in which the maximum element (i.e. the largest number in that subarray) appears at least k times.

For example, if nums = [1,3,2,3,3] and k = 2 then there are 6 subarrays where the maximum (which is 3) appears at least twice.

Key Insights

  • In any subarray the “maximum” is defined as the largest element present.
  • A subarray will have maximum m if it does not contain any element strictly greater than m and it contains at least one occurrence of m.
  • Thus, if we “focus” on a candidate m that occurs in the array, then all subarrays whose maximum is m must lie in a contiguous “zone” of the array that is delimited by indices where an element larger than m occurs (we call these blockers).
  • For each occurrence of m we can precompute: • left blocker: the index of the closest element to the left that is > m (or -1 if none), and • right blocker: the index of the closest element to the right that is > m (or n if none).
  • Then the “valid zone” for that occurrence is [left_blocker+1, right_blocker–1]. In any such zone every subarray that contains at least one copy of m will have maximum m.
  • To ensure the maximum appears at least k times we group together those occurrences of m that lie in the same valid zone. If the positions are p0,p1,…,p(t–1), then the standard combinatorial idea is: for every contiguous window of k occurrences (say from p[i] to p[i+k–1]), the number of subarrays that include at least these k copies is   (p[i] – zone_start + 1) * (zone_end – p[i+k–1] + 1).
  • By summing the contributions from every candidate (and since every subarray has a unique maximum) we count each valid subarray exactly once.

Space and Time Complexity

Time Complexity: O(n) for the two “monotonic‐stack” passes plus O(n) to group positions – overall O(n), where n is the length of the array. Space Complexity: O(n) extra space for the stacks, dictionaries, and grouping.

Solution

We first precompute for every index the nearest element to the left that is greater than nums[i] (prevGreater) and to the right that is greater than nums[i] (nextGreater). These values define the boundaries of the “zone” in which nums[i] is the largest value.

Then we group, for each candidate value m, all indices i with nums[i] = m but further we separate them by their valid zone (each index i “belongs” to the subarray [L, R] where L = prevGreater[i] + 1 and R = nextGreater[i] – 1). In a given valid zone the maximum in any subarray is m. Now, if in a valid zone the candidate m occurs at positions p0, p1, …, p(t–1) (in increasing order) then for every window of k consecutive occurrences, the number of subarrays that “use” that block is    (p[i] – zone_start + 1) * (zone_end – p[i+k–1] + 1). Summing over all i gives the total count contributed by candidate m in that zone. Finally, summing over all candidates (and zones) gives the answer.

The key data structures used are: • Two stacks (for left and right boundaries). • A dictionary (or hashmap) that groups indices of the same candidate value together based on their valid zone. The “trick” is to count subarrays with at least k occurrences of the maximum by “anchoring” on the k‑th occurrence in each group and then counting all ways to choose a left endpoint (to the left of the first occurrence in the block) and a right endpoint (to the right of the k‑th occurrence) within the valid zone.

Code Solutions

# Python solution with detailed comments
class Solution:
    def countSubarrays(self, nums, k):
        n = len(nums)
        # Precompute previous greater element indices for each index.
        prevGreater = [-1] * n
        stack = []
        for i in range(n):
            # Pop until the current number is less than the element at the top (we want strictly greater)
            while stack and nums[stack[-1]] <= nums[i]:
                stack.pop()
            prevGreater[i] = stack[-1] if stack else -1
            stack.append(i)
        
        # Precompute next greater element indices for each index.
        nextGreater = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                stack.pop()
            nextGreater[i] = stack[-1] if stack else n
            stack.append(i)
        
        # Group indices by candidate number and its valid zone (zone = (zone_start, zone_end))
        groups = {}  # key: (m, zone_start, zone_end), value: list of indices
        for i in range(n):
            m = nums[i]
            zone_start = prevGreater[i] + 1
            zone_end = nextGreater[i] - 1
            key = (m, zone_start, zone_end)
            if key not in groups:
                groups[key] = []
            groups[key].append(i)
        
        result = 0
        # For each group (all occurrences of the same candidate m in the same valid zone)
        for (m, zone_start, zone_end), positions in groups.items():
            # positions are in increasing order already because we traversed i from 0 to n-1
            count = len(positions)
            if count < k:
                continue
            # For each contiguous block of k occurrences
            for i in range(count - k + 1):
                # The left endpoints can be chosen from [zone_start, positions[i]]
                left_choices = positions[i] - zone_start + 1
                # The right endpoints can be chosen from [positions[i+k-1], zone_end]
                right_choices = zone_end - positions[i+k-1] + 1
                result += left_choices * right_choices
        return result

# Example usage:
# sol = Solution()
# print(sol.countSubarrays([1,3,2,3,3], 2))   # Expected output: 6
← Back to All Questions