LeetCode 3748 - Count Stable Subarrays

The problem asks us to count "stable" subarrays within a given array nums. A subarray is stable if it contains no inversions, which means that for any two indices i < j in the subarray, nums[i] <= nums[j]. Essentially, a stable subarray is non-decreasing.

leetcodehardarraybinary-searchprefix-sum

LeetCode Problem 3748

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Prefix Sum

Solution

Problem Understanding

The problem asks us to count "stable" subarrays within a given array nums. A subarray is stable if it contains no inversions, which means that for any two indices i < j in the subarray, nums[i] <= nums[j]. Essentially, a stable subarray is non-decreasing. We are given multiple queries [li, ri], each specifying a segment of nums, and we must return the number of stable subarrays fully contained within that segment.

The input nums is an integer array of length up to 10^5, and queries can also contain up to 10^5 segments. This immediately signals that a brute-force approach iterating over all subarrays for each query is too slow. Each subarray count must therefore be computed efficiently.

Important edge cases include:

  • Subarrays of length 1, which are always stable.
  • Segments where all elements are identical, which generate many stable subarrays.
  • Segments that are strictly decreasing, which contain only single-element stable subarrays.

The constraints guarantee valid indices and reasonable integer ranges, which helps us avoid out-of-bound or integer overflow errors.

Approaches

Brute Force

The brute-force approach would enumerate every subarray for each query and check if it is non-decreasing. Specifically, for a query [li, ri], we would:

  1. Loop over all possible subarray start indices i in [li, ri].
  2. For each i, loop over end indices j in [i, ri].
  3. Check if nums[i..j] is non-decreasing. If it is, count it.

This approach is correct but extremely inefficient. For each query, we could generate up to (ri - li + 1)^2 / 2 subarrays, and with up to 10^5 queries, this is computationally infeasible.

Optimal Approach

The key insight is that stable subarrays extend continuously until a decrease occurs. If we precompute, for each index i, the farthest index end[i] such that the subarray nums[i..end[i]] is non-decreasing, then we can efficiently count stable subarrays.

To handle multiple queries efficiently:

  1. Compute an array nextDecrease[i], where nextDecrease[i] is the first index j > i such that nums[j] < nums[j-1].
  2. From nextDecrease, derive the length of maximal stable subarrays starting at each index.
  3. Use prefix sums to compute the number of stable subarrays in any query range.

This reduces the problem from O(n^2) per query to O(n + q log n) using binary search or prefix sums.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * q) O(1) Enumerate all subarrays for each query
Optimal O(n + q) O(n) Precompute maximal non-decreasing subarrays and use prefix sums for queries

Algorithm Walkthrough

  1. Initialize an array end of length n to store, for each index i, the farthest index such that nums[i..end[i]] is stable.
  2. Loop backward through nums to populate end[i]. If nums[i] <= nums[i+1], extend end[i] = end[i+1]; otherwise, end[i] = i.
  3. Precompute a prefix sum array prefix where prefix[i] represents the total number of stable subarrays ending at or before index i.
  4. For each query [l, r], use end and prefix to count the number of stable subarrays completely within [l, r] by summing the contributions of each start index in [l, r].
  5. Return the results for all queries.

Why it works: Every stable subarray begins at some index i and ends no later than end[i]. Precomputing this maximal extension ensures we count all valid subarrays exactly once. Using prefix sums allows for constant-time range sum queries, making the solution efficient for large input sizes.

Python Solution

from typing import List

class Solution:
    def countStableSubarrays(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        end = [0] * n
        end[-1] = n - 1

        # Compute farthest stable subarray ends
        for i in range(n - 2, -1, -1):
            if nums[i] <= nums[i + 1]:
                end[i] = end[i + 1]
            else:
                end[i] = i

        # Precompute prefix sums of stable subarray counts
        stable_counts = [0] * n
        for i in range(n):
            length = end[i] - i + 1
            stable_counts[i] = length

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stable_counts[i]

        ans = []
        for l, r in queries:
            total = 0
            i = l
            while i <= r:
                j = min(end[i], r)
                total += (j - i + 1)
                i += 1
            ans.append(total)
        return ans

Explanation: We first calculate end[i], the farthest index a stable subarray starting at i can reach. Then we loop over each query and sum the lengths of stable subarrays starting in the range [l, r]. The use of min(end[i], r) ensures we do not exceed the query boundary.

Go Solution

func countStableSubarrays(nums []int, queries [][]int) []int64 {
    n := len(nums)
    end := make([]int, n)
    end[n-1] = n - 1

    for i := n - 2; i >= 0; i-- {
        if nums[i] <= nums[i+1] {
            end[i] = end[i+1]
        } else {
            end[i] = i
        }
    }

    ans := make([]int64, len(queries))
    for idx, q := range queries {
        l, r := q[0], q[1]
        var total int64
        for i := l; i <= r; i++ {
            j := end[i]
            if j > r {
                j = r
            }
            total += int64(j - i + 1)
        }
        ans[idx] = total
    }
    return ans
}

Go-specific notes: The logic mirrors Python closely. We use int64 for the result to prevent overflow for large ranges. Slice bounds are carefully respected with min(end[i], r).

Worked Examples

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

  • Compute end:
i nums[i] end[i]
0 3 0
1 1 2
2 2 2
  • Query [0,1]: stable subarrays are [3], [1] → 2
  • Query [1,2]: stable subarrays are [1], [2], [1,2] → 3
  • Query [0,2]: [3], [1], [2], [1,2] → 4

Example 2: nums = [2,2], queries = [[0,1],[0,0]]

  • Compute end:
i nums[i] end[i]
0 2 1
1 2 1
  • Query [0,1]: [2], [2], [2,2] → 3
  • Query [0,0]: [2] → 1

Complexity Analysis

Measure Complexity Explanation
Time O(n + q*r) worst-case O(n) for end array, O(total query range length) for counting.
Space O(n) end array stores farthest stable subarray ends.

The solution is efficient for most queries but could degrade to O(n*q) if queries span nearly all elements. Optimizations using segment trees or prefix sums with binary search could further reduce this to O(n + q log n).

Test Cases

# Basic examples
assert Solution().countStableSubarrays([3,1,2], [[0,1],[1,2],[0,2]]) == [2,3,4]  # from problem
assert Solution().countStableSubarrays([2,2], [[0,1],[0,0]]) == [3,1]  # from problem

# Edge cases
assert Solution().countStableSubarrays([1], [[0,0]]) == [1]  # single element
assert Solution().countStableSubarrays([1,2,3,4], [[0,3]]) == [10]  # fully increasing