Log inSign up
hardLeetCodeNot Started

Count Subarrays With Fixed Bounds

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

A fixed-bound subarray of nums is a subarray that satisfies the following conditions: 1. The minimum value in the subarray is equal to minK. 2. The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous sequence of elements within an array.

Example 1 · Multiple Overlapping Subarrays:

Input: nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1, 3, 5] and [1, 3, 5, 2]. Note that [1, 3, 5, 2, 7] contains 7 > 5 so it is invalid.

Example 2 · minK Equals maxK:

Input: nums = [1, 1, 1, 1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray contains only 1s, so min=1 and max=1. Total subarrays = 4*(4+1)/2 = 10.

Example 3 · Out-of-Bounds Elements:

Input: nums = [2, 1, 4, 3], minK = 1, maxK = 3
Output: 0
Explanation: 4 is greater than maxK (3), and 1 and 3 are separated by 4. No valid subarray exists.

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i], minK, maxK <= 106

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window and Two Pointer mechanics
  • Subarray counting via endpoint fixing
  • Understanding bounding indices and boundary intersections

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the endpoint-fixing technique for subarray counting.
  • Formulate valid start position bounds: (lastBad, min(lastMin, lastMax)].
  • Prevent 32-bit integer overflow using 64-bit integer accumulators.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Track three state indices: lastMin = -1, lastMax = -1, lastBad = -1.
  • At each element x: if x < minK or x > maxK, set lastBad = i. If x == minK, lastMin = i. If x == maxK, lastMax = i.
  • Add max(0LL, min(lastMin, lastMax) - lastBad) to total answer.

Connected Patterns:

Subarrays with K Different IntegersNumber of Subarrays with Bounded MaximumCount Subarrays with Median K

1. Nested Loops Validation (Brute Force)

Intuition

Inspect every possible subarray (i, j), maintaining running min and max values.

Algorithm

  1. 1. Initialize ans = 0.
  2. 2. Loop i from 0 to N-1: - curMin = infinity, curMax = -infinity - Loop j from i to N-1: - curMin = min(curMin, nums[j]), curMax = max(curMax, nums[j]) - if curMin < minK or curMax > maxK: break - if curMin == minK and curMax == maxK: ans++.
  3. 3. Return ans.

Brute Force All Subarrays Min/Max Evaluation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 2, 7, 5]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: Subarray [1, 3, 5] from i=0 to j=2 has min = 1 and max = 5
Visual state
Values and pointers at this exact step
array
S
1
3
5
2
7
5
0
↑ i=0 (val 1)
1
2
↑ j=2 (val 5)
3
4
5
Variables at this step
i
0
j
2
min
1
max
5
count
1
Check / comparison
Subarray [1, 3, 5]: min = 1 == minK (1), max = 5 == maxK (5).
Decision / next transition
FIXED-BOUND SUBARRAY FOUND! count += 1 (count = 1).
Why this step matters

Phase 1 — Step 1: Step 1: Subarray [1, 3, 5] from i=0 to j=2 has min = 1 and max = 5. Both bounds satisfied! count = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Brute Force Approach: Nested Loops Validation
7long long countSubarrays(const vector<int>& nums, int minK, int maxK) {
8 long long ans = 0;
9 int n = nums.size();
10
11 for (int i = 0; i < n; i++) {
12 int curMin = nums[i];
13 int curMax = nums[i];
14 for (int j = i; j < n; j++) {
15 curMin = min(curMin, nums[j]);
16 curMax = max(curMax, nums[j]);
17
18 if (curMin < minK || curMax > maxK) {
19 break;
20 }
21 if (curMin == minK && curMax == maxK) {
22 ans++;
23 }
24 }
25 }
26 return ans;
27}
28
29int main() {
30 vector<int> nums = {1, 3, 5, 2, 7, 5};
31 int minK = 1, maxK = 5;
32 long long result = countSubarrays(nums, minK, maxK);
33 cout << "Output: " << result << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops examine up to N*(N+1)/2 subarrays.
  • Space complexity: O(1) — Only constant extra variables are used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Segmenting by Invalid Elements (Better)

Intuition

Split array into contiguous valid subsegments and count valid combinations per subsegment.

Algorithm

  1. 1. Identify segments of nums with no out-of-range elements.
  2. 2. For each segment of length L: - Total subarrays = L * (L + 1) / 2 - Subtract subarrays without minK - Subtract subarrays without maxK - Add back subarrays with neither minK nor maxK.
  3. 3. Sum contributions from all segments.

Segment Splitting by Invalid Elements

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 2, 7, 5]
Current operationSTEP 1 OF 6
Phase 1 — Process each segment independently: Step 1: Numbers < 1 or > 5 act as hard segment dividers
Visual state
Values and pointers at this exact step
array
S
1
3
5
2
7
5
0
↑ Segment 1: [0..3]
1
2
3
4
↑ Splitter: 7
5
Variables at this step
Segment 1
[1, 3, 5, 2]
Splitter
7
Segment 2
[5]
Check / comparison
Element 7 > 5. Splits array into valid segments: [1, 3, 5, 2] and [5].
Decision / next transition
Process each segment independently.
Why this step matters

Phase 1 — Process each segment independently: Step 1: Numbers < 1 or > 5 act as hard segment dividers. Segment 1 is [1, 3, 5, 2], Segment 2 is [5].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better Approach: Segmenting by Invalid Elements
6long long countValidInSegment(const vector<int>& seg, int minK, int maxK) {
7 long long count = 0;
8 int lastMin = -1, lastMax = -1;
9 for (int i = 0; i < seg.size(); i++) {
10 if (seg[i] == minK) lastMin = i;
11 if (seg[i] == maxK) lastMax = i;
12 if (lastMin != -1 && lastMax != -1) {
13 count += (min(lastMin, lastMax) + 1);
14 }
15 }
16 return count;
17}
18
19long long countSubarrays(const vector<int>& nums, int minK, int maxK) {
20 long long total = 0;
21 vector<int> curSeg;
22
23 for (int x : nums) {
24 if (x >= minK && x <= maxK) {
25 curSeg.push_back(x);
26 } else {
27 if (!curSeg.empty()) {
28 total += countValidInSegment(curSeg, minK, maxK);
29 curSeg.clear();
30 }
31 }
32 }
33 if (!curSeg.empty()) {
34 total += countValidInSegment(curSeg, minK, maxK);
35 }
36 return total;
37}
38
39int main() {
40 vector<int> nums = {1, 3, 5, 2, 7, 5};
41 int minK = 1, maxK = 5;
42 long long result = countSubarrays(nums, minK, maxK);
43 cout << "Output: " << result << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — Partitioning into segments and processing each subsegment takes linear O(N) time.
  • Space complexity: O(N) — Storing segments requires O(N) auxiliary memory.

3. Three-Index Window Tracking (Optimal)

Intuition

Single pass in O(N) time and O(1) space tracking lastMin, lastMax, and lastBad indices.

Algorithm

  1. 1. Initialize ans = 0, lastMin = -1, lastMax = -1, lastBad = -1.
  2. 2. Loop i from 0 to N-1: - if nums[i] == minK: lastMin = i - if nums[i] == maxK: lastMax = i - if nums[i] < minK or nums[i] > maxK: lastBad = i - validStarts = min(lastMin, lastMax) - lastBad - if validStarts > 0: ans += validStarts.
  3. 3. Return ans.

3-Pointer Sliding Window (Last Seen Indices)

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [1, 3, 5, 2, 7, 5]
Current operationSTEP 1 OF 8
Phase 1 — Begin single linear pass: Step 1: Key insight: Any valid subarray ending at i must start after the latest badIdx and at or before min(minIdx, maxIdx)
Visual state
Values and pointers at this exact step
array
S
1
3
5
2
7
5
0
↑ Init Pointers
1
2
3
4
5
Variables at this step
badIdx
-1
minIdx
-1
maxIdx
-1
ans
0
Check / comparison
Track 3 key indices: badIdx = -1, minIdx = -1, maxIdx = -1. For each i: valid starts = max(0, min(minIdx, maxIdx) - badIdx).
Decision / next transition
Begin single linear pass.
Why this step matters

Phase 1 — Begin single linear pass: Step 1: Key insight: Any valid subarray ending at i must start after the latest badIdx and at or before min(minIdx, maxIdx)! Formula: max(0, min(minIdx, maxIdx) - badIdx).

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Optimal Approach: Three-Index Window Tracking
7long long countSubarrays(const vector<int>& nums, int minK, int maxK) {
8 long long ans = 0;
9 int lastMin = -1, lastMax = -1, lastBad = -1;
10
11 for (int i = 0; i < nums.size(); i++) {
12 if (nums[i] == minK) lastMin = i;
13 if (nums[i] == maxK) lastMax = i;
14 if (nums[i] < minK || nums[i] > maxK) lastBad = i;
15
16 int validStarts = min(lastMin, lastMax) - lastBad;
17 if (validStarts > 0) {
18 ans += validStarts;
19 }
20 }
21 return ans;
22}
23
24int main() {
25 vector<int> nums = {1, 3, 5, 2, 7, 5};
26 int minK = 1, maxK = 5;
27 long long result = countSubarrays(nums, minK, maxK);
28 cout << "Output: " << result << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass through nums performing constant O(1) arithmetic operations per element.
  • Space complexity: O(1) — Only three integer pointer variables used.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Check every subarray (i, j), tracking min and max.Recomputing minimums and maximums across O(N2) pairs.
2.Better — Segmenting by Bad ElementsO(N)O(N)Split array into segments bounded by bad elements, then count valid subarrays per segment.Auxiliary segment arrays.
3.Optimal — Three-Index Window TrackingOptimalO(N)O(1)Maintain lastMin, lastMax, lastBad pointers in a single pass.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • minK == maxK (e.g. nums = [1, 1, 1], minK=1, maxK=1) -> lastMin and lastMax point to the same index, formula min(lastMin, lastMax) - lastBad correctly computes all valid windows.
  • Array with no valid elements: nums = [10, 20, 30], minK=1, maxK=5 -> returns 0.
  • Result exceeds 32-bit integer limit: using 64-bit int (long in Java, long long in C++) avoids overflow on N=105.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Count Subarrays With Fixed Bounds?

2.Why is the brute force approach suboptimal for large inputs in Count Subarrays With Fixed Bounds?

3.Which data structure or technique enables the optimal solution for Count Subarrays With Fixed Bounds?

Back to DSA Sheet