Count Subarrays With Fixed Bounds

Hard Arrays & Hashing Sliding Window · Variable Original on LeetCode

Count Subarrays With Fixed Bounds is a hard arrays & hashing problem solved with the sliding window · variable pattern. The best approach, optimal (track last wall, last mink, last maxk), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend every start) up.

Problem

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray is a contiguous, non-empty part of nums whose smallest element is exactly minK and whose largest element is exactly maxK. Return the number of fixed-bound subarrays.

Examples

Example 1

Input
nums = [2, 4, 3, 2, 6], minK = 2, maxK = 4
Output
4
Why
[2, 4], [2, 4, 3], [2, 4, 3, 2] and [4, 3, 2] qualify; nothing may include the 6.

Example 2

Input
nums = [3, 3, 3], minK = 3, maxK = 3
Output
6
Why
Every one of the 6 subarrays has minimum 3 and maximum 3.

Example 3

Input
nums = [1, 5, 2], minK = 2, maxK = 5
Output
1
Why
Only [5, 2] works; anything containing the 1 has a minimum that is too small.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (extend every start)O(n²)O(1)
Optimal (track last wall, last minK, last maxK)O(n)O(1)

1Brute force (extend every start)

TimeO(n²)Each start may scan to the end of the array.
SpaceO(1)A few running values.

For each start index, walk right while keeping the running minimum and maximum. Count every end where min == minK and max == maxK, and stop as soon as a value falls outside [minK, maxK], since no longer subarray from this start can recover.

  1. For each l: mn = +inf, mx = -inf.
  2. For r from l: update mn and mx with nums[r]; if mn < minK or mx > maxK, break.
  3. If mn == minK and mx == maxK, count++.
class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long count = 0;
        int n = nums.length;
        for (int l = 0; l < n; l++) {
            int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
            for (int r = l; r < n; r++) {
                mn = Math.min(mn, nums[r]);
                mx = Math.max(mx, nums[r]);
                if (mn < minK || mx > maxK) break;
                if (mn == minK && mx == maxK) count++;
            }
        }
        return count;
    }
}

2Optimal (track last wall, last minK, last maxK)

TimeO(n)One pass with constant work per index.
SpaceO(1)Three indices and the running total.

Scan once and remember three positions: the last index holding a value outside [minK, maxK] (a wall), the last index equal to minK and the last index equal to maxK. A subarray ending at r qualifies exactly when its start lies after the wall and at or before both of the other two positions, which gives max(0, min(lastMin, lastMax) - wall) choices.

  1. wall = lastMin = lastMax = -1.
  2. For each r: if nums[r] is outside [minK, maxK], wall = r. If nums[r] == minK, lastMin = r. If nums[r] == maxK, lastMax = r.
  3. Add max(0, min(lastMin, lastMax) - wall) to the answer.
class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long count = 0;
        int wall = -1, lastMin = -1, lastMax = -1;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] < minK || nums[r] > maxK) wall = r;
            if (nums[r] == minK) lastMin = r;
            if (nums[r] == maxK) lastMax = r;
            count += Math.max(0, Math.min(lastMin, lastMax) - wall);
        }
        return count;
    }
}

Edge cases to test

  • minK == maxK: every subarray made only of that value counts
  • minK > maxK: no subarray can qualify
  • Out-of-range values split the array into independent pieces
  • The answer can exceed 32 bits

Hints

Hint 1

A qualifying subarray cannot contain any value below minK or above maxK. Those values act as walls.

Hint 2

Fix the right end r. The subarray [l, r] qualifies when l is after the last wall and at or before both the last minK and the last maxK seen so far.

Hint 3

So for each r add max(0, min(lastMin, lastMax) - lastWall). One pass, three indices.

FAQ

What is the best time complexity for Count Subarrays With Fixed Bounds?

Optimal (track last wall, last minK, last maxK) runs in O(n) time and O(1) extra space. One pass with constant work per index.

Which pattern does Count Subarrays With Fixed Bounds use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.

Is there a brute force solution for Count Subarrays With Fixed Bounds?

Yes. Brute force (extend every start) takes O(n²) time and O(1) space. For each start index, walk right while keeping the running minimum and maximum.

Which edge cases should I test for Count Subarrays With Fixed Bounds?

minK == maxK: every subarray made only of that value counts; minK maxK: no subarray can qualify; Out-of-range values split the array into independent pieces; The answer can exceed 32 bits.