Count Subarrays Where Max Element Appears at Least K Times - Video Solutions
Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - Python
Count Subarrays Where Max Element Appears at Least K Times - Video Solution
Watch 10 video solutions for Count Subarrays Where Max Element Appears at Least K Times, a medium level problem involving Array, Sliding Window. This walkthrough by NeetCodeIO has 22,599 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are 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.
Example 1:
Input: nums = [1,3,2,3,3], k = 2 Output: 6 Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
Example 2:
Input: nums = [1,4,2,1], k = 3 Output: 0 Explanation: No subarray contains the element 4 at least 3 times.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= k <= 105
Approach Overview
Problem Overview: Given an integer array nums, count how many subarrays contain the maximum element of the entire array at least k times. The key observation: only the global maximum matters. Any valid subarray must include that value at least k times.
Approach 1: Sliding Window Technique (O(n) time, O(1) space)
First compute the global maximum of the array. Use a classic sliding window with two pointers left and right. Expand right across the array and count how many times the maximum appears inside the window. Whenever the count reaches k, start shrinking the window from the left until the count drops below k. For every position of right, the number of valid subarrays ending at right equals the current left pointer value. This works because any starting index before left still keeps at least k maximum elements in the window. The algorithm scans the array once, giving O(n) time and O(1) extra space.
Approach 2: Two-Pointer Approach with Max Index Tracking (O(n) time, O(k) space)
Another view is to track the indices where the global maximum appears. As you iterate through the array, push each max index into a list or queue. Once you have at least k occurrences, the earliest valid start of a subarray that includes those k maxima is the index of the (count-k)th maximum plus one. Every extension of the right pointer forms additional valid subarrays starting from earlier positions. This effectively behaves like a two-pointer scan but driven by the positions of the maximum values. Time complexity remains O(n), while space is O(k) for storing recent max indices.
Recommended for interviews: The sliding window approach is what interviewers expect for problems involving subarray counts with frequency constraints. It shows you recognize a variable-size window pattern and can translate a frequency condition into pointer movement. A brute-force enumeration would be O(n^2) or worse and mainly demonstrates baseline understanding, while the sliding window demonstrates real algorithmic skill with array traversal.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^2) | O(1) | Conceptual baseline or small input sizes |
| Sliding Window Technique | O(n) | O(1) | Best general solution for counting subarrays with frequency constraints |
| Two-Pointer with Max Index Tracking | O(n) | O(k) | Useful when tracking positions of important values simplifies counting logic |