3748. Count Stable Subarrays

HardArrayBinary SearchPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A subarray of nums is called stable if it contains no inversions. In other words, there is no pair of indices i < j within the subarray such that nums[i] > nums[j]. This effectively means the elements of a stable subarray are arranged in non-decreasing order.

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], you need to 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 i-th query.

Note:

A single element subarray is always considered stable.
For a contiguous run of k elements that are all non-decreasing, the number of stable subarrays it contributes is (1 + k) * k / 2, since every subarray within a non-decreasing run is itself non-decreasing (and hence stable).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Checking feasibility with binary search works because the condition is monotonic.

Open in Flowchart

Intuition

The key observation is that a stable subarray is simply a subarray whose elements are in non-decreasing order. So instead of thinking about inversions, we can think about where the array "breaks" — that is, the positions where nums[r] > nums[r + 1].

These break points naturally split the whole array into several maximal non-decreasing segments. Within any one of these segments, every subarray is automatically stable, because all elements are already in non-decreasing order. For a segment of length k, the number of stable subarrays it contains is (1 + k) * k / 2 (counting all possible subarrays). Importantly, no stable subarray can ever cross a break point, since crossing it would introduce an inversion.

This means that if we precompute these segments once, we can answer each query efficiently. We record the starting index of each segment in an array seg, and we build a prefix sum array s that stores the cumulative count of stable subarrays across full segments. With these, every query reduces to figuring out which segments the range [l, r] touches.

For a query [l, r], there are two situations:

The range lies inside a single segment. Since the whole range is non-decreasing, the answer is just (1 + k) * k / 2 where k = r - l + 1.
The range spans multiple segments. Here we split the work into three parts:
- The left partial segment, from l up to the end of its segment — a non-decreasing run of length a, contributing (1 + a) * a / 2.
- The fully covered middle segments, whose total is obtained instantly from the prefix sum s using s[j] - s[i].
- The right partial segment, from the start of the last segment up to r — a non-decreasing run of length b, contributing (1 + b) * b / 2.
Adding these three pieces together gives the answer.

To quickly locate which segments a query falls into, we use binary search (bisect_right) on the seg array. This lets us find the boundaries i and j of the involved segments in O(log n) time, so each query is answered fast after the one-time preprocessing.

Pattern Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

We use the Segmented Counting technique combined with prefix sums and binary search to answer each query efficiently.

Step 1: Build the non-decreasing segments.

We scan through nums and detect the end of each maximal non-decreasing segment. A segment ends at index r when either r is the last index (r == n - 1) or the order breaks (nums[r] > nums[r + 1]).

We keep l as the start of the current segment.
When a segment [l, r] is completed, we push l into the array seg to record its starting position.
We compute the number of stable subarrays in this segment of length k = r - l + 1 using (1 + k) * k // 2, and accumulate it into the prefix sum array s. So s[i] stores the total count of stable subarrays over the first i complete segments.
Then we move l to r + 1 to begin the next segment.

s = [0]
l, n = 0, len(nums)
seg = []
for r, x in enumerate(nums):
    if r == n - 1 or x > nums[r + 1]:
        seg.append(l)
        k = r - l + 1
        s.append(s[-1] + (1 + k) * k // 2)
        l = r + 1

After this loop, seg holds the starting indices of all segments, and s is a prefix sum array aligned with seg.

Step 2: Answer each query with binary search.

For a query [l, r], we use bisect_right(seg, l) and bisect_right(seg, r) to locate the relevant segments:

i = bisect_right(seg, l) — the index of the first segment whose start is strictly greater than l. This marks where the fully covered middle segments begin.
j = bisect_right(seg, r) - 1 — the index of the last segment whose start is ≤ r. This is the segment containing r.

Case 1: i > j — the range lies within a single segment.

The entire range [l, r] is non-decreasing, so the answer is simply:

k = r - l + 1
ans.append((1 + k) * k // 2)

Case 2: i <= j — the range spans multiple segments.

We split the count into three parts:

Left partial segment: from l to just before seg[i], with length a = seg[i] - l, contributing (1 + a) * a // 2.
Middle full segments: the complete segments from index i to j - 1, counted instantly via the prefix sum as s[j] - s[i].
Right partial segment: from seg[j] to r, with length b = r - seg[j] + 1, contributing (1 + b) * b // 2.

a = seg[i] - l
b = r - seg[j] + 1
ans.append((1 + a) * a // 2 + s[j] - s[i] + (1 + b) * b // 2)

Complexity Analysis:

Time complexity: O(n + q * log n), where n is the length of nums and q is the number of queries. Building the segments takes O(n), and each query takes O(log n) due to the two binary searches.
Space complexity: O(n) for the seg and s arrays (excluding the output array).

This approach works because stable subarrays can never cross a break point, so precomputing per-segment counts lets us reuse work across all queries instead of recomputing from scratch.

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Input:

nums = [1, 3, 2, 2, 4]
queries = [[0, 4], [1, 3], [2, 4]]

Step 1: Build the non-decreasing segments

We scan through nums and break it into maximal non-decreasing runs. A segment ends whenever the next element is smaller (an inversion) or we reach the end of the array.

`r`	`nums[r]`	`nums[r+1]`	Break here?	Reason
0	1	3	No	`1 <= 3`
1	3	2	Yes	`3 > 2` (inversion)
2	2	2	No	`2 <= 2`
3	2	4	No	`2 <= 4`
4	4	—	Yes	last index

This produces three segments:

Segment 0: indices [0, 1] → [1, 3], length k = 2
Segment 1: indices [2, 4] → [2, 2, 4], length k = 3

Wait — let's recount. The break at r = 1 closes segment [0, 1]. The next segment starts at l = 2 and runs to r = 4 (no breaks in between), so it is [2, 4].

So we actually have two segments:

Segment	Range	Elements	Length `k`	Stable count `(1+k)*k/2`
0	[0,1]	[1, 3]	2	`(1+2)*2/2 = 3`
1	[2,4]	[2,2,4]	3	`(1+3)*3/2 = 6`

This gives us:

seg = [0, 2]          # starting index of each segment
s   = [0, 3, 9]       # prefix sums: s[0]=0, s[1]=3, s[2]=3+6=9

Step 2: Answer each query

Query [0, 4] — the full array:

i = bisect_right(seg, 0) = 1 (first segment start strictly > 0)
j = bisect_right(seg, 4) - 1 = 2 - 1 = 1 (last segment with start ≤ 4)

Since i (1) <= j (1), the range spans multiple segments. Split into three parts:

Left partial: a = seg[1] - 0 = 2 → (1+2)*2/2 = 3 (covers indices [0,1])
Middle full: s[1] - s[1] = 3 - 3 = 0 (no fully covered interior segments)
Right partial: b = 4 - seg[1] + 1 = 4 - 2 + 1 = 3 → (1+3)*3/2 = 6 (covers indices [2,4])

Answer = 3 + 0 + 6 = 9 ✅ (matches counting all 3 stable subarrays in [1,3] plus all 6 in [2,2,4])

Query [1, 3] — range nums[1..3] = [3, 2, 2]:

i = bisect_right(seg, 1) = 1
j = bisect_right(seg, 3) - 1 = 2 - 1 = 1

Since i (1) <= j (1), span multiple segments:

Left partial: a = seg[1] - 1 = 2 - 1 = 1 → (1+1)*1/2 = 1 (covers index [1], just the element 3)
Middle full: s[1] - s[1] = 0
Right partial: b = 3 - seg[1] + 1 = 3 - 2 + 1 = 2 → (1+2)*2/2 = 3 (covers indices [2,3] = [2,2])

Answer = 1 + 0 + 3 = 4 ✅

Let's verify by hand. Stable subarrays in [3, 2, 2]: [3], [2](idx2), [2](idx3), [2,2]. That's 4. The break at index 1→2 (3 > 2) correctly prevents any subarray from crossing it.

Query [2, 4] — range nums[2..4] = [2, 2, 4]:

i = bisect_right(seg, 2) = 2
j = bisect_right(seg, 4) - 1 = 2 - 1 = 1

Since i (2) > j (1), the range lies entirely within a single segment (Case 1):

k = 4 - 2 + 1 = 3 → (1+3)*3/2 = 6

Answer = 6 ✅ (every subarray of the non-decreasing run [2,2,4] is stable)

Final Result

ans = [9, 4, 6]

The key insight illustrated here: stable subarrays never cross a break point (like the 3 > 2 drop at index 1). By precomputing each segment's count and storing prefix sums, every query collapses into at most two binary searches plus a constant amount of arithmetic over a left partial run, the fully covered middle, and a right partial run.

Solution Implementation

1from bisect import bisect_right
2from typing import List
3
4
5class Solution:
6    def countStableSubarrays(
7        self, nums: List[int], queries: List[List[int]]
8    ) -> List[int]:
9        # prefix_counts[i] = total number of non-decreasing subarrays
10        # contained in the first i non-decreasing segments
11        prefix_counts = [0]
12        # seg_starts[k] = starting index of the k-th maximal non-decreasing segment
13        seg_starts = []
14
15        start, n = 0, len(nums)
16
17        # Split nums into maximal non-decreasing segments.
18        # A break occurs at r when r is the last index or nums[r] > nums[r + 1].
19        for r, x in enumerate(nums):
20            if r == n - 1 or x > nums[r + 1]:
21                seg_starts.append(start)
22                length = r - start + 1
23                # Number of subarrays inside a block of given length: length*(length+1)/2
24                prefix_counts.append(prefix_counts[-1] + (1 + length) * length // 2)
25                start = r + 1
26
27        ans = []
28        for left, right in queries:
29            # First segment whose start index is strictly greater than left.
30            i = bisect_right(seg_starts, left)
31            # Last segment whose start index is <= right.
32            j = bisect_right(seg_starts, right) - 1
33
34            if i > j:
35                # The query range [left, right] lies entirely within a single segment,
36                # so it is fully non-decreasing.
37                length = right - left + 1
38                ans.append((1 + length) * length // 2)
39            else:
40                # Partial left piece: from left up to the start of segment i.
41                left_len = seg_starts[i] - left
42                # Partial right piece: from the start of segment j to right.
43                right_len = right - seg_starts[j] + 1
44                # Combine: left partial + fully covered middle segments + right partial.
45                ans.append(
46                    (1 + left_len) * left_len // 2
47                    + prefix_counts[j] - prefix_counts[i]
48                    + (1 + right_len) * right_len // 2
49                )
50        return ans
51

1class Solution {
2    public long[] countStableSubarrays(int[] nums, int[][] queries) {
3        // segmentStarts: stores the starting index of each non-decreasing segment.
4        // A "segment" is a maximal run where nums[r] <= nums[r + 1].
5        List<Integer> segmentStarts = new ArrayList<>();
6
7        // prefixSum: prefix sum of the number of subarrays fully contained in
8        // each segment. prefixSum.get(i) = total subarrays over the first i segments.
9        // The leading 0 makes range queries (prefixSum[j] - prefixSum[i]) clean.
10        List<Long> prefixSum = new ArrayList<>();
11        prefixSum.add(0L);
12
13        int left = 0;
14        int n = nums.length;
15
16        // Split the array into maximal segments. A segment ends at index r when
17        // r is the last element, or the value drops (nums[r] > nums[r + 1]).
18        for (int right = 0; right < n; right++) {
19            if (right == n - 1 || nums[right] > nums[right + 1]) {
20                segmentStarts.add(left);
21
22                // Length of the current segment.
23                int length = right - left + 1;
24
25                // Number of subarrays within a length-k segment is k * (k + 1) / 2.
26                prefixSum.add(prefixSum.getLast() + (long) length * (length + 1) / 2);
27
28                // Move the left pointer to the start of the next segment.
29                left = right + 1;
30            }
31        }
32
33        long[] ans = new long[queries.length];
34
35        for (int q = 0; q < queries.length; q++) {
36            int queryLeft = queries[q][0];
37            int queryRight = queries[q][1];
38
39            // firstSegment: index of the first segment whose start is strictly
40            // greater than queryLeft. The segment containing queryLeft is
41            // firstSegment - 1.
42            int firstSegment = upperBound(segmentStarts, queryLeft);
43
44            // lastSegment: index of the last segment whose start is <= queryRight.
45            int lastSegment = upperBound(segmentStarts, queryRight) - 1;
46
47            if (firstSegment > lastSegment) {
48                // The query range [queryLeft, queryRight] lies entirely inside a
49                // single segment, so count all subarrays directly.
50                int length = queryRight - queryLeft + 1;
51                ans[q] = (long) length * (length + 1) / 2;
52            } else {
53                // The query spans multiple segments. Break it into three parts:
54
55                // 1) Partial head: from queryLeft up to the start of segment
56                //    firstSegment (the boundary of the first fully-covered segment).
57                int headLength = segmentStarts.get(firstSegment) - queryLeft;
58
59                // 2) Partial tail: from the start of segment lastSegment to queryRight.
60                int tailLength = queryRight - segmentStarts.get(lastSegment) + 1;
61
62                // 3) Middle: the segments fully covered between firstSegment and
63                //    lastSegment, obtained from the prefix-sum difference.
64                ans[q] = (long) headLength * (headLength + 1) / 2
65                        + prefixSum.get(lastSegment) - prefixSum.get(firstSegment)
66                        + (long) tailLength * (tailLength + 1) / 2;
67            }
68        }
69        return ans;
70    }
71
72    // Returns the index of the first element in the list strictly greater than target.
73    // If no such element exists, returns list.size().
74    private int upperBound(List<Integer> list, int target) {
75        int low = 0, high = list.size();
76        while (low < high) {
77            int mid = (low + high) >>> 1; // unsigned shift avoids overflow
78            if (list.get(mid) > target) {
79                high = mid;
80            } else {
81                low = mid + 1;
82            }
83        }
84        return low;
85    }
86}
87

1class Solution {
2public:
3    vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
4        int n = nums.size();
5
6        // segmentStarts[i] holds the starting index of the i-th maximal non-decreasing segment.
7        vector<int> segmentStarts;
8
9        // prefixCounts[i] holds the total number of subarrays contained
10        // within the first i complete segments.
11        // For a segment of length k, it contributes k*(k+1)/2 subarrays.
12        vector<long long> prefixCounts = {0};
13
14        // Scan the array and cut it into maximal non-decreasing runs.
15        int left = 0;
16        for (int right = 0; right < n; ++right) {
17            // A segment ends at the array's tail or right before a decrease.
18            if (right == n - 1 || nums[right] > nums[right + 1]) {
19                segmentStarts.push_back(left);
20                long long length = right - left + 1;
21                // Accumulate the subarray count of this segment.
22                prefixCounts.push_back(prefixCounts.back() + length * (length + 1) / 2);
23                left = right + 1; // Move to the start of the next segment.
24            }
25        }
26
27        vector<long long> answer;
28        answer.reserve(queries.size());
29
30        for (const auto& query : queries) {
31            int queryLeft = query[0];
32            int queryRight = query[1];
33
34            // firstInnerSeg: index of the first segment whose start is strictly
35            // greater than queryLeft (i.e. the first fully-contained segment on the left side).
36            int firstInnerSeg =
37                upper_bound(segmentStarts.begin(), segmentStarts.end(), queryLeft) - segmentStarts.begin();
38
39            // lastInnerSeg: index of the last segment whose start is <= queryRight
40            // (i.e. the last fully-contained segment on the right side).
41            int lastInnerSeg =
42                upper_bound(segmentStarts.begin(), segmentStarts.end(), queryRight) - segmentStarts.begin() - 1;
43
44            if (firstInnerSeg > lastInnerSeg) {
45                // The whole query range lies inside a single segment.
46                long long length = queryRight - queryLeft + 1;
47                answer.push_back(length * (length + 1) / 2);
48            } else {
49                // Left partial slice: from queryLeft up to the start of the first inner segment.
50                long long leftPartLength = segmentStarts[firstInnerSeg] - queryLeft;
51
52                // Right partial slice: from the start of the last inner segment to queryRight.
53                long long rightPartLength = queryRight - segmentStarts[lastInnerSeg] + 1;
54
55                // Combine the left partial part, the fully-contained segments
56                // (via prefix sums), and the right partial part.
57                long long total = leftPartLength * (leftPartLength + 1) / 2
58                                + prefixCounts[lastInnerSeg] - prefixCounts[firstInnerSeg]
59                                + rightPartLength * (rightPartLength + 1) / 2;
60
61                answer.push_back(total);
62            }
63        }
64
65        return answer;
66    }
67};
68

1/**
2 * Binary search: returns the leftmost index at which `target`
3 * could be inserted into the sorted array `arr` to keep it sorted.
4 * Equivalent to lodash's _.sortedIndex.
5 */
6function sortedIndex(arr: number[], target: number): number {
7    let low = 0;
8    let high = arr.length;
9    while (low < high) {
10        const mid = (low + high) >> 1;
11        if (arr[mid] < target) {
12            low = mid + 1;
13        } else {
14            high = mid;
15        }
16    }
17    return low;
18}
19
20function countStableSubarrays(nums: number[], queries: number[][]): number[] {
21    const n = nums.length;
22
23    // segStarts[i] holds the starting index of the i-th non-decreasing segment.
24    const segStarts: number[] = [];
25    // prefix[i] is the total number of non-decreasing subarrays
26    // contained in the first i segments (prefix[0] = 0).
27    const prefix: number[] = [0];
28
29    let segLeft = 0;
30    for (let r = 0; r < n; r++) {
31        // A segment ends at r when r is the last element
32        // or the value drops at the next position.
33        if (r === n - 1 || nums[r] > nums[r + 1]) {
34            segStarts.push(segLeft);
35            const len = r - segLeft + 1;
36            // A segment of length len yields len*(len+1)/2 subarrays.
37            prefix.push(prefix[prefix.length - 1] + (len * (len + 1)) / 2);
38            segLeft = r + 1;
39        }
40    }
41
42    const ans: number[] = [];
43    for (const [left, right] of queries) {
44        // First fully-contained segment: its start must be >= left,
45        // so we look for the insertion point of (left + 1).
46        const i = sortedIndex(segStarts, left + 1);
47        // Last fully-contained segment: its start must be <= right,
48        // so we take the insertion point of (right + 1) minus one.
49        const j = sortedIndex(segStarts, right + 1) - 1;
50
51        if (i > j) {
52            // The query range lies entirely inside a single segment;
53            // count all non-decreasing subarrays of that contiguous piece.
54            const len = right - left + 1;
55            ans.push((len * (len + 1)) / 2);
56        } else {
57            // Partial left piece: from `left` up to the start of segment i.
58            const leftLen = segStarts[i] - left;
59            // Partial right piece: from the start of segment j to `right`.
60            const rightLen = right - segStarts[j] + 1;
61            ans.push(
62                (leftLen * (leftLen + 1)) / 2 +    // subarrays in the left partial piece
63                prefix[j] - prefix[i] +            // full segments strictly between i and j
64                (rightLen * (rightLen + 1)) / 2    // subarrays in the right partial piece
65            );
66        }
67    }
68
69    return ans;
70}
71

Time and Space Complexity

Time Complexity: O((n + q) log n)

The algorithm consists of two main phases:

Preprocessing phase (building segments): The first loop iterates through all n elements of nums exactly once. For each element, it performs constant-time operations (comparisons, arithmetic, and appending to lists seg and s). Therefore, this phase takes O(n) time.
Query processing phase: The second loop iterates over all q queries. For each query, it performs two binary searches using bisect_right on the seg array. Since seg contains at most n elements, each bisect_right call costs O(log n). The remaining operations (array indexing into s, arithmetic for triangular number formulas) are all O(1). Thus, processing all queries takes O(q log n).

Combining both phases yields a total time complexity of O(n) + O(q log n) = O((n + q) log n), where n is the length of the array and q is the number of queries.

Space Complexity: O(n)

The algorithm uses several auxiliary data structures:

The prefix sum array s stores one entry per segment, plus an initial 0, requiring at most O(n) space.
The seg array stores the starting index of each segment, requiring at most O(n) space (in the worst case, every element forms its own segment).

The ans array holds the results for each query (O(q) space), but this is typically considered output space rather than auxiliary space. Excluding the output, the dominant auxiliary space usage comes from s and seg, giving a space complexity of O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misaligning `bisect_right` boundaries when a query starts exactly at a segment boundary

The most subtle bug in this solution lies in choosing bisect_right vs bisect_left for locating segments, and in correctly distinguishing the left partial piece from the fully covered middle pieces.

The code deliberately uses two different conventions for the two ends:

For left: i = bisect_right(seg_starts, left) — the first segment whose start is strictly greater than left.
For right: j = bisect_right(seg_starts, right) - 1 — the last segment whose start is ≤ right.

If you naively use bisect_left for the left endpoint instead, you break the logic when left lands exactly on a segment's start index.

Why it matters: Suppose left == seg_starts[k] (the query begins exactly at the start of segment k).

With bisect_right(seg_starts, left), you get i = k + 1, and the left partial length becomes seg_starts[k+1] - left, which is the full length of segment k. That whole segment is then counted as a "partial" piece — correct.
With bisect_left(seg_starts, left), you would get i = k, making the left partial length seg_starts[k] - left = 0, and then prefix_counts[j] - prefix_counts[i] would also start including segment k. Segment k gets counted incorrectly (its prefix-sum value uses the segment's full length, but left may sit anywhere inside it).

Solution: Stick consistently with the asymmetric pattern: bisect_right for left (so the segment containing left is always handled as the left partial piece), and bisect_right(...) - 1 for right (so the segment containing right is always handled as the right partial piece). This guarantees the left and right boundary segments are clipped to the query range, while only interior full segments are pulled from the prefix sum.

A quick sanity check to verify alignment:

# When left and right are in the same segment, i > j must hold,
# routing to the single-segment branch.
assert i > j or seg_starts[i] > left   # left segment always partial
assert i > j or seg_starts[j] <= right # right segment always partial

Pitfall 2: Counting the boundary segments twice when `i == j`

When the query spans exactly two adjacent segments such that the left partial and right partial both reference work near the same index, you must ensure the middle term prefix_counts[j] - prefix_counts[i] evaluates to 0 (or only counts strictly interior segments).

Because i points to the first fully covered middle segment and j points to the right boundary segment, the middle slice is [i, j) — it excludes segment j (handled as right partial) and starts after the left boundary segment (i-1, handled as left partial). When i == j, prefix_counts[j] - prefix_counts[i] == 0, so no middle segments exist and only the two partial pieces contribute — which is exactly right.

Solution: Trust the half-open interval [i, j). Do not add +1 to j or change to prefix_counts[j+1] - prefix_counts[i], which would double-count the right boundary segment (counting its full length once via the prefix sum and again via the clipped right_len).

Pitfall 3: Integer overflow / large counts

For a segment of length k, the count is k*(k+1)/2, which for k ≈ 10^5 reaches ~5 × 10^9 — exceeding 32-bit integer range. In languages like Java or C++, this requires long/long long for both the per-segment count and the prefix sums.

Solution: In Python this is automatic (arbitrary precision). In statically typed languages, declare prefix_counts and all intermediate products as 64-bit. Always compute (1 + length) * length as a 64-bit multiplication before dividing by 2.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering