Stable subarrays with equal boundary and interior sum

Array Hash Table Prefix Sum

25.9% acceptance

Feb 24, 2026

168

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[r-1]). Return an integer denoting the number of stable subarrays.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_stable_subarrays(capacity: Vec<i32>) -> i64 {
    let n = capacity.len();
    // Build prefix sums
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + capacity[i] as i64;
    }
    let mut count = 0i64;
    // For each pair l, r with r >= l+2:
    // capacity[l] == capacity[r] == prefix[r] - prefix[l+1]
    // i.e., capacity[l] == interior_sum AND capacity[r] == interior_sum
    // Group by value of capacity[l]. For each l, add to a map: key=capacity[l], value=prefix[l+1]
    // For each r, check if capacity[r] = interior_sum and if prefix[l+1] = prefix[r] - capacity[r]
    // i.e., prefix[l+1] = prefix[r] - capacity[r]
    // So for r, we need count of l < r-1 such that: capacity[l] == capacity[r] AND prefix[l+1] == prefix[r] - capacity[r]
    use std::collections::HashMap;
    // Map from (value, prefix_after_l) -> count
    let mut map: HashMap<(i64, i64), i64> = HashMap::new();
    for r in 2..n {
      // Add l = r-2 to map (r-2 is valid since r >= l+2 means l <= r-2)
      let l = r - 2;
      let key = (capacity[l] as i64, prefix[l + 1]);
      *map.entry(key).or_insert(0) += 1;
      // Query for current r
      let val_r = capacity[r] as i64;
      let needed_prefix_l1 = prefix[r] - val_r;
      let key_query = (val_r, needed_prefix_l1);
      count += map.get(&key_query).copied().unwrap_or(0);
    }
    count
  }
}