Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Count Stable Subarrays solution and explanation

HardArrayBinary SearchPrefix Sum6 min read31.9% acceptanceUpdated 24 Mar 2026
Practise Count Stable Subarrays
17:15
Q4. Count Stable Subarrays || Easy 1-d DP Approach || Leetcode Weekly Contest 476 || Watch 2X 🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 17:15 · 1K viewsWatch on YouTube
6 more videos on this problem
  1. Q4. Count Stable Subarrays || Easy 1-d DP Approach || Leetcode Weekly Contest 476 || Watch 2X 🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 17:15 · 1K views
  2. Leetcode 3748 🔥 Count Stable Subarrays | Weekly Contest 476 Q4 | Simple Array Approach | O(n) Time Study Placement · 27:09 · 395 views
  3. Leetcode 3748 | Count Stable SubarraysCodeWithMeGuys · 21:48 · 359 views
  4. 3748. Count Stable Subarrays (Leetcode Hard)Programming Live with Larry · 29:07 · 197 views
  5. LeetCode Weekly Contest 476: Problem 3748 – Count Stable SubarraysDesiCoding · 21:32 · 151 views
  6. Count Stable Subarrays - LeetCode 3748 | Best Intuition + Easy Approach #leetcode #leetcodesolutionCodehurdle · 37:04 · 32 views
  7. 3748. Count Stable Subarrays (LeetCode Hard)WYCode · 37:54 · 13 views

The problem

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:

  • A single element subarray is considered stable.

Example 1:

Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]

Output: [2,3,4]

Explanation:​​​​​

  • For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
    • The stable subarrays are [3] and [1]. The total number of stable subarrays is 2.
  • For queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
    • The stable subarrays are [1], [2], and [1, 2]. The total number of stable subarrays is 3.
  • For queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
    • The stable subarrays are [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:

  • For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
    • The stable subarrays are [2], [2], and [2, 2]. The total number of stable subarrays is 3.
  • For queries[1] = [0, 0], the subarray is [nums[0]] = [2].
    • The stable subarray is [2]. The total number of stable subarrays is 1.

Thus, ans = [3, 1].

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i] = [li, ri]
  • 0 <= li <= ri <= nums.length - 1

Approach overview

Problem 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.

Solution

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:

  1. The query interval [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.
  2. The query interval [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).

class Solution:
    def countStableSubarrays(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        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
        ans = []
        for l, r in queries:
            i = bisect_right(seg, l)
            j = bisect_right(seg, r) - 1
            if i > j:
                k = r - l + 1
                ans.append((1 + k) * k // 2)
            else:
                a = seg[i] - l
                b = r - seg[j] + 1
                ans.append((1 + a) * a // 2 + s[j] - s[i] + (1 + b) * b // 2)
        return ans
class Solution {
    public long[] countStableSubarrays(int[] nums, int[][] queries) {
        List<Integer> seg = new ArrayList<>();
        List<Long> s = new ArrayList<>();
        s.add(0L);

        int l = 0;
        int n = nums.length;
        for (int r = 0; r < n; r++) {
            if (r == n - 1 || nums[r] > nums[r + 1]) {
                seg.add(l);
                int k = r - l + 1;
                s.add(s.getLast() + (long) k * (k + 1) / 2);
                l = r + 1;
            }
        }

        long[] ans = new long[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int left = queries[q][0];
            int right = queries[q][1];

            int i = upperBound(seg, left);
            int j = upperBound(seg, right) - 1;

            if (i > j) {
                int k = right - left + 1;
                ans[q] = (long) k * (k + 1) / 2;
            } else {
                int a = seg.get(i) - left;
                int b = right - seg.get(j) + 1;
                ans[q] = (long) a * (a + 1) / 2 + s.get(j) - s.get(i) + (long) b * (b + 1) / 2;
            }
        }
        return ans;
    }

    private int upperBound(List<Integer> list, int target) {
        int l = 0, r = list.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (list.get(mid) > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
class Solution {
public:
    vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> seg;
        vector<long long> s = {0};

        int l = 0;
        for (int r = 0; r < n; ++r) {
            if (r == n - 1 || nums[r] > nums[r + 1]) {
                seg.push_back(l);
                long long k = r - l + 1;
                s.push_back(s.back() + k * (k + 1) / 2);
                l = r + 1;
            }
        }

        vector<long long> ans;
        for (auto& q : queries) {
            int left = q[0], right = q[1];

            int i = upper_bound(seg.begin(), seg.end(), left) - seg.begin();
            int j = upper_bound(seg.begin(), seg.end(), right) - seg.begin() - 1;

            if (i > j) {
                long long k = right - left + 1;
                ans.push_back(k * (k + 1) / 2);
            } else {
                long long a = seg[i] - left;
                long long b = right - seg[j] + 1;
                ans.push_back(a * (a + 1) / 2 + s[j] - s[i] + b * (b + 1) / 2);
            }
        }

        return ans;
    }
};
function countStableSubarrays(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const seg: number[] = [];
    const s: number[] = [0];

    let l = 0;
    for (let r = 0; r < n; r++) {
        if (r === n - 1 || nums[r] > nums[r + 1]) {
            seg.push(l);
            const k = r - l + 1;
            s.push(s[s.length - 1] + (k * (k + 1)) / 2);
            l = r + 1;
        }
    }

    const ans: number[] = [];
    for (const [left, right] of queries) {
        const i = _.sortedIndex(seg, left + 1);
        const j = _.sortedIndex(seg, right + 1) - 1;

        if (i > j) {
            const k = right - left + 1;
            ans.push((k * (k + 1)) / 2);
        } else {
            const a = seg[i] - left;
            const b = right - seg[j] + 1;
            ans.push((a * (a + 1)) / 2 + s[j] - s[i] + (b * (b + 1)) / 2);
        }
    }

    return ans;
}
func countStableSubarrays(nums []int, queries [][]int) []int64 {
	n := len(nums)
	seg := []int{}
	s := []int64{0}

	l := 0
	for r := 0; r < n; r++ {
		if r == n-1 || nums[r] > nums[r+1] {
			seg = append(seg, l)
			k := int64(r - l + 1)
			s = append(s, s[len(s)-1]+k*(k+1)/2)
			l = r + 1
		}
	}

	ans := make([]int64, len(queries))
	for idx, q := range queries {
		left, right := q[0], q[1]

		i := sort.SearchInts(seg, left+1)
		j := sort.SearchInts(seg, right+1) - 1

		if i > j {
			k := int64(right - left + 1)
			ans[idx] = k * (k + 1) / 2
		} else {
			a := int64(seg[i] - left)
			b := int64(right - seg[j] + 1)
			ans[idx] = a*(a+1)/2 + s[j] - s[i] + b*(b+1)/2
		}
	}

	return ans
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Good for understanding the stability condition and verifying small inputs
Prefix Sum + Binary SearchO(n log n)O(n)When the stability rule can be expressed using cumulative values and monotonic boundaries
Segmented Counting with Prefix AggregatesO(n log n)O(n)General scalable solution that counts valid prefix pairs instead of enumerating all subarrays

Frequently asked questions

Is Count Stable Subarrays easy or hard?

Count Stable Subarrays is generally considered a hard problem because it requires recognizing that subarray validation can be transformed into prefix relationships. Efficient solutions combine array processing, prefix sums, and binary search rather than straightforward iteration.

Count Stable Subarrays Python/Java solution

A typical Python or Java implementation computes prefix values and iterates through the array while searching previous prefixes using binary search. Each step counts how many earlier indices produce a stable subarray ending at the current position, leading to an O(n log n) algorithm.

How to solve Count Stable Subarrays in O(n)?

A pure O(n) solution is difficult unless the stability condition forms a strict monotonic constraint that allows a sliding window. Most implementations rely on prefix sums combined with binary search or ordered counting structures, resulting in O(n log n) time while keeping the logic manageable.

What is the best approach for Count Stable Subarrays?

Segmented counting using prefix sums and binary search is the most practical approach. It converts the problem into counting valid prefix relationships instead of checking every subarray. This reduces the complexity to O(n log n) with O(n) additional space, which works well for large arrays.

Is Count Stable Subarrays asked at Google/Amazon/Meta?

Problems involving subarray counting with prefix sums and binary search frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require counting valid ranges or prefix relationships are common in hard-level array interview questions.

What data structure is used in Count Stable Subarrays?

Typical solutions use prefix sum arrays combined with binary search over stored prefix states. Some implementations also rely on ordered containers or indexed structures to efficiently count valid prefix pairs while scanning the array.

What is the time complexity of Count Stable Subarrays?

The brute force approach runs in O(n^2) time because it evaluates every possible subarray. Optimized solutions using prefix sums and binary search reduce this to O(n log n) by quickly identifying valid boundaries or counting compatible prefix states.

Comments

Now write it yourselfClose this page and solve Count Stable Subarrays in the editor, without looking.
Practise Count Stable Subarrays