# Count Subarrays Where Max Element Appears at Least K Times
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times)
Canonical: https://scaleengineer.com/dsa/problems/count-subarrays-where-max-element-appears-at-least-k-times
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force
This approach involves systematically checking every possible contiguous subarray within the `nums` array. We use two nested loops to define the start and end of each subarray. For each subarray, we count the occurrences of the global maximum element and check if the count meets the `k` threshold.
**Time:** O(N^2) in the worst case. Finding the maximum element takes O(N). The nested loops run in O(N^2) time, leading to a total complexity dominated by the loops. · **Space:** O(1), as we only use a few variables to store the maximum value, counters, and loop indices.
**Pros:** The logic is simple and easy to understand.; It's a direct implementation of the problem statement.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The brute-force method is the most straightforward way to solve the problem. 

1.  First, we iterate through the entire array to find its maximum element, let's call it `maxVal`.
2.  We then initialize a variable `ans` to 0, which will store our final count of valid subarrays.
3.  We use a pair of nested loops. The outer loop, with index `i`, iterates from `0` to `n-1` and sets the starting point of our subarrays. 
4.  The inner loop, with index `j`, iterates from `i` to `n-1`, setting the ending point. This `(i, j)` pair defines the subarray `nums[i...j]`.
5.  For each subarray, we count the number of times `maxVal` appears. To optimize this slightly from a naive O(N^3) approach, we can maintain a running count of `maxVal` within the inner loop. 
6.  When the count of `maxVal` in `nums[i...j]` reaches or exceeds `k`, we increment our `ans`. A further optimization is to notice that if `nums[i...j]` is valid, so is `nums[i...j+1]`, `nums[i...j+2]`, etc. So, once a valid subarray is found, we can add all remaining extensions to the answer and break the inner loop.

```java
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        long ans = 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] == maxVal) {
                    currentMaxCount++;
                }
                if (currentMaxCount >= k) {
                    // If nums[i..j] is valid, then nums[i..j+1], nums[i..j+2], ..., nums[i..n-1] are also valid.
                    // There are (n-1) - j + 1 = n - j such subarrays.
                    ans += (n - j);
                    break; // Move to the next starting position i
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
*   First, find the maximum element `maxVal` in the entire `nums` array.
*   Initialize a result counter, `ans`, to zero.
*   Use a nested loop to iterate through all possible subarrays. The outer loop with index `i` defines the start of the subarray, and the inner loop with index `j` defines the end.
*   For each starting position `i`, initialize a counter `currentMaxCount` to 0.
*   As the inner loop for `j` progresses from `i` to `n-1`, check if `nums[j]` is equal to `maxVal`. If it is, increment `currentMaxCount`.
*   If `currentMaxCount` becomes greater than or equal to `k`, it means the subarray `nums[i...j]` is valid. From this point on, for this fixed `i`, all subsequent subarrays `nums[i...j+1]`, `nums[i...j+2]`, etc., will also be valid.
*   Therefore, once `currentMaxCount >= k`, we can add the remaining number of subarrays, which is `n - j`, to our `ans` and break the inner loop to move to the next `i`.
*   After iterating through all possible starting points `i`, `ans` will hold the total count.

## Optimal Sliding Window
A much more efficient solution uses the sliding window technique. The core idea is to maintain a window `[left...right]` and efficiently count the number of valid subarrays as we iterate through the array with the `right` pointer. For each position `right`, we determine how many subarrays ending at `right` satisfy the condition.
**Time:** O(N). Finding the maximum element is O(N). The main loop involves two pointers, `left` and `right`, each traversing the array at most once. This results in a total time complexity of O(N). · **Space:** O(1), as it only requires a few variables for the pointers and the count, irrespective of the input size.
**Pros:** Extremely efficient with O(N) time complexity.; Uses constant extra space, making it optimal in terms of memory usage.
**Cons:** The logic, while efficient, can be less intuitive to grasp initially compared to the brute-force method.
### Explanation
This optimal approach leverages a sliding window to achieve linear time complexity. Instead of re-calculating for every subarray, we maintain a window and update our counts as the window slides.

The key insight is to count, for each ending position `right`, how many valid subarrays `[i...right]` exist. A subarray is valid if it has at least `k` occurrences of the array's maximum element (`maxVal`).

We use two pointers, `left` and `right`, to define our sliding window. We expand the window by moving `right` one step at a time. If `nums[right]` is `maxVal`, we increment a counter for `maxVal` within the window. 

Whenever our window `[left...right]` becomes 'valid' (i.e., contains `k` or more `maxVal`s), we know that any subarray starting at an index `i <= left` and ending at `right` is also valid. To simplify counting, we can find the minimal valid window. 

A cleaner way to count is to observe the following: for a fixed `right`, we advance `left` as much as possible while the window `[left...right]` remains valid. Let's say we stop at `left = p`. This means any subarray starting at `0, 1, ..., p-1` and ending at `right` is a valid subarray. There are `p` such subarrays. So, for each `right`, we add the current `left` pointer's value to our answer.

```java
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        long ans = 0;
        int left = 0;
        int maxCountInWindow = 0;
        int n = nums.length;

        for (int right = 0; right < n; right++) {
            if (nums[right] == maxVal) {
                maxCountInWindow++;
            }

            // While the window is valid (has at least k max elements),
            // shrink it from the left to find the boundary.
            while (maxCountInWindow >= k) {
                if (nums[left] == maxVal) {
                    maxCountInWindow--;
                }
                left++;
            }
            
            // For the current 'right', any subarray ending at 'right' with a starting
            // index from 0 to 'left - 1' is a valid subarray. The number of such
            // starting points is 'left'.
            ans += left;
        }

        return ans;
    }
}
```
### Algorithm
*   First, find the maximum element `maxVal` in the `nums` array.
*   Initialize `ans = 0`, a `left` pointer to `0`, and `maxCountInWindow = 0`.
*   Iterate through the array with a `right` pointer from `0` to `n-1`.
*   At each `right`, if `nums[right] == maxVal`, increment `maxCountInWindow`.
*   Now, use a `while` loop to shrink the window from the left. As long as the current window `[left...right]` is valid (i.e., `maxCountInWindow >= k`), we shrink it by incrementing `left`. If the element at the old `left` position was `maxVal`, we decrement `maxCountInWindow`.
*   After the `while` loop finishes, `left` points to the first index `p` such that the window `[p...right]` has *fewer than* `k` maximum elements. This implies that any subarray ending at `right` with a starting index `i` from `0` to `p-1` is a valid subarray.
*   The number of such valid starting indices is `p`, which is the current value of `left`. So, we add `left` to our total `ans`.
*   Repeat this for all `right` pointers.
*   Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  long countSubarrays(int[] nums, int k) {
    int mx = Arrays.stream(nums).max().getAsInt();
    int n = nums.length;
    long ans = 0;
    int cnt = 0, j = 0;
    for (int x : nums) {
      while (j < n && cnt < k) {
        cnt += nums[j++] == mx ? 1 : 0;
      }
      if (cnt < k) {
        break;
      }
      ans += n - j + 1;
      cnt -= x == mx ? 1 : 0;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countSubarrays(vector<int> &nums, int k) {
    int mx = *max_element(nums.begin(), nums.end());
    int n = nums.size();
    long long ans = 0;
    int cnt = 0, j = 0;
    for (int x : nums) {
      while (j < n && cnt < k) {
        cnt += nums[j++] == mx;
      }
      if (cnt < k) {
        break;
      }
      ans += n - j + 1;
      cnt -= x == mx;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int: mx = max(nums) n = len(nums) ans = cnt = j = 0 for x in nums: while j < n and cnt < k: cnt += nums[j] == mx j += 1 if cnt < k: break ans += n - j + 1 cnt -= x == mx return ans

```