Number of Subarrays with Bounded Maximum

medium two-pointers arrays counting

Problem

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum element in the subarray is in the range [left, right].

Inputnums = [2,1,4,3], left = 2, right = 3

Output3

Subarrays: [2], [2,1], [3].

nums, left, right

def numSubarrayBoundedMax(nums, left, right):
    def count(bound):
        cur = ans = 0
        for x in nums:
            cur = cur + 1 if x <= bound else 0
            ans += cur
        return ans
    return count(right) - count(left - 1)

var numSubarrayBoundedMax = function(nums, left, right) {
    const count = (bound) => {
        let cur = 0, ans = 0;
        for (const x of nums) {
            cur = x <= bound ? cur + 1 : 0;
            ans += cur;
        }
        return ans;
    };
    return count(right) - count(left - 1);
};

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }
    private int count(int[] nums, int bound) {
        int cur = 0, ans = 0;
        for (int x : nums) {
            cur = x <= bound ? cur + 1 : 0;
            ans += cur;
        }
        return ans;
    }
}

class Solution {
    int count(vector<int>& nums, int bound) {
        int cur = 0, ans = 0;
        for (int x : nums) {
            cur = x <= bound ? cur + 1 : 0;
            ans += cur;
        }
        return ans;
    }
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }
};

Explanation

Counting subarrays whose maximum falls between left and right sounds tricky, but there is a neat shortcut: count the easier thing and subtract. The key trick is "count(bound)", which counts subarrays whose maximum is at most some value.

The answer is count(right) - count(left - 1). Subarrays whose max is <= right minus those whose max is <= left - 1 leaves exactly the ones whose max sits in the range [left, right].

To compute count(bound) in one pass, we keep a running length cur of the current streak of elements that are all <= bound. Each time we add a valid element, every subarray ending here is valid, so we add cur to the total. A "too big" element breaks the streak and resets cur to 0.

Example: nums = [2,1,4,3], left = 2, right = 3. For count(3) the streaks give 1+2+0+1 = 4. For count(1) only the 1 qualifies, giving 1. So the answer is 4 - 1 = 3.

Because each count call is a single sweep, the whole thing runs in linear time with just a couple of counters.

Time: O(n) Space: O(1)