Problem Description

You are given an integer array nums and two integers left and right. Your task is to count how many contiguous non-empty subarrays have their maximum element within the range [left, right] (inclusive).

A subarray is a contiguous part of the array. For example, if nums = [2, 1, 4, 3], then [2, 1], [1, 4, 3], and [4] are all subarrays, but [2, 4] is not since the elements are not contiguous.

For each subarray, you need to:

1. Find the maximum element in that subarray
2. Check if this maximum value is between left and right (inclusive)
3. Count all subarrays that satisfy this condition

The solution uses a clever approach by calculating the difference between two values:

• f(right): counts all subarrays where the maximum element is at most right
• f(left - 1): counts all subarrays where the maximum element is at most left - 1

The difference f(right) - f(left - 1) gives us exactly the subarrays where the maximum is in the range [left, right].

The helper function f(x) works by maintaining a counter t that tracks the length of the current valid subarray ending at each position. When we encounter a value greater than x, we reset t to 0. Otherwise, we increment t and add it to our total count, since each position contributes t valid subarrays ending at that position.

Intuition

The key insight is recognizing that finding subarrays with maximum in range [left, right] is equivalent to finding subarrays with maximum ≤ right and then removing those with maximum ≤ left - 1.

Think about it this way: if we want numbers in the range [left, right], we can:

1. First find all subarrays where max ≤ right
2. Then subtract all subarrays where max ≤ left - 1
3. What remains are subarrays where left ≤ max ≤ right

This transforms our problem into a simpler one: "count subarrays where the maximum element is at most x". This simpler problem can be solved efficiently in a single pass.

For counting subarrays with max ≤ x, we observe that:

• When we encounter an element > x, it cannot be part of any valid subarray, so we "break" the chain
• When we encounter an element ≤ x, it can form valid subarrays with all previous consecutive valid elements

For example, if we have [3, 1, 2] and x = 3:

• At position 0 (value 3): we can form 1 subarray: [3]
• At position 1 (value 1): we can form 2 subarrays: [1] and [3,1]
• At position 2 (value 2): we can form 3 subarrays: [2], [1,2], and [3,1,2]

The pattern is clear: at each valid position, the number of valid subarrays ending there equals the length of the current valid segment. This is tracked by variable t in the code, which counts consecutive valid elements and resets to 0 when we hit an invalid element (one that's > x).

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a difference-based counting strategy using a helper function f(x) that counts all subarrays with maximum element at most x.

Helper Function f(x):

• Initialize two variables:

  • cnt: accumulates the total count of valid subarrays
  • t: tracks the length of the current valid segment (consecutive elements ≤ x)

• Iterate through each element v in nums:

  • If v > x: Reset t = 0 (this element breaks the valid segment)
  • Otherwise: Increment t by 1 (extend the valid segment)
  • Add t to cnt (all subarrays ending at current position)

Main Logic: The final answer is computed as f(right) - f(left - 1):

• f(right) counts all subarrays where max ≤ right
• f(left - 1) counts all subarrays where max ≤ left - 1
• The difference gives subarrays where left ≤ max ≤ right

Example Walkthrough: Consider nums = [2, 1, 4, 3], left = 2, right = 3

For f(3) (max ≤ 3):

• Position 0 (value 2): t = 1, cnt = 1 → subarray [2]
• Position 1 (value 1): t = 2, cnt = 3 → subarrays [1], [2,1]
• Position 2 (value 4): t = 0, cnt = 3 → 4 > 3, reset
• Position 3 (value 3): t = 1, cnt = 4 → subarray [3]

For f(1) (max ≤ 1):

• Position 0 (value 2): t = 0, cnt = 0 → 2 > 1, reset
• Position 1 (value 1): t = 1, cnt = 1 → subarray [1]
• Position 2 (value 4): t = 0, cnt = 1 → 4 > 1, reset
• Position 3 (value 3): t = 0, cnt = 1 → 3 > 1, reset

Result: f(3) - f(1) = 4 - 1 = 3

The valid subarrays are [2], [2,1], and [3], each having their maximum in range [2, 3].

Time Complexity: O(n) - single pass through the array for each call to f() Space Complexity: O(1) - only using constant extra space

Example Walkthrough

Let's walk through a concrete example with nums = [3, 0, 2, 1, 4], left = 1, right = 3.

We need to find all subarrays where the maximum element is between 1 and 3 (inclusive).

Step 1: Calculate f(3) - count subarrays where max ≤ 3

Starting with cnt = 0 and t = 0:

• Index 0, value = 3:

  • 3 ≤ 3 ✓, so t = 1
  • Add t to cnt: cnt = 0 + 1 = 1
  • Valid subarrays ending here: [3]

• Index 1, value = 0:

  • 0 ≤ 3 ✓, so t = 2
  • Add t to cnt: cnt = 1 + 2 = 3
  • Valid subarrays ending here: [0], [3,0]

• Index 2, value = 2:

  • 2 ≤ 3 ✓, so t = 3
  • Add t to cnt: cnt = 3 + 3 = 6
  • Valid subarrays ending here: [2], [0,2], [3,0,2]

• Index 3, value = 1:

  • 1 ≤ 3 ✓, so t = 4
  • Add t to cnt: cnt = 6 + 4 = 10
  • Valid subarrays ending here: [1], [2,1], [0,2,1], [3,0,2,1]

• Index 4, value = 4:

  • 4 > 3 ✗, so reset t = 0
  • Add t to cnt: cnt = 10 + 0 = 10
  • No valid subarrays ending here

f(3) = 10

Step 2: Calculate f(0) - count subarrays where max ≤ 0

Starting with cnt = 0 and t = 0:

• Index 0, value = 3: 3 > 0 ✗, t = 0, cnt = 0
• Index 1, value = 0: 0 ≤ 0 ✓, t = 1, cnt = 0 + 1 = 1 (subarray: [0])
• Index 2, value = 2: 2 > 0 ✗, t = 0, cnt = 1
• Index 3, value = 1: 1 > 0 ✗, t = 0, cnt = 1
• Index 4, value = 4: 4 > 0 ✗, t = 0, cnt = 1

f(0) = 1

Step 3: Calculate the final answer

Answer = f(3) - f(0) = 10 - 1 = 9

The 9 valid subarrays with max in range [1, 3] are:

1. [3] - max = 3
2. [3,0] - max = 3
3. [2] - max = 2
4. [0,2] - max = 2
5. [3,0,2] - max = 3
6. [1] - max = 1
7. [2,1] - max = 2
8. [0,2,1] - max = 2
9. [3,0,2,1] - max = 3

Each subarray's maximum falls within [1, 3], confirming our answer of 9.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm consists of:

• The helper function f(x) iterates through the entire array once, performing constant time operations for each element - this takes O(n) time
• The main function calls f(right) and f(left - 1), which means two passes through the array
• Total time: O(n) + O(n) = O(2n) = O(n)

Space Complexity: O(1) - constant extra space.

The algorithm only uses a fixed number of variables:

• In function f(x): variables cnt, t, and v
• No additional data structures are created
• The space used doesn't scale with the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Counting Logic

A common mistake is trying to directly count subarrays with maximum in range [left, right] by checking each subarray individually, leading to inefficient O(n²) or O(n³) solutions.

Incorrect Approach:

def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
    count = 0
    n = len(nums)
    # Inefficient: Check every subarray
    for i in range(n):
        for j in range(i, n):
            max_val = max(nums[i:j+1])  # O(n) operation
            if left <= max_val <= right:
                count += 1
    return count

Solution: Use the difference-based approach with the helper function that counts subarrays with max at most a threshold.

2. Incorrect Handling of Elements Equal to Boundaries

Developers might incorrectly exclude elements equal to left or right, forgetting that the range is inclusive.

Incorrect:

def count_subarrays_with_max_at_most(threshold):
    total_count = 0
    consecutive_valid_elements = 0
  
    for value in nums:
        if value >= threshold:  # Wrong: should be value > threshold
            consecutive_valid_elements = 0
        else:
            consecutive_valid_elements += 1
        total_count += consecutive_valid_elements
  
    return total_count

Solution: Ensure the condition correctly uses value > threshold to include elements equal to the threshold.

3. Forgetting to Reset Counter When Element Exceeds Threshold

A subtle bug occurs when developers forget to reset the consecutive count when encountering an element greater than the threshold.

Incorrect:

def count_subarrays_with_max_at_most(threshold):
    total_count = 0
    consecutive_valid_elements = 0
  
    for value in nums:
        if value <= threshold:
            consecutive_valid_elements += 1
            total_count += consecutive_valid_elements
        # Missing: reset consecutive_valid_elements when value > threshold
  
    return total_count

Solution: Always reset consecutive_valid_elements = 0 when value > threshold.

4. Off-by-One Error in the Difference Calculation

Using f(left) instead of f(left - 1) is a critical mistake that excludes subarrays with maximum exactly equal to left.

Incorrect:

return count_subarrays_with_max_at_most(right) - count_subarrays_with_max_at_most(left)
# This would count subarrays with max in range (left, right], excluding left

Solution: Always use f(left - 1) to ensure subarrays with maximum equal to left are included.

5. Not Understanding Why the Consecutive Count Works

Some might incorrectly think they need to track all possible starting positions for subarrays.

Key Insight: When at position i with consecutive_valid_elements = t, there are exactly t valid subarrays ending at position i:

• Subarray starting at position i (length 1)
• Subarray starting at position i-1 (length 2)
• ...
• Subarray starting at position i-t+1 (length t)

This is why adding consecutive_valid_elements to the total count at each step gives the correct result.