Count Subarrays With Loose Bounds solution and explanation
The problem
You are given an integer array nums and two integers minK and maxK.
A loose-bound subarray is a subarray in which every element is greater than or equal to minK and less than or equal to maxK.
Return the number of loose-bound subarrays in nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,4,7,3], minK = 1, maxK = 5
Output: 4
Explanation:
The loose-bound subarrays are [1], [4], [3], and [1, 4]. The minimum value in these subarrays is at least minK = 1 and the maximum value is at most maxK = 5.
Example 2:
Input: nums = [1,1], minK = 1, maxK = 1
Output: 3
Explanation:
The loose-bound subarrays are [1], [1], and [1, 1]. The minimum value in these subarrays is at least minK = 1 and the maximum value is at most maxK = 1.
Constraints:
2 <= nums.length <= 1051 <= nums[i], minK, maxK <= 106
Approach overview
Problem Overview: Given an array and two bounds, count every contiguous subarray whose elements all fall between the lower and upper bound, inclusive. A subarray is valid only if no element breaks either bound, so one out-of-range element invalidates every subarray that contains it.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Fix a left index, then extend the right index one element at a time. Track the running min and max as you extend. Each time the min drops below the lower bound or the max exceeds the upper bound, stop extending, because every longer subarray from that left index also fails. Otherwise, count the subarray and move on. This is simple to write and easy to verify, but it still touches up to n^2 / 2 subarrays in the worst case. Use it to confirm your understanding before optimizing.
Approach 2: Single Pass with a Valid Segment Start (O(n) time, O(1) space)
The key insight is that you never need to revisit a subarray. Keep a variable start that marks the first index of the current run of valid elements. Walk the array once. When you hit an element outside the bounds, set start to the next index, since no subarray can cross that element. For every index i, the number of valid subarrays ending at i equals i - start + 1. Add that to the answer. This works because every valid subarray ending at i starts somewhere inside the current valid segment, and that count is exactly the segment length up to i. Prefer this approach in every real setting. It is a single loop with two integer variables.
Approach 3: Counting Segments Then Summing (O(n) time, O(1) space)
You can also split the array into maximal valid segments and add L * (L + 1) / 2 for each segment of length L. This produces the same answer and makes the combinatorics explicit. It requires a second bookkeeping step when a segment closes, so it is harder to get right under interview pressure than Approach 2. Know it as an alternate view, but code Approach 2.
Recommended for interviews: Start by describing the brute force to show you understand the subarray constraint. Then move to the single-pass method and explain why the running count of valid endings works. The brute force shows understanding, but the single pass shows you can reduce a counting problem to one linear scan. This pattern also appears in array problems and in sliding window style counting. If the problem extends to tracking more state per window, reach for two pointers next.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Small inputs or verifying results against the optimal solution |
| Single Pass with Valid Segment Start | O(n) | O(1) | General case and interviews. Default choice. |
| Segment Summation | O(n) | O(1) | When you need the segment lengths themselves for other logic |
Frequently asked questions
Count Subarrays With Loose Bounds Python solution?
Initialize a total and a start index at 0. Loop over indices with enumerate. If the value is below the lower bound or above the upper bound, set start to i + 1. Otherwise, add i - start + 1 to the total, then return the total.
How to solve Count Subarrays With Loose Bounds in O(n)?
Walk the array with an index and a variable marking where the current valid run began. When an element falls outside the bounds, move the start past it. At each index, add the current index minus the start plus one to the total count.
What is the best approach for Count Subarrays With Loose Bounds?
The best approach is a single pass that tracks the start of the current valid run. For each index, add the length of the valid run ending there to the answer. It runs in O(n) time with O(1) extra space.
What data structure is used in Count Subarrays With Loose Bounds?
The optimal solution uses only integer variables, so no extra data structure is needed. You track the segment start index and a running total. The brute force also needs only a few variables for running min and max.
What is the time complexity of Count Subarrays With Loose Bounds?
The optimal solution runs in O(n) time because it scans the array once. The brute force enumeration runs in O(n^2) time because it checks every subarray starting point. Both use O(1) extra space.
Is Count Subarrays With Loose Bounds asked at Google, Amazon, or Meta?
The problem tags on FleetCode list only General topics, so company-specific frequency is not confirmed here. Subarray counting with bounds is a common pattern in interviews at large tech companies, so practice the single-pass method either way.