Count Subarrays Where Max Element Appears at Least K Times

Step 1: Only one value matters

Find max, the largest value in the array. A subarray qualifies when it holds at least k copies of max; nothing else about it matters.

Step 2: Count by the right end

Fix the right end of a subarray at right. Moving its left end further left only adds elements, so it can only add copies of max. That means the valid left ends form a block: every start from 0 up to some point works, and nothing after it does.

Step 3: Find where that block ends

Keep a window [left, right] and the number of copies of max inside it. After adding nums[right], while the window has k copies, move left forward. When the loop stops, the window has k - 1 copies, and every start before left gives a subarray with at least k. That is left subarrays ending at right.

Step 4: Use a long

The count can reach about n² / 2, which for n = 10⁵ is far beyond an int.

nums = [1, 3, 2, 3, 3], k = 2, so max = 3.

result += left counts all the valid starts for the current right end at once.

public class CountSubarraysWhereMaxAppearsKTimes {

    public static long countSubarrays(int[] nums, int k) {
        int max = 0;
        for (int x : nums) {
            max = Math.max(max, x);
        }
        long result = 0;
        int left = 0;
        int count = 0;                        // copies of max in nums[left..right]
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == max) {
                count++;
            }
            while (count == k) {              // shrink until the window has k - 1 copies
                if (nums[left] == max) {
                    count--;
                }
                left++;
            }
            result += left;                   // starts 0 .. left-1 all give >= k copies
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(countSubarrays(new int[] {1, 3, 2, 3, 3}, 2));   // 6
        System.out.println(countSubarrays(new int[] {1, 4, 2, 1}, 3));      // 0
    }
}

• Time: O(n): one pass to find the maximum, one pass for the window.
• Space: O(1).

The same "count all starts before left" step is used in Number of Substrings Containing All Three Characters.