Count Subarrays With Fixed Bounds

Hard
804.

Count Subarrays With Fixed Bounds

Count Subarrays With Fixed Bounds is a hard coding problem on arrays, two pointers and sliding window, asked in Amazon, Google, Flipkart and Morgan Stanley interviews.

A subarray is fixed-bound when its minimum is exactly minK and its maximum is exactly maxK.

Return the number of fixed-bound subarrays of nums.

Example 1

Input
nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output
2
Explanation
[1,3,5] and [1,3,5,2].

Example 2

Input
nums = [1,1,1,1], minK = 1, maxK = 1
Output
10
Explanation
Every subarray qualifies.

Example 3

Input
nums = [1,3,5,2,7,5], minK = 1, maxK = 9
Output
0
Explanation
No element equals 9.

Constraints

  • 2 <= nums.length <= 50000
  • 1 <= nums[i], minK, maxK <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} minK
 * @param {number} maxK
 * @return {number}
 */
var countSubarraysFixedBounds = function(nums, minK, maxK) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Subarrays With Fixed Bounds — Problem & Solution

Count Subarrays With Fixed Bounds solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count Subarrays With Fixed Bounds is a hard coding problem on arrays, two pointers and sliding window, asked in Amazon, Google, Flipkart and Morgan Stanley interviews.

Problem statement

A subarray is fixed-bound when its minimum is exactly minK and its maximum is exactly maxK.

Return the number of fixed-bound subarrays of nums.

Example 1

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

Example 2

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray qualifies.

Example 3

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 9
Output: 0
Explanation: No element equals 9.

Constraints

  • 2 <= nums.length <= 50000
  • 1 <= nums[i], minK, maxK <= 1000000

Hints for Count Subarrays With Fixed Bounds

  1. Hint 1

    A valid subarray must contain at least one minK, at least one maxK, and nothing outside [minK, maxK].

  2. Hint 2

    Fix the right end and track three positions: the last minK, the last maxK, and the last out-of-range element.

  3. Hint 3

    The valid left ends sit strictly after the out-of-range element and at or before both of the other two.

How to solve Count Subarrays With Fixed Bounds

For each right end, the set of valid left ends is an interval determined by three running positions. Counting its size at every step totals every valid subarray in one pass.

Approach

  1. Track lastBad (the most recent element outside [minK, maxK]), lastMin and lastMax.
  2. At index i, update whichever of the three applies.
  3. The valid starts are lastBad + 1 … min(lastMin, lastMax); add min(lastMin, lastMax) - lastBad when positive.

Why it works

A subarray [l, i] is fixed-bound exactly when it avoids every out-of-range element (l > lastBad) and still reaches back to an occurrence of each bound (l <= lastMin and l <= lastMax). Those constraints define a contiguous range of l, whose size is the expression above — and it is 0 or negative precisely when no valid start exists.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Using >= instead of > against lastBad admits the out-of-range element itself.
  • minK may equal maxK, in which case both positions track the same index.
  • The count reaches about 1.25 · 10^9 at the stated size — accumulate carefully.

Reference solution

Python

from typing import List

def countSubarraysFixedBounds(nums: List[int], minK: int, maxK: int) -> int:
    res = 0
    last_min = last_max = last_bad = -1
    for i, x in enumerate(nums):
        if x < minK or x > maxK:
            last_bad = i
        if x == minK:
            last_min = i
        if x == maxK:
            last_max = i
        lo = min(last_min, last_max)
        if lo > last_bad:
            res += lo - last_bad
    return res

Java

public static int countSubarraysFixedBounds(int[] nums, int minK, int maxK) {
    long res = 0;
    int lastMin = -1, lastMax = -1, lastBad = -1;
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        if (x < minK || x > maxK) lastBad = i;
        if (x == minK) lastMin = i;
        if (x == maxK) lastMax = i;
        int lo = Math.min(lastMin, lastMax);
        if (lo > lastBad) res += lo - lastBad;
    }
    return (int) res;
}

C++

int countSubarraysFixedBounds(vector<int>& nums, int minK, int maxK) {
    long long res = 0;
    int lastMin = -1, lastMax = -1, lastBad = -1;
    for (int i = 0; i < (int) nums.size(); i++) {
        int x = nums[i];
        if (x < minK || x > maxK) lastBad = i;
        if (x == minK) lastMin = i;
        if (x == maxK) lastMax = i;
        int lo = min(lastMin, lastMax);
        if (lo > lastBad) res += lo - lastBad;
    }
    return (int) res;
}

JavaScript

var countSubarraysFixedBounds = function(nums, minK, maxK) {
    var res = 0, lastMin = -1, lastMax = -1, lastBad = -1;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        if (x < minK || x > maxK) lastBad = i;
        if (x === minK) lastMin = i;
        if (x === maxK) lastMax = i;
        var lo = Math.min(lastMin, lastMax);
        if (lo > lastBad) res += lo - lastBad;
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique