Count Subarrays with Max Element ≥ k Times

Max Frequency Subarray Problem – Number of Subarrays Where Maximum Appears at Least k Times

Problem Statement:

You are given an integer array nums[] and a positive integer k.

A subarray is a contiguous portion of the array. Your task is to count how many subarrays contain the maximum element of the entire array at least k times.

Example 1:

Input:

nums = [1, 3, 2, 3, 3], k = 2

Output:

6

Explanation: Subarrays where the max element (3) appears at least 2 times:

• [1, 3, 2, 3]

• [1, 3, 2, 3, 3]

• [3, 2, 3]

• [3, 2, 3, 3]

• [2, 3, 3]

• [3, 3]

Best Technique – Two Pointers (Sliding Window)

This problem is efficiently solved using the Two Pointers technique.

We maintain a sliding window [left...right] and track how many times the maximum value appears within that window. As soon as it appears at least k times, we know that:

• All subarrays ending at right and starting at any position from left to right are valid!

We use this to add (n - right) valid subarrays in one step, and then slide left to continue checking the rest.

Different Approaches:

Approach 1: Brute Force (Nested Loops)

Try all subarrays and count how many times the maximum element appears.

public long countSubarraysBruteForce(int[] nums, int k) {
    int n = nums.length;
    long count = 0;
    int maxVal = Arrays.stream(nums).max().getAsInt();

    for (int i = 0; i < n; i++) {
        int freq = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == maxVal) freq++;
            if (freq >= k) count++;
        }
    }

    return count;
}

Approach 2: Sliding Window (Two Pointers – Optimal)

public long countSubarrays(int[] nums, int k) {
    int maxVal = Integer.MIN_VALUE;
    for (int num : nums) {
        maxVal = Math.max(maxVal, num);
    }

    int n = nums.length;
    long count = 0;
    int left = 0;
    int maxCount = 0;

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

        while (maxCount >= k) {
            count += (n - right);  // Add all valid subarrays
            if (nums[left] == maxVal) {
                maxCount--;
            }
            left++;
        }
    }

    return count;
}

⚠️ Common Pitfalls:

• Integer Overflow: Make sure count is a long since the number of valid subarrays can be large.

• Correct Window Length: This approach doesn’t rely on length directly, but always ensure sliding window bounds are managed precisely.

• Don’t forget to update maxCount when shrinking the window.

📊 Time and Space Complexity:

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Two Pointers	O(n)	O(1)

🌍 Real-World Applications:

• Monitoring Systems: Detect when a critical value (like temperature, usage) remains dangerously high for too long.

• Stock Market: Identify windows where a stock hits its peak repeatedly over time.

• Sensor Networks: Trigger alarms when a maximum reading is sustained beyond a threshold.

I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)