Minimum number of operations to move all balls to each box

Array String Prefix Sum

90.1% acceptance

Feb 25, 2026

3118

139

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball. Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(boxes: String) -> Vec<i32> {
    let s = boxes.as_bytes();
    let n = s.len();
    let mut answer = vec![0i32; n];
    // Left pass: accumulate cost from balls on the left
    let mut balls = 0i32;
    let mut ops = 0i32;
    for i in 0..n {
      answer[i] += ops;
      if s[i] == b'1' { balls += 1; }
      ops += balls;
    }
    // Right pass: accumulate cost from balls on the right
    balls = 0;
    ops = 0;
    for i in (0..n).rev() {
      answer[i] += ops;
      if s[i] == b'1' { balls += 1; }
      ops += balls;
    }
    answer
  }
}