Count Subarrays With Fixed Bounds — Three-Index Counting Trick

Problem Statement#

Given an integer array nums and integers minK and maxK, count subarrays whose minimum equals minK and maximum equals maxK.

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= minK <= maxK <= 10^6
• 1 <= nums[i] <= 10^6

Input:  nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5
Output: 2

Input:  nums = [1, 1, 1, 1], minK = 1, maxK = 1
Output: 10

Why This Problem Matters#

LeetCode 2444 — Count Subarrays With Fixed Bounds — is a Hard rotation regular at Google and Amazon onsite loops. Brute forcing every subarray is O(n^2) and breaks for n = 10^5. The interviewer is looking for a candidate who can decompose the constraints and count contributions per right endpoint in O(1) extra work.

The trick is recognising that you do not need an explicit window. Three indices — last out-of-range index, last minK index, last maxK index — implicitly describe every valid window ending at the current position. Once you see this, the algorithm collapses into a five-line single pass.

This counting pattern reappears in scoring problems, log analytics, and stream summarisation: any time a subarray must include certain markers and exclude others, the same three-index trick applies.

The Core Insight#

A subarray is valid iff it includes at least one minK, at least one maxK, and no value outside [minK, maxK]. Walk left to right while maintaining:

• bad — last index where nums[i] was out of range.
• min_pos — last index where nums[i] == minK.
• max_pos — last index where nums[i] == maxK.

For a right endpoint i, a left endpoint j is valid iff j > bad and j <= min(min_pos, max_pos). The count of such j is max(0, min(min_pos, max_pos) - bad).

Initialising all three sentinels to -1 makes the formula naturally evaluate to 0 before the first valid window. Sum the per-i contribution and you have the answer in O(n) time and O(1) space.

Visual Dry Run#

nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5.

Total = 2.

Solution (Optimal)#

class Solution:
    def countSubarrays(self, nums, minK, maxK):
        ans = 0
        # bad: last index of an out-of-range element
        # min_pos: last index where nums[i] == minK
        # max_pos: last index where nums[i] == maxK
        bad = min_pos = max_pos = -1
 
        for i, v in enumerate(nums):
            if v < minK or v > maxK:
                bad = i
            if v == minK:
                min_pos = i
            if v == maxK:
                max_pos = i
 
            # Valid left endpoints j satisfy bad < j <= min(min_pos, max_pos).
            ans += max(0, min(min_pos, max_pos) - bad)
 
        return ans

var countSubarrays = function(nums, minK, maxK) {
    let ans = 0;
    let bad = -1, minPos = -1, maxPos = -1;
 
    for (let i = 0; i < nums.length; i++) {
        const v = nums[i];
 
        if (v < minK || v > maxK) bad = i;
        if (v === minK) minPos = i;
        if (v === maxK) maxPos = i;
 
        ans += Math.max(0, Math.min(minPos, maxPos) - bad);
    }
 
    return ans;
};

Time: O(n) — one pass, O(1) work per element. Space: O(1) — three integer trackers.

Common Mistakes#

• Brute forcing all subarrays in O(n^2).
• Initialising the trackers to 0 instead of -1, which double-counts the first index.
• Forgetting max(0, ...) so negative contributions corrupt the answer.
• Tracking running min and max instead of last positions of the exact bound values.
• Using a 32-bit accumulator: the answer can reach n * (n + 1) / 2, which overflows for n = 10^5 in Java or C++.

Interview Tips#

• State the three conditions explicitly before coding so the formula is justified.
• Emphasise why the answer is contiguous and why the rightmost positions are sufficient.
• Walk the dry run with one out-of-range element so the interviewer sees the bad reset.
• Mention 64-bit safety even when coding in Python; it shows production awareness.

Follow-up Questions#

• What if you need min >= minK and max <= maxK? Drop the position trackers and just use the bad pointer with an expanding window.
• What if minK > maxK? Return 0 immediately.
• Streaming version? Maintain the same three indices and emit contribution per arrival.
• Handle multiple (minK, maxK) queries? Precompute prefix counts of bound positions and use offline processing.
• Maximum possible answer? n * (n + 1) / 2 when all elements equal minK == maxK.

Key Takeaways#

• LeetCode 2444 is a Hard asked at Google and Amazon.
• A valid subarray must include minK, include maxK, and exclude any out-of-range value.
• Track three indices: last bad, last minK, last maxK, all initialised to -1.
• Contribution per right endpoint is max(0, min(min_pos, max_pos) - bad).
• Total time is O(n); space is O(1).
• The answer can exceed 32-bit range, use 64-bit integers in compiled languages.
• Three-index counting generalises to any subarray problem with mixed include and exclude conditions.