LeetCode-in-Java

2962. Count Subarrays Where Max Element Appears at Least K Times

Medium

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

Solution

public class Solution {
    public long countSubarrays(int[] n, int k) {
        int[] st = new int[n.length + 1];
        int si = 0;
        int m = 0;
        for (int i = 0; i < n.length; i++) {
            if (m < n[i]) {
                m = n[i];
                si = 0;
            }
            if (m == n[i]) {
                st[si++] = i;
            }
        }
        if (si < k) {
            return 0;
        }
        long r = 0;
        st[si] = n.length;
        for (int i = k; i <= si; i++) {
            r += (long) (st[i - k] + 1) * (st[i] - st[i - 1]);
        }
        return r;
    }
}

This site is open source. Improve this page.