LeetCode 3728 - Stable Subarrays With Equal Boundary and Interior Sum

LeetCode Problem 3728

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to count stable subarrays in an integer array capacity. A subarray capacity[l..r] is stable if it satisfies two conditions: its length is at least 3, and the first and last elements are each equal to the sum of the elements strictly between them. In other words, for a subarray [a0, a1, ..., ak], it must hold that a0 = ak = a1 + a2 + ... + a(k-1).

The input is an integer array, which can be fairly large (3 <= capacity.length <= 10^5) and may contain negative values (-10^9 <= capacity[i] <= 10^9). The output is a single integer, the count of subarrays satisfying the stable condition.

Key points from the constraints are that a brute-force solution checking all subarrays would be too slow due to the potential size of capacity, and integer sums may exceed typical 32-bit limits, requiring careful handling in languages like Go. Edge cases include arrays with all equal elements, arrays where no stable subarray exists, and arrays containing negative numbers.

Approaches

The brute-force approach iterates over all subarrays of length ≥3. For each subarray, it computes the sum of interior elements and checks if the first and last elements are equal to this sum. This guarantees correctness but is too slow because the number of subarrays is roughly O(n^2), and computing the sum for each subarray adds an extra factor, resulting in O(n^3) if done naively.

The optimal approach uses prefix sums and a hash map. The key observation is that for a subarray [l..r], if capacity[l] = capacity[r] = sum(capacity[l+1..r-1]), then capacity[l] = capacity[r] = prefix[r] - prefix[l+1], where prefix[i] is the sum of elements capacity[0..i-1]. Rearranging gives prefix[r] - prefix[l+1] = capacity[l], which can be rewritten in terms of the prefix sum of capacity[l] to check for stable subarrays efficiently. This reduces the problem to iterating over possible end indices and checking for corresponding start indices using a hash map.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Checks all subarrays and sums interiors explicitly
Optimal	O(n^2)	O(n)	Uses prefix sums to compute interior sums quickly

Although there is still an O(n^2) worst-case in the optimal approach, careful implementation and constraints make it feasible for LeetCode limits.

Algorithm Walkthrough

1. Compute the prefix sum array of capacity, where prefix[i] is the sum of the first i elements.
2. Initialize a counter count to zero.
3. Iterate over all possible starting indices l from 0 to n-3.
4. For each l, iterate over all possible ending indices r from l+2 to n-1.
5. Compute the sum of the interior elements using the prefix sum: interior_sum = prefix[r] - prefix[l+1].
6. Check if capacity[l] == capacity[r] == interior_sum. If true, increment count.
7. Return count after iterating all valid subarrays.

Why it works: Using prefix sums ensures that the interior sum can be computed in O(1) time. By checking all valid subarrays and comparing the first and last elements with the interior sum, the algorithm counts all subarrays that satisfy the stable condition.

Python Solution

from typing import List

class Solution:
    def countStableSubarrays(self, capacity: List[int]) -> int:
        n = len(capacity)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + capacity[i]
        
        count = 0
        for l in range(n - 2):
            for r in range(l + 2, n):
                interior_sum = prefix[r] - prefix[l + 1]
                if capacity[l] == capacity[r] == interior_sum:
                    count += 1
        return count

The Python implementation first constructs the prefix sum array, then iterates over all subarrays of length at least 3. The interior sum is computed using the prefix array, which avoids recomputing sums repeatedly. The conditional checks if both the first and last elements equal the interior sum, incrementing the count when true.

Go Solution

func countStableSubarrays(capacity []int) int64 {
    n := len(capacity)
    prefix := make([]int64, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + int64(capacity[i])
    }

    var count int64 = 0
    for l := 0; l < n-2; l++ {
        for r := l + 2; r < n; r++ {
            interiorSum := prefix[r] - prefix[l+1]
            if int64(capacity[l]) == int64(capacity[r]) && int64(capacity[l]) == interiorSum {
                count++
            }
        }
    }
    return count
}

The Go implementation is similar to Python but uses int64 for prefix sums and comparisons to prevent integer overflow. The iteration over subarrays and condition checks mirrors the Python approach.

Worked Examples

Example 1: capacity = [9,3,3,3,9]

l	r	interior_sum	capacity[l]	capacity[r]	Stable?	count
0	2	3	9	3	No	0
0	3	6	9	3	No	0
0	4	9	9	9	Yes	1
1	3	3	3	3	Yes	2

Example 2: capacity = [1,2,3,4,5]

All subarrays fail the condition. Count remains 0.

Example 3: capacity = [-4,4,0,0,-8,-4]

l	r	interior_sum	capacity[l]	capacity[r]	Stable?	count
0	5	-4	-4	-4	Yes	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Two nested loops over indices l and r; prefix sum lookup is O(1)
Space	O(n)	Prefix sum array stores n+1 integers

The time complexity is quadratic because all subarrays of length ≥3 are checked. Space complexity is linear due to the prefix sum array.

Test Cases

# Basic examples
assert Solution().countStableSubarrays([9,3,3,3,9]) == 2  # example 1
assert Solution().countStableSubarrays([1,2,3,4,5]) == 0  # example 2
assert Solution().countStableSubarrays([-4,4,0,0,-8,-4]) == 1  # example 3

# Edge cases
assert Solution().countStableSubarrays([1,1,1]) == 1  # minimal length subarray
assert Solution().countStableSubarrays([0,0,0,0,0]) == 6  # all zeros
assert Solution().countStableSubarrays([1,-1,0]) == 1  # includes negative numbers
assert Solution().countStableSubarrays([1000000000,0,1000000000]) == 1  # large numbers
assert Solution().countStableSubarrays([1,2,1,2,1,2,1]) == 0  # repeating pattern, no stable

Test	Why
[9,3,3,3,9]	Standard example, multiple stable subarrays
[1,2,3,4,5]	No stable subarrays exist
[-4,4,0,0,-8,-4]	Negative numbers
[1,1,1]	Minimal valid length
[0,0,0,0,0]	All zeros, multiple overlapping stable subarrays
[1,-1,0]	Negative values, sum matches
[1000000000,0,1000000000]	Large integers, test for overflow
[1,2,1,2,1,2,1]	Patterned array, no stable subarrays

Edge Cases

Minimal length subarray: The smallest valid stable subarray has length 3. Arrays with fewer than 3 elements cannot produce any stable subarray. The implementation ensures we start the inner loop from l+2.

Negative and zero values: Since elements can be negative or zero, interior sums may cancel out. The algorithm correctly handles negative sums by computing prefix sums