Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: You are given an integer array capacity. A subarray capacity[l..r] is considered stable if: Its length is at least 3. The first and last elements are each equal to the sum of all elements strictly between them (i.e., capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1]). Return an integer denoting the number of stable subarrays.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[9,3,3,3,9]
[1,2,3,4,5]
[-4,4,0,0,-8,-4]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
class Solution {
public long countStableSubarrays(int[] capacity) {
int n = capacity.length;
long[] s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + capacity[i - 1];
}
Map<Pair<Integer, Long>, Integer> cnt = new HashMap<>();
long ans = 0;
for (int r = 2; r < n; ++r) {
int l = r - 2;
cnt.merge(new Pair<>(capacity[l], capacity[l] + s[l + 1]), 1, Integer::sum);
ans += cnt.getOrDefault(new Pair<>(capacity[r], s[r]), 0);
}
return ans;
}
}
// Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
func countStableSubarrays(capacity []int) (ans int64) {
n := len(capacity)
s := make([]int64, n+1)
for i := 1; i <= n; i++ {
s[i] = s[i-1] + int64(capacity[i-1])
}
type key struct {
first int
second int64
}
cnt := make(map[key]int)
for r := 2; r < n; r++ {
l := r - 2
keyL := key{capacity[l], int64(capacity[l]) + s[l+1]}
cnt[keyL] += 1
keyR := key{capacity[r], s[r]}
ans += int64(cnt[keyR])
}
return
}
# Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
class Solution:
def countStableSubarrays(self, capacity: List[int]) -> int:
s = list(accumulate(capacity, initial=0))
n = len(capacity)
ans = 0
cnt = defaultdict(int)
for r in range(2, n):
l = r - 2
cnt[(capacity[l], capacity[l] + s[l + 1])] += 1
ans += cnt[(capacity[r], s[r])]
return ans
// Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
// class Solution {
// public long countStableSubarrays(int[] capacity) {
// int n = capacity.length;
// long[] s = new long[n + 1];
// for (int i = 1; i <= n; ++i) {
// s[i] = s[i - 1] + capacity[i - 1];
// }
// Map<Pair<Integer, Long>, Integer> cnt = new HashMap<>();
// long ans = 0;
// for (int r = 2; r < n; ++r) {
// int l = r - 2;
// cnt.merge(new Pair<>(capacity[l], capacity[l] + s[l + 1]), 1, Integer::sum);
// ans += cnt.getOrDefault(new Pair<>(capacity[r], s[r]), 0);
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #3728: Stable Subarrays With Equal Boundary and Interior Sum
function countStableSubarrays(capacity: number[]): number {
const n = capacity.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
s[i] = s[i - 1] + capacity[i - 1];
}
const cnt = new Map<string, number>();
let ans = 0;
for (let r = 2; r < n; r++) {
const l = r - 2;
const keyL = `${capacity[l]},${capacity[l] + s[l + 1]}`;
cnt.set(keyL, (cnt.get(keyL) || 0) + 1);
const keyR = `${capacity[r]},${s[r]}`;
ans += cnt.get(keyR) || 0;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.