Number of Subarrays with Bounded Maximum

Number of Subarrays with Bounded Maximum

What is this problem about?

The Number of Subarrays with Bounded Maximum problem asks you to count subarrays where the maximum element is in the range [left, right]. This coding problem uses the inclusion-exclusion principle: count(max ≤ right) - count(max ≤ left-1), where count(max ≤ x) is easily computed with a two-pointer sweep.

Why is this asked in interviews?

Uber, Quora, Amazon, and Google ask this because it demonstrates the powerful "count subarrays with max ≤ x" auxiliary function. Any range constraint can be decomposed using this function. The array and two pointers interview pattern is directly applied with the inclusion-exclusion insight.

Algorithmic pattern used

Inclusion-exclusion with count(max ≤ x) helper. Define count(bound) = number of subarrays where all elements ≤ bound. For a subarray with max in [left, right]: count(right) - count(left-1). The helper count(bound) is computed with two pointers: maintain a window of consecutive elements ≤ bound; at each right endpoint, valid subarrays = current window size.

Example explanation

arr=[2,1,4,3], left=2, right=3.

• count(3): valid windows (all ≤3): [2],[2,1],[1],[3],[3] — careful: at index 2 (val=4), reset window. Windows: [2]→1, [2,1]→2, [1]→1+2=3, reset at 4, [3]→1. count(3)=7? Let me compute properly: dp tracking. count(3): dp[0]=1(2≤3), dp[1]=2(2,1 both ≤3), dp[2]=0(4>3), dp[3]=1(3≤3). Sum=4. count(1): dp[0]=0(2>1), dp[1]=1(1≤1), dp[2]=0, dp[3]=0. Sum=1. Answer = count(3)-count(1) = 4-1 = 3.

Common mistakes candidates make

• Forgetting to reset the window length when an element exceeds the bound.
• Off-by-one: count(left-1) not count(left).
• Not using the helper function pattern (recomputing from scratch).
• Confusing "max ≤ bound" with "max < bound."

Interview preparation tip

The count(max ≤ x) helper is a powerful building block. Any problem asking "count subarrays where max is in [L, R]" decomposes into two calls. The helper uses a DP/two-pointer approach: dp[i] = number of valid subarrays ending at i = (dp[i-1]+1 if arr[i]≤bound else 0). Practice building this helper, then applying it to bounded max problems. This decomposition generalizes to "bounded min," "bounded sum," and combined constraints.