LeetCode 2962: Count Subarrays Where Max Element Appears at Least K Times

The problem "Count Subarrays Where Max Element Appears at Least K Times" (LeetCode 2962) requires us to count the number of subarrays where the maximum element of the array appears at least k times in that subarray. This problem tests our ability to efficiently count subarrays that meet specific frequency conditions.

Problem Statement

Given an integer array nums and a positive integer k, return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

A subarray is a contiguous sequence of elements within an array.

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 106
• 1 ≤ k ≤ 105

Problem Link

View on LeetCode ↗

Example 1

Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation:
The subarrays that contain the element 3 (which is the maximum) at least 2 times are:
- [1,3,2,3] → contains 3 twice
- [1,3,2,3,3] → contains 3 three times
- [3,2,3] → contains 3 twice
- [3,2,3,3] → contains 3 three times
- [2,3,3] → contains 3 twice
- [3,3] → contains 3 twice

Example 2

Input: nums = [1,4,2,1], k = 3
Output: 0
Explanation:
No subarray contains the maximum element (4) at least 3 times.

Approach 1: Brute Force (TLE)

The brute force approach checks every possible subarray and counts how many times the maximum element appears in each. While straightforward, this approach results in O(n²) time complexity, which is too slow for the upper constraint of n ≤ 10⁵.

Algorithm Steps

1. Find the maximum element in the array
2. Initialize a counter to zero
3. Iterate through all possible starting indices
4. For each starting index, expand the subarray to the right
5. Count occurrences of max element in current subarray
6. Increment counter if count ≥ k
7. Return the final count

Complexity Analysis

Why it fails: For n = 10⁵, the number of operations would be around 10¹⁰, which is way beyond what's acceptable (typically need to stay under 10⁶ operations).

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int max_num = *max_element(nums.begin(), nums.end());
        long long count = 0;
        int n = nums.size();
        
        for(int i = 0; i < n; i++) {
            int current_max_count = 0;
            for(int j = i; j < n; j++) {
                if(nums[j] == max_num) {
                    current_max_count++;
                }
                if(current_max_count >= k) {
                    count += (n - j);
                    break;
                }
            }
        }
        
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int maxNum = Arrays.stream(nums).max().getAsInt();
        long count = 0;
        int n = nums.length;
        
        for(int i = 0; i < n; i++) {
            int currentMaxCount = 0;
            for(int j = i; j < n; j++) {
                if(nums[j] == maxNum) {
                    currentMaxCount++;
                }
                if(currentMaxCount >= k) {
                    count += (n - j);
                    break;
                }
            }
        }
        
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        count = 0
        n = len(nums)
        
        for i in range(n):
            current_max_count = 0
            for j in range(i, n):
                if nums[j] == max_num:
                    current_max_count += 1
                if current_max_count >= k:
                    count += (n - j)
                    break
                    
        return count
                

Approach 2: Sliding Window with Frequency Map (Optimal)

The optimal solution uses a sliding window technique combined with a frequency map to track occurrences of the maximum element. This approach works by maintaining a window where the count of the maximum element is at least k.

Key Insights

• First find the maximum element in the array (only need to do this once)
• Use a sliding window to track subarrays containing the max element
• When the count of max element reaches k, all subarrays ending at current right pointer and starting from current left pointer to any previous valid position will be valid
• Use a frequency map to efficiently track counts of elements in the current window

Algorithm Steps

1. Find the maximum element in the array
2. Initialize left pointer, count, and result to 0
3. Initialize a frequency map (or just track count of max element)
4. Iterate with right pointer from 0 to n-1:
   • Update frequency of current element
   • If current element is max, update max count
   • While max count ≥ k:
     • Add all valid subarrays ending at right pointer to result
     • Move left pointer forward and adjust counts
5. Return the total count

Complexity Analysis

Explanation: Each element is processed exactly twice (added once when window expands and removed once when window contracts), resulting in O(n) time complexity. We only need constant space to track the count of the maximum element.

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int max_num = *max_element(nums.begin(), nums.end());
        long long count = 0;
        int max_count = 0;
        int left = 0;
        int n = nums.size();
        
        for(int right = 0; right < n; right++) {
            if(nums[right] == max_num) {
                max_count++;
            }
            
            while(max_count >= k) {
                count += (n - right);
                if(nums[left] == max_num) {
                    max_count--;
                }
                left++;
            }
        }
        
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int maxNum = Arrays.stream(nums).max().getAsInt();
        long count = 0;
        int maxCount = 0;
        int left = 0;
        int n = nums.length;
        
        for(int right = 0; right < n; right++) {
            if(nums[right] == maxNum) {
                maxCount++;
            }
            
            while(maxCount >= k) {
                count += (n - right);
                if(nums[left] == maxNum) {
                    maxCount--;
                }
                left++;
            }
        }
        
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        count = 0
        max_count = 0
        left = 0
        n = len(nums)
        
        for right in range(n):
            if nums[right] == max_num:
                max_count += 1
                
            while max_count >= k:
                count += (n - right)
                if nums[left] == max_num:
                    max_count -= 1
                left += 1
                
        return count
                

Approach 3: Sliding Window with Map (Alternative Solution)

This alternative solution uses a map to track all elements in the current window, but still focuses on the count of the maximum element. It's slightly more general but has the same time complexity.

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        map<int, int> mp;
        long long count = 0;
        int max_num = *max_element(nums.begin(), nums.end());
        int left = 0;
        int n = nums.size();
        
        for(int right = 0; right < n; right++) {
            mp[nums[right]]++;
            
            while(mp[max_num] >= k) {
                count += (n - right);
                mp[nums[left]]--;
                left++;
            }
        }
        
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        long count = 0;
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int left = 0;
        int n = nums.length;
        
        for(int right = 0; right < n; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            
            while(map.getOrDefault(maxNum, 0) >= k) {
                count += (n - right);
                map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }
        }
        
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        
        mp = defaultdict(int)
        count = 0
        max_num = max(nums)
        left = 0
        n = len(nums)
        
        for right in range(n):
            mp[nums[right]] += 1
            
            while mp.get(max_num, 0) >= k:
                count += (n - right)
                mp[nums[left]] -= 1
                left += 1
                
        return count
                

Edge Cases and Special Considerations

When implementing solutions for this problem, consider these edge cases:

1. All Elements Same

Input: nums = [3,3,3,3], k = 2
Output: 6
All subarrays of length ≥2 contain the max element (3) at least twice:
[3,3], [3,3], [3,3], [3,3,3], [3,3,3], [3,3,3,3]

2. Single Element Array

Input: nums = [5], k = 1
Output: 1 (the single element subarray contains max once)

Input: nums = [5], k = 2
Output: 0 (can't have count ≥2 in single element array)

3. Max Element Doesn't Appear Enough

Input: nums = [1,2,1,2], k = 1
Output: 4 (each single element subarray contains max once)

Input: nums = [1,2,1,2], k = 2
Output: 0 (max element 2 never appears twice in any subarray)

4. Large k Value

Input: nums = [1,1,1,...,1] (105 elements), k = 105
Output: 1 (only the full array has count = k)

Approach 4: Optimized Sliding Window (Without Map)

This is the most efficient implementation of the sliding window approach that doesn't require any additional space for a map. It simply tracks the count of the maximum element in the current window.

Key Insights

• Only need to track count of the maximum element, not all elements
• When max_count reaches k, all subarrays ending at current right and starting from current left are valid
• No need for extra space - just maintain a counter for max element

Algorithm Steps

1. Find the maximum element in the array
2. Initialize left pointer, max_count, and result count to 0
3. Iterate with right pointer from 0 to n-1:
   • If current element is max, increment max_count
   • While max_count ≥ k:
     • Add (n - right) to count (all valid subarrays ending at right)
     • If left element is max, decrement max_count
     • Move left pointer forward
4. Return the total count

Complexity Analysis

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        long long max_count = 0;
        long long count = 0;
        int maxi = *max_element(begin(nums), end(nums));
        int i = 0;
        int j = 0;

        while(j < n) {
            if(nums[j] == maxi)
                max_count++;

            while(max_count >= k) {
                count += (n - j);
                if(nums[i] == maxi)
                    max_count--;
                i++;
            }
            j++;
        }
        return count;
    }
};
                

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int n = nums.length;
        long maxCount = 0;
        long count = 0;
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int left = 0;
        
        for(int right = 0; right < n; right++) {
            if(nums[right] == maxNum)
                maxCount++;
                
            while(maxCount >= k) {
                count += (n - right);
                if(nums[left] == maxNum)
                    maxCount--;
                left++;
            }
        }
        return count;
    }
}
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_count = 0
        count = 0
        max_num = max(nums)
        left = 0
        
        for right in range(n):
            if nums[right] == max_num:
                max_count += 1
                
            while max_count >= k:
                count += (n - right)
                if nums[left] == max_num:
                    max_count -= 1
                left += 1
                
        return count
                

Approach 5: Index Tracking (Optimal Space)

This approach tracks the indices of all occurrences of the maximum element, then calculates valid subarrays by leveraging these indices. It provides an alternative way to solve the problem with O(n) time and O(m) space (where m is the count of max elements).

Key Insights

• Store all indices where the maximum element appears
• For each occurrence after the k-th one, calculate valid subarrays using the (i-k)th index
• Efficiently counts subarrays without maintaining a sliding window

Algorithm Steps

1. Find the maximum element in the array
2. Initialize an empty list to store indices of max elements
3. Initialize count to 0
4. Iterate through the array:
   • When encountering the max element, record its index
   • If we have at least k occurrences:
     • The valid starting points are from 0 to the (i-k)th occurrence index + 1
     • Add these starting points to the count
5. Return the total count

Complexity Analysis

Implementation

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        long long count = 0;
        int maxE = *max_element(begin(nums),end(nums));
        vector<int> indices;

        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == maxE) {
                indices.push_back(i);
            }

            int size = indices.size();
            if(size >= k) {
                int last_index = indices[size-k];
                count += last_index + 1;
            }
        }
        return count;
    }
};
// TC: O(n) 
// SC: O(m) where m is number of max elements
                

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long count = 0;
        int maxE = Arrays.stream(nums).max().getAsInt();
        List<Integer> indices = new ArrayList<>();

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == maxE) {
                indices.add(i);
            }

            int size = indices.size();
            if(size >= k) {
                int last_index = indices.get(size - k);
                count += last_index + 1;
            }
        }
        return count;
    }
}
// TC: O(n) 
// SC: O(m) where m is number of max elements
                

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        count = 0
        maxE = max(nums)
        indices = []

        for i in range(len(nums)):
            if nums[i] == maxE:
                indices.append(i)

            size = len(indices)
            if size >= k:
                last_index = indices[size - k]
                count += last_index + 1
                
        return count
# TC: O(n) 
# SC: O(m) where m is number of max elements
                

Comparison of Approaches

Frequently Asked Questions