Watch 7 video solutions for Count Stable Subarrays, a hard level problem involving Array, Binary Search, Prefix Sum. This walkthrough by Rajan Keshari ( CSE - IIT Dhanbad ) has 1,075 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
A subarray of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j].
You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri].
Return an integer array ans of length q, where ans[i] is the answer to the ith query.āāāāāāāāāāāāāā
Note:
Example 1:
Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]
Output: [2,3,4]
Explanation:āāāāā
queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
[3] and [1]. The total number of stable subarrays is 2.queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
[1], [2], and [1, 2]. The total number of stable subarrays is 3.queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
[3], [1], [2], and [1, 2]. The total number of stable subarrays is 4.Thus, ans = [2, 3, 4].
Example 2:
Input: nums = [2,2], queries = [[0,1],[0,0]]
Output: [3,1]
Explanation:
queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
[2], [2], and [2, 2]. The total number of stable subarrays is 3.queries[1] = [0, 0], the subarray is [nums[0]] = [2].
[2]. The total number of stable subarrays is 1.Thus, ans = [3, 1].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i] = [li, ri]0 <= li <= ri <= nums.length - 1Problem Overview: You are given an array and need to count how many contiguous subarrays satisfy a specific stability condition defined by the problem. The challenge is that checking every possible subarray quickly becomes too slow, so the solution relies on prefix aggregation and efficient range counting.
Approach 1: Brute Force Enumeration (O(nĀ²) time, O(1) space)
The most direct method checks every possible subarray. Use two nested loops: the outer loop chooses the start index and the inner loop extends the subarray to the right while maintaining the values required to verify stability. For each extension, evaluate whether the current segment satisfies the condition. This approach is easy to implement but performs up to n(n+1)/2 checks, which becomes impractical for large inputs.
Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)
Instead of recomputing values for every subarray, precompute a prefix sum array so any segment property based on cumulative values can be derived in constant time. For each starting index, you can use binary search to find the furthest ending index that keeps the subarray stable. Once that boundary is found, every index between the start and the boundary forms a valid subarray. This reduces the repeated scanning cost while keeping the verification step efficient.
Approach 3: Segmented Counting with Prefix Aggregates (O(n log n) time, O(n) space)
The optimized solution groups the array into segments where the stability constraint can be evaluated through prefix relationships. As you iterate through the array, maintain prefix values and use a searchable structure or binary search on previously seen prefix states. Each step counts how many earlier positions can pair with the current index to produce a stable subarray. This converts the problem from enumerating ranges to counting valid prefix pairs, which dramatically reduces redundant work. The segmented counting idea also avoids recomputing values for overlapping ranges.
Recommended for interviews: Start by explaining the brute force approach to show you understand the definition of a stable subarray. Interviewers then expect you to reduce repeated work using prefix sums and binary search. The segmented counting approach is the most practical implementation because it converts the problem into counting valid prefix relationships, achieving O(n log n) time while keeping the logic scalable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(nĀ²) | O(1) | Good for understanding the stability condition and verifying small inputs |
| Prefix Sum + Binary Search | O(n log n) | O(n) | When the stability rule can be expressed using cumulative values and monotonic boundaries |
| Segmented Counting with Prefix Aggregates | O(n log n) | O(n) | General scalable solution that counts valid prefix pairs instead of enumerating all subarrays |