You are given an integer array capacity.
A subarray capacity[l..r] is considered stable if:
capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1]).Return an integer denoting the number of stable subarrays.
Example 1:
Input: capacity = [9,3,3,3,9]
Output: 2
Explanation:
[9,3,3,3,9] is stable because the first and last elements are both 9, and the sum of the elements strictly between them is 3 + 3 + 3 = 9.[3,3,3] is stable because the first and last elements are both 3, and the sum of the elements strictly between them is 3.Example 2:
Input: capacity = [1,2,3,4,5]
Output: 0
Explanation:
No subarray of length at least 3 has equal first and last elements, so the answer is 0.
Example 3:
Input: capacity = [-4,4,0,0,-8,-4]
Output: 1
Explanation:
[-4,4,0,0,-8,-4] is stable because the first and last elements are both -4, and the sum of the elements strictly between them is 4 + 0 + 0 + (-8) = -4
Constraints:
3 <= capacity.length <= 105-109 <= capacity[i] <= 109Problem Overview: You are given an integer array and must count subarrays where the sum of the two boundary elements equals the sum of all elements strictly inside the subarray. Formally, for subarray [l...r], the condition is nums[l] + nums[r] == sum(nums[l+1...r-1]). The challenge is evaluating this efficiently across all possible subarrays.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Enumerate every pair of indices (l, r) such that r - l >= 2 to ensure the subarray has interior elements. For each pair, iterate through the interior range l+1 to r-1 and compute its sum directly. Compare the interior sum with nums[l] + nums[r]. This approach is straightforward and useful for validating correctness during early development, but the triple nested iteration makes it too slow for large inputs.
Approach 2: Prefix Sum + Enumeration (O(n²) time, O(n) space)
Use a prefix sum array so the interior sum can be computed in constant time: interior = prefix[r] - prefix[l+1]. Then enumerate all valid boundary pairs (l, r) and check if nums[l] + nums[r] == interior. This removes the inner summation loop and reduces the complexity from cubic to quadratic. The approach is often acceptable for moderate input sizes and demonstrates a standard optimization technique used in many array problems.
Approach 3: Prefix Sum + Hash Table + Enumeration (O(n) time, O(n) space)
The equality condition can be rearranged algebraically. Since nums[l] + nums[r] = prefix[r] - prefix[l+1], move terms to get prefix[l+1] + nums[l] = prefix[r] - nums[r]. Now the expression on the left depends only on l, and the right side depends only on r. While scanning the array, maintain a hash table that counts values of prefix[l+1] + nums[l] for valid left boundaries. For each index r, compute prefix[r] - nums[r] and look it up in the map to find how many matching l values exist. To enforce the interior constraint (r - l ≥ 2), only insert index l = r - 2 into the map as the scan progresses. Each step performs constant-time hash lookups and updates, producing a linear-time solution.
Recommended for interviews: Start with the prefix-sum enumeration idea to demonstrate you understand how to convert range sums into constant-time queries. Then derive the algebraic transformation that enables the array scan with a hash table. Interviewers typically expect the final O(n) solution because it shows you can combine prefix sums, hash-based counting, and algebraic manipulation to eliminate nested loops.
We define a prefix sum array s, where s[i] represents the sum of the first i elements in the array capacity, that is, s[i] = capacity[0] + capacity[1] + ldots + capacity[i-1]. Initially, s[0] = 0.
According to the problem statement, a subarray capacity[l..r] is a stable array if:
$
capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ldots + capacity[r - 1]
That is:
capacity[l] = capacity[r] = s[r] - s[l + 1]
We can enumerate the right endpoint r. For each r, we calculate the left endpoint l = r - 2, and store the information of the left endpoints that meet the condition in a hash table. Specifically, we use a hash table cnt to record the number of occurrences of each key-value pair (capacity[l], capacity[l] + s[l + 1]).
When we enumerate the right endpoint r, we can query the hash table cnt to get the number of left endpoints that meet the condition, that is, the number of occurrences of the key-value pair (capacity[r], s[r]), and add it to the answer.
The time complexity is O(n) and the space complexity is O(n), where n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n³) | O(1) | Conceptual baseline or verifying correctness on small inputs |
| Prefix Sum + Pair Enumeration | O(n²) | O(n) | When constraints allow quadratic solutions and you want simpler implementation |
| Prefix Sum + Hash Table | O(n) | O(n) | Optimal approach for large arrays using prefix sums and hash lookups |
Stable Subarrays With Equal Boundary and Interior Sum | LeetCode 3728 | Weekly Contest 473 • Sanyam IIT Guwahati • 2,530 views views
Watch 7 more video solutions →Practice Stable Subarrays With Equal Boundary and Interior Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor