Watch 8 video solutions for Stable Subarrays With Equal Boundary and Interior Sum, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Sanyam IIT Guwahati has 2,530 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |