1class Solution {
2    /**
3     * Counts the number of "stable" subarrays.
4     * A subarray [left, right] (length >= 3) is stable when:
5     *   1. capacity[left] == capacity[right]
6     *   2. The sum of the elements strictly between them
7     *      (capacity[left+1] + ... + capacity[right-1]) equals capacity[left].
8     *
9     * Approach:
10     *   - Build a prefix sum array so any range sum is O(1).
11     *   - Sweep the right endpoint from left to right. For each candidate left
12     *     endpoint l (which must satisfy l <= r - 2), store a key describing
13     *     what a matching right endpoint must look like:
14     *         (capacity[l], capacity[l] + prefixSum[l + 1])
15     *     A right endpoint r matches when:
16     *         capacity[r] == capacity[l]                          (same boundary value)
17     *         prefixSum[r] == capacity[l] + prefixSum[l + 1]      (middle sum == boundary value)
18     *   - A hash map counts how many left endpoints produce each key, so each
19     *     right endpoint contributes the count of its matching key in O(1).
20     *
21     * Time complexity:  O(n)
22     * Space complexity: O(n)
23     */
24    public long countStableSubarrays(int[] capacity) {
25        int n = capacity.length;
26
27        // prefixSum[i] = sum of capacity[0 .. i-1]
28        long[] prefixSum = new long[n + 1];
29        for (int i = 1; i <= n; ++i) {
30            prefixSum[i] = prefixSum[i - 1] + capacity[i - 1];
31        }
32
33        // Maps the expected (boundaryValue, requiredPrefixSum) of a right endpoint
34        // to the number of left endpoints that demand it.
35        Map<Key, Integer> leftEndpointCount = new HashMap<>();
36
37        long answer = 0;
38
39        // The right endpoint must be at least index 2 so the subarray has length >= 3.
40        for (int right = 2; right < n; ++right) {
41            // The newly available left endpoint for this right endpoint.
42            int left = right - 2;
43
44            // Register the key a matching right endpoint must satisfy:
45            //   capacity[right] == capacity[left]
46            //   prefixSum[right] == capacity[left] + prefixSum[left + 1]
47            Key expectedKey = new Key(capacity[left], capacity[left] + prefixSum[left + 1]);
48            leftEndpointCount.merge(expectedKey, 1, Integer::sum);
49
50            // Count all left endpoints that pair with the current right endpoint.
51            Key currentKey = new Key(capacity[right], prefixSum[right]);
52            answer += leftEndpointCount.getOrDefault(currentKey, 0);
53        }
54
55        return answer;
56    }
57
58    /**
59     * Immutable composite key: the boundary value and the prefix sum
60     * a matching right endpoint must have.
61     */
62    private record Key(int boundaryValue, long requiredPrefixSum) {
63    }
64}
65

1// Custom hash functor so that std::pair<int, long long> can be used
2// as a key in an unordered_map.
3struct PairHash {
4    size_t operator()(const pair<int, long long>& p) const {
5        // Combine the hashes of both components; the shift reduces
6        // collisions between symmetric pairs.
7        return hash<int>()(p.first) ^ (hash<long long>()(p.second) << 1);
8    }
9};
10
11class Solution {
12public:
13    long long countStableSubarrays(vector<int>& capacity) {
14        int n = capacity.size();
15
16        // prefixSum[i] holds the sum of capacity[0 .. i-1].
17        // prefixSum[0] = 0 acts as the base case.
18        vector<long long> prefixSum(n + 1, 0);
19        for (int i = 1; i <= n; ++i) {
20            prefixSum[i] = prefixSum[i - 1] + capacity[i - 1];
21        }
22
23        // A subarray [l .. r] (length >= 3) is "stable" when:
24        //   1. capacity[l] == capacity[r]
25        //   2. The sum of the middle part capacity[l+1 .. r-1]
26        //      equals the boundary value capacity[l].
27        //
28        // The middle sum is prefixSum[r] - prefixSum[l + 1], so the
29        // condition rewrites to:
30        //   capacity[l] + prefixSum[l + 1] == prefixSum[r]
31        //
32        // For each left endpoint l we store the key
33        //   (capacity[l], capacity[l] + prefixSum[l + 1])
34        // and for each right endpoint r we look up the key
35        //   (capacity[r], prefixSum[r]).
36        unordered_map<pair<int, long long>, int, PairHash> keyCount;
37
38        long long answer = 0;
39
40        // The smallest valid right endpoint is index 2,
41        // since a stable subarray needs at least 3 elements.
42        for (int right = 2; right < n; ++right) {
43            // Register the newly available left endpoint (right - 2),
44            // which keeps a gap of at least one middle element.
45            int left = right - 2;
46            pair<int, long long> leftKey = {capacity[left],
47                                            capacity[left] + prefixSum[left + 1]};
48            keyCount[leftKey] += 1;
49
50            // Count all previously registered left endpoints that
51            // form a stable subarray with the current right endpoint.
52            pair<int, long long> rightKey = {capacity[right], prefixSum[right]};
53            auto it = keyCount.find(rightKey);
54            if (it != keyCount.end()) {
55                answer += it->second;
56            }
57        }
58
59        return answer;
60    }
61};
62

1/**
2 * Counts the number of "stable" subarrays in the given array.
3 *
4 * A subarray [l, r] (with at least 3 elements) is considered stable when:
5 *   1. capacity[l] === capacity[r]  (first and last elements are equal)
6 *   2. The sum of the elements strictly between l and r equals capacity[l].
7 *
8 * Approach:
9 *   - Build a prefix sum array so that prefixSum[i] = capacity[0] + ... + capacity[i - 1].
10 *   - The middle sum of subarray [l, r] is prefixSum[r] - prefixSum[l + 1].
11 *     The stability condition becomes:
12 *         capacity[l] === capacity[r]
13 *         capacity[l] + prefixSum[l + 1] === prefixSum[r]
14 *   - Sweep the right endpoint r from left to right. For each r, every index
15 *     l <= r - 2 has already been registered in a hash map keyed by the pair
16 *     (capacity[l], capacity[l] + prefixSum[l + 1]). Looking up the key
17 *     (capacity[r], prefixSum[r]) gives the number of valid left endpoints.
18 *
19 * Time complexity:  O(n) — single pass with O(1) map operations.
20 * Space complexity: O(n) — prefix sums and the hash map.
21 *
22 * @param capacity - The input array of numbers.
23 * @returns The total count of stable subarrays.
24 */
25function countStableSubarrays(capacity: number[]): number {
26    const n: number = capacity.length;
27
28    // prefixSum[i] holds the sum of the first i elements of capacity.
29    const prefixSum: number[] = Array(n + 1).fill(0);
30    for (let i = 1; i <= n; i++) {
31        prefixSum[i] = prefixSum[i - 1] + capacity[i - 1];
32    }
33
34    // Maps the composite key "value,value + prefixSum" of a candidate left
35    // endpoint to how many times that key has occurred so far.
36    const leftKeyCount: Map<string, number> = new Map<string, number>();
37
38    // Running total of stable subarrays found.
39    let answer: number = 0;
40
41    // Iterate over every possible right endpoint (subarray needs >= 3 elements).
42    for (let right = 2; right < n; right++) {
43        // The newest left endpoint that keeps a gap of at least one element.
44        const left: number = right - 2;
45
46        // Register the left endpoint's key:
47        // (capacity[left], capacity[left] + prefixSum[left + 1])
48        const leftKey: string = `${capacity[left]},${capacity[left] + prefixSum[left + 1]}`;
49        leftKeyCount.set(leftKey, (leftKeyCount.get(leftKey) ?? 0) + 1);
50
51        // Query with the right endpoint's key:
52        // (capacity[right], prefixSum[right])
53        // Every matching left endpoint forms one stable subarray.
54        const rightKey: string = `${capacity[right]},${prefixSum[right]}`;
55        answer += leftKeyCount.get(rightKey) ?? 0;
56    }
57
58    return answer;
59}
60