Skip to main content
Talentd

Count Subarrays Where Max Element Appears at Least K Times - Solution & Explanation

MediumArraySliding Window18 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

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 <= 105
  • 1 <= nums[i] <= 106
  • 1 <= 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.

Approach 1: Sliding Window Technique

This approach utilizes the sliding window technique to efficiently count subarrays that satisfy the given condition. By maintaining a window and a count of the occurrences of the maximum element within that window, we can determine the valid subarrays as we expand and contract the window.

The code initializes a sliding window by setting pointers i and j. As we iterate through the array, we update the current maximum element and its count within the window. When the count of the maximum element reaches k or more, we add subarrays from the start of the window to the end of the array that satisfy the condition.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), only constant space is used for variables.

Try this approach in the editor →

Approach 2: Two-Pointer Approach with Reset

This strategy involves iterating through the array with two pointers, resetting conditions when new maximum elements are encountered and calculating valid subarrays based on maximum occurrence counts.

The C code uses two pointers (left and right) to validate subarrays. When a maximum condition changes, the calculation restarts, which ensures only subarrays with the required maximum occurrence are considered.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as we process each element in nums.
Space Complexity: O(1), no extra space besides pointer variables.

Try this approach in the editor →

Approach 3: Two Pointers

Let's denote the maximum value in the array as mx.

We use two pointers i and j to maintain a sliding window, such that in the subarray between [i, j), there are k elements equal to mx. If we fix the left endpoint i, then all right endpoints greater than or equal to j-1 meet the condition, totaling n - (j - 1).

Therefore, we enumerate the left endpoint i, use the pointer j to maintain the right endpoint, use a variable cnt to record the number of elements equal to mx in the current window. When cnt is greater than or equal to k, we have found a subarray that meets the condition, and we increase the answer by n - (j - 1). Then we update cnt and continue to enumerate the next left endpoint.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Technique

Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), only constant space is used for variables.

Two-Pointer Approach with Reset

Time Complexity: O(n), as we process each element in nums.
Space Complexity: O(1), no extra space besides pointer variables.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n^2)O(1)Conceptual baseline or small input sizes
Sliding Window TechniqueO(n)O(1)Best general solution for counting subarrays with frequency constraints
Two-Pointer with Max Index TrackingO(n)O(k)Useful when tracking positions of important values simplifies counting logic

Video Solution

Count Subarrays Where Max Element Appears at Least K Times - Leetcode 2962 - Python • NeetCodeIO • 22,599 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Subarrays Where Max Element Appears at Least K Times easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing that only the global maximum matters and translating the "at least k occurrences" condition into a sliding window counting strategy.
Count Subarrays Where Max Element Appears at Least K Times Python/Java solution
In Python or Java, the solution uses two pointers and a counter tracking how many times the maximum element appears in the current window. Each time the count reaches k, move the left pointer while updating the count and accumulate the number of valid starting positions. The algorithm runs in O(n) time and constant space.
How to solve Count Subarrays Where Max Element Appears at Least K Times in O(n)?
Find the global maximum value in the array. Use a sliding window with two pointers and track how many times the maximum appears inside the window. When the count reaches k, move the left pointer until the count drops below k and add the current left index to the result for each right pointer position. This counts all valid subarrays ending at that position in linear time.
What is the best approach for Count Subarrays Where Max Element Appears at Least K Times?
The sliding window approach is the most efficient solution. First compute the global maximum of the array, then expand a window with a right pointer while tracking how many times the maximum appears. When the count reaches k, shrink the window from the left and count valid subarrays. This runs in O(n) time with O(1) extra space.
Is Count Subarrays Where Max Element Appears at Least K Times asked at Google/Amazon/Meta?
Problems involving sliding window subarray counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to maintain frequency constraints inside a dynamic window and compute counts efficiently.
What data structure is used in Count Subarrays Where Max Element Appears at Least K Times?
The optimal implementation mainly uses the sliding window pattern with two pointers and simple counters. Some variants also maintain a queue or list of indices where the maximum element appears to help count valid subarrays.
What is the time complexity of Count Subarrays Where Max Element Appears at Least K Times?
The optimal solution runs in O(n) time because each element is processed at most twice by the sliding window pointers. Space complexity is O(1) since only counters and pointer variables are maintained. A naive brute-force approach would take O(n^2) by checking every subarray.

Ready to solve this problem?

Practice Count Subarrays Where Max Element Appears at Least K Times with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Number of Subarrays Where Boundary Elements Are Maximum