Count Stable Subarrays - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

HardArray Binary Search Prefix Sum12 min read

Practice this problem

Problem Statement

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] = [l_i, r_i] represents a query. For each query [l_i, r_i], compute the number of stable subarrays that lie entirely within the segment nums[l_i..r_i].

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 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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i] = [l_i, r_i]
0 <= l_i <= r_i <= 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:

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

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

Q4. Count Stable Subarrays || Easy 1-d DP Approach || Leetcode Weekly Contest 476 || Watch 2X 🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 1,138 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Count Stable Subarrays with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance33.0%

Approaches1

Reading time12 min