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.
According to the problem description, a stable subarray is defined as a subarray without inversion pairs, meaning the elements in the subarray are arranged in non-decreasing order. Therefore, we can divide the array into several non-decreasing segments, using an array seg to record the starting position of each segment. At the same time, we need a prefix sum array s to record the number of stable subarrays within each segment.
Then, for each query [l, r], there may be 3 cases:
[l, r] is completely contained within a single segment. In this case, the number of stable subarrays can be directly calculated using the formula \frac{(k + 1) cdot k}{2}, where k = r - l + 1.[l, r] spans multiple segments. In this case, we need to separately calculate the number of stable subarrays in the left incomplete segment, the right incomplete segment, and the complete segments in the middle, then add them together to get the final result.The time complexity is O((n + q) log n), where n is the length of the array and q is the number of queries. The space complexity is O(n).
Python
Java
C++
Go
TypeScript
| 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 |
Q4. Count Stable Subarrays || Easy 1-d DP Approach || Leetcode Weekly Contest 476 || Watch 2X 🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 1,075 views views
Watch 6 more video solutions →Practice Count Stable Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor