Count Subarrays Where Max Element Appears at Least K Times

Problem Statement

In this task, you are provided with an integer array nums and a positive integer k. Your objective is to calculate how many subarrays exist in which the maximum element of the array appears at least k times. A subarray is defined as a contiguous part of the main array, maintaining the order of elements as they appear in nums.

Examples

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 and Intuition

To solve this problem, consider the following steps and understanding based on the given examples:

1. Identify the maximum element in any potential subarray.
2. Check if this maximum element appears at least k times in that subarray.
3. Count all such subarrays that meet the criteria.

Analysis based on examples:

• For nums = [1,3,2,3,3] and k = 2:

  • The number (3) is the maximum in various subarrays and appears at least twice. Subarrays like [1,3,2,3], [1,3,2,3,3], etc., are valid.
  • This leads to a count of 6 such subarrays.

• For nums = [1,4,2,1] and k = 3:

  • No subarray can have the maximum element appearing at least three times, leading to a count of 0.

Key Constraints to keep in mind:

• The size of the nums (nums.length) can go up to 100,000, implying that efficiency is crucial.
• The values within nums and the value of k can be quite large, up to 1,000,000 and 100,000 respectively. This suggests that handling large values and possibly large arrays is essential for an efficient solution.
• Direct brute force approaches that check all subarrays will be inefficient due to the potential high value of nums.length. An optimal approach would be necessary to scan through possible subarrays and quickly determine if they meet the criteria without redundant checks.

Solutions

class Solution {
public:
    long long computeSubarrays(vector<int>& elements, int threshold) {
        int highestValue = *max_element(elements.begin(), elements.end());
        vector<int> maxIndices;
        long long result = 0;
    
        for (int i = 0; i < elements.size(); i++) {
            if (elements[i] == highestValue) {
                maxIndices.push_back(i);
            }
    
            int count = maxIndices.size();
            if (count >= threshold) {
                result += maxIndices[count - threshold] + 1;
            }
        }
    
        return result;
    }
};