Find the smallest balanced index

Array Prefix Sum

19.1% acceptance

Mar 15, 2026

You are given an integer array nums. An index i is balanced if the sum of elements strictly to the left of i equals the product of elements strictly to the right of i. If there are no elements to the left, the sum is considered as 0. Similarly, if there are no elements to the right, the product is considered as 1. Return an integer denoting the smallest balanced index. If no balanced index exists, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_balanced_index(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // Right product can overflow with nums[i] up to 10^9 and n up to 10^5.
    // Left sum max = 10^9 * 10^5 = 10^14, fits i64.
    // Right product can be astronomically large. We need to handle overflow.
    // If right product exceeds max possible left sum (which is at most ~10^14),
    // we can cap it and skip.

    let max_sum: i64 = nums.iter().map(|&x| x as i64).sum();

    // Compute suffix products, capping at max_sum + 1 to detect overflow
    let mut right_prod: Vec<i64> = vec![0; n + 1];
    right_prod[n] = 1;
    for i in (0..n).rev() {
      let p = right_prod[i + 1];
      if p > max_sum {
        right_prod[i] = max_sum + 1; // sentinel: too large
      } else {
        let val = p.checked_mul(nums[i] as i64).unwrap_or(max_sum + 1);
        right_prod[i] = if val > max_sum { max_sum + 1 } else { val };
      }
    }

    let mut left_sum: i64 = 0;
    for i in 0..n {
      let rp = if i + 1 <= n { right_prod[i + 1] } else { 1 };
      if left_sum == rp {
        return i as i32;
      }
      left_sum += nums[i] as i64;
    }
    -1
  }
}