1769. Minimum Number of Operations to Move All Balls to Each Box - Explanation

Description

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i-th box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the i-th box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"

Output: [1,1,3]

Explanation: The answer for each box is as follows:

First box: you will have to move one ball from the second box to the first box in one operation.
Second box: you will have to move one ball from the first box to the second box in one operation.
Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"

Output: [11,8,5,4,3,4]

Constraints:

n == boxes.length
1 <= n <= 2000
boxes[i] is either '0' or '1'.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Traversal - Understanding how to iterate through arrays and compute cumulative values
Prefix Sums - The optimized solution uses prefix sums to efficiently calculate contributions from left and right
Two-Pass Technique - The optimal approach processes the array in two passes (left-to-right and right-to-left)

1. Brute Force

Intuition

For each box position, we want to know the total number of moves needed to bring all balls to that position. A move shifts a ball one position left or right. The cost to move a ball from position i to position pos is simply the absolute difference |pos - i|.

We can compute this directly by iterating through all boxes for each target position and summing up the distances from each ball.

Algorithm

Create a res array of size n.
For each target position pos:
- Iterate through all boxes.
- If box i contains a ball (value is '1'), add |pos - i| to res.
Return the res array.

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        res = [0] * n

        for pos in range(n):
            for i in range(n):
                if boxes[i] == '1':
                    res[pos] += abs(pos - i)

        return res

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res = new int[n];

        for (int pos = 0; pos < n; pos++) {
            for (int i = 0; i < n; i++) {
                if (boxes.charAt(i) == '1') {
                    res[pos] += Math.abs(pos - i);
                }
            }
        }

        return res;
    }
}

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> res(n, 0);

        for (int pos = 0; pos < n; pos++) {
            for (int i = 0; i < n; i++) {
                if (boxes[i] == '1') {
                    res[pos] += abs(pos - i);
                }
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} boxes
     * @return {number[]}
     */
    minOperations(boxes) {
        const n = boxes.length;
        const res = new Array(n).fill(0);

        for (let pos = 0; pos < n; pos++) {
            for (let i = 0; i < n; i++) {
                if (boxes[i] === '1') {
                    res[pos] += Math.abs(pos - i);
                }
            }
        }

        return res;
    }
}

public class Solution {
    public int[] MinOperations(string boxes) {
        int n = boxes.Length;
        int[] res = new int[n];

        for (int pos = 0; pos < n; pos++) {
            for (int i = 0; i < n; i++) {
                if (boxes[i] == '1') {
                    res[pos] += Math.Abs(pos - i);
                }
            }
        }

        return res;
    }
}

func minOperations(boxes string) []int {
    n := len(boxes)
    res := make([]int, n)

    for pos := 0; pos < n; pos++ {
        for i := 0; i < n; i++ {
            if boxes[i] == '1' {
                if pos > i {
                    res[pos] += pos - i
                } else {
                    res[pos] += i - pos
                }
            }
        }
    }

    return res
}

class Solution {
    fun minOperations(boxes: String): IntArray {
        val n = boxes.length
        val res = IntArray(n)

        for (pos in 0 until n) {
            for (i in 0 until n) {
                if (boxes[i] == '1') {
                    res[pos] += kotlin.math.abs(pos - i)
                }
            }
        }

        return res
    }
}

class Solution {
    func minOperations(_ boxes: String) -> [Int] {
        let n = boxes.count
        var res = [Int](repeating: 0, count: n)
        let chars = Array(boxes)

        for pos in 0..<n {
            for i in 0..<n {
                if chars[i] == "1" {
                    res[pos] += abs(pos - i)
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn min_operations(boxes: String) -> Vec<i32> {
        let n = boxes.len();
        let bytes = boxes.as_bytes();
        let mut res = vec![0; n];

        for pos in 0..n {
            for i in 0..n {
                if bytes[i] == b'1' {
                    res[pos] += (pos as i32 - i as i32).abs();
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output list.

2. Prefix Sum

Intuition

We can split the total cost for each position into contributions from the left and the right. For balls on the left, the cost is i * count_left - sum_of_indices_left. For balls on the right, the cost is sum_of_indices_right - i * count_right. Using prefix sums for both the count of balls and the sum of their indices, we can compute both parts efficiently.

Algorithm

Build two prefix arrays:
- prefix_count[i] = number of balls in boxes 0 to i-1.
- index_sum[i] = sum of indices of balls in boxes 0 to i-1.
For each position i:
- Left contribution: i * left_count - left_sum.
- Right contribution: right_sum - i * right_count.
- Add both to get the res for position i.
Return the res array.

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        res = [0] * n

        prefix_count = [0] * (n + 1)
        index_sum = [0] * (n + 1)
        for i in range(n):
            prefix_count[i + 1] = prefix_count[i] + (boxes[i] == '1')
            index_sum[i + 1] = index_sum[i] + (i if boxes[i] == '1' else 0)

        for i in range(n):
            left = prefix_count[i]
            left_sum = index_sum[i]

            right = prefix_count[n] - prefix_count[i + 1]
            right_sum = index_sum[n] - index_sum[i + 1]

            res[i] = (i * left - left_sum) + (right_sum - i * right)

        return res

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res = new int[n];
        int[] prefixCount = new int[n + 1];
        int[] indexSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixCount[i + 1] = prefixCount[i] + (boxes.charAt(i) == '1' ? 1 : 0);
            indexSum[i + 1] = indexSum[i] + (boxes.charAt(i) == '1' ? i : 0);
        }

        for (int i = 0; i < n; i++) {
            int left = prefixCount[i];
            int leftSum = indexSum[i];

            int right = prefixCount[n] - prefixCount[i + 1];
            int rightSum = indexSum[n] - indexSum[i + 1];

            res[i] = i * left - leftSum + (rightSum - i * right);
        }

        return res;
    }
}

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> res(n), prefixCount(n + 1, 0), indexSum(n + 1, 0);

        for (int i = 0; i < n; i++) {
            prefixCount[i + 1] = prefixCount[i] + (boxes[i] == '1' ? 1 : 0);
            indexSum[i + 1] = indexSum[i] + (boxes[i] == '1' ? i : 0);
        }

        for (int i = 0; i < n; i++) {
            int left = prefixCount[i];
            int leftSum = indexSum[i];
            int right = prefixCount[n] - prefixCount[i + 1];
            int rightSum = indexSum[n] - indexSum[i + 1];
            res[i] = i * left - leftSum + (rightSum - i * right);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} boxes
     * @return {number[]}
     */
    minOperations(boxes) {
        const n = boxes.length;
        const res = new Array(n).fill(0);
        const prefixCount = new Array(n + 1).fill(0);
        const indexSum = new Array(n + 1).fill(0);

        for (let i = 0; i < n; i++) {
            prefixCount[i + 1] = prefixCount[i] + (boxes[i] === '1' ? 1 : 0);
            indexSum[i + 1] = indexSum[i] + (boxes[i] === '1' ? i : 0);
        }

        for (let i = 0; i < n; i++) {
            const left = prefixCount[i];
            const leftSum = indexSum[i];
            const right = prefixCount[n] - prefixCount[i + 1];
            const rightSum = indexSum[n] - indexSum[i + 1];

            res[i] = i * left - leftSum + (rightSum - i * right);
        }

        return res;
    }
}

public class Solution {
    public int[] MinOperations(string boxes) {
        int n = boxes.Length;
        int[] res = new int[n];
        int[] prefixCount = new int[n + 1];
        int[] indexSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixCount[i + 1] = prefixCount[i] + (boxes[i] == '1' ? 1 : 0);
            indexSum[i + 1] = indexSum[i] + (boxes[i] == '1' ? i : 0);
        }

        for (int i = 0; i < n; i++) {
            int left = prefixCount[i];
            int leftSum = indexSum[i];
            int right = prefixCount[n] - prefixCount[i + 1];
            int rightSum = indexSum[n] - indexSum[i + 1];

            res[i] = i * left - leftSum + (rightSum - i * right);
        }

        return res;
    }
}

func minOperations(boxes string) []int {
    n := len(boxes)
    res := make([]int, n)
    prefixCount := make([]int, n+1)
    indexSum := make([]int, n+1)

    for i := 0; i < n; i++ {
        if boxes[i] == '1' {
            prefixCount[i+1] = prefixCount[i] + 1
            indexSum[i+1] = indexSum[i] + i
        } else {
            prefixCount[i+1] = prefixCount[i]
            indexSum[i+1] = indexSum[i]
        }
    }

    for i := 0; i < n; i++ {
        left := prefixCount[i]
        leftSum := indexSum[i]
        right := prefixCount[n] - prefixCount[i+1]
        rightSum := indexSum[n] - indexSum[i+1]

        res[i] = i*left - leftSum + (rightSum - i*right)
    }

    return res
}

class Solution {
    fun minOperations(boxes: String): IntArray {
        val n = boxes.length
        val res = IntArray(n)
        val prefixCount = IntArray(n + 1)
        val indexSum = IntArray(n + 1)

        for (i in 0 until n) {
            prefixCount[i + 1] = prefixCount[i] + if (boxes[i] == '1') 1 else 0
            indexSum[i + 1] = indexSum[i] + if (boxes[i] == '1') i else 0
        }

        for (i in 0 until n) {
            val left = prefixCount[i]
            val leftSum = indexSum[i]
            val right = prefixCount[n] - prefixCount[i + 1]
            val rightSum = indexSum[n] - indexSum[i + 1]

            res[i] = i * left - leftSum + (rightSum - i * right)
        }

        return res
    }
}

class Solution {
    func minOperations(_ boxes: String) -> [Int] {
        let n = boxes.count
        var res = [Int](repeating: 0, count: n)
        var prefixCount = [Int](repeating: 0, count: n + 1)
        var indexSum = [Int](repeating: 0, count: n + 1)
        let chars = Array(boxes)

        for i in 0..<n {
            prefixCount[i + 1] = prefixCount[i] + (chars[i] == "1" ? 1 : 0)
            indexSum[i + 1] = indexSum[i] + (chars[i] == "1" ? i : 0)
        }

        for i in 0..<n {
            let left = prefixCount[i]
            let leftSum = indexSum[i]
            let right = prefixCount[n] - prefixCount[i + 1]
            let rightSum = indexSum[n] - indexSum[i + 1]

            res[i] = i * left - leftSum + (rightSum - i * right)
        }

        return res
    }
}

impl Solution {
    pub fn min_operations(boxes: String) -> Vec<i32> {
        let n = boxes.len();
        let bytes = boxes.as_bytes();
        let mut res = vec![0i32; n];
        let mut prefix_count = vec![0i32; n + 1];
        let mut index_sum = vec![0i32; n + 1];

        for i in 0..n {
            let is_one = if bytes[i] == b'1' { 1 } else { 0 };
            prefix_count[i + 1] = prefix_count[i] + is_one;
            index_sum[i + 1] = index_sum[i] + if bytes[i] == b'1' { i as i32 } else { 0 };
        }

        for i in 0..n {
            let left = prefix_count[i];
            let left_sum = index_sum[i];
            let right = prefix_count[n] - prefix_count[i + 1];
            let right_sum = index_sum[n] - index_sum[i + 1];
            res[i] = i as i32 * left - left_sum + (right_sum - i as i32 * right);
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Prefix Sum (Optimal)

Intuition

Instead of storing prefix arrays, we can compute the contribution incrementally using two passes. In the left-to-right pass, we track how many balls are to the left and accumulate the moves needed to shift them one position right. In the right-to-left pass, we do the same for balls on the right. The sum of both passes gives the final answer.

Algorithm

Left-to-right pass:
- Track balls (count of balls seen) and moves (cumulative operations).
- For each position, res[i] = balls + moves, then update moves += balls and add current ball if present.
Right-to-left pass:
- Reset balls and moves.
- For each position from right to left, add balls + moves to res[i], then update similarly.
Return the res array.

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        res = [0] * n

        balls = moves = 0
        for i in range(n):
            res[i] = balls + moves
            moves += balls
            balls += int(boxes[i])

        balls = moves = 0
        for i in range(n - 1, -1, -1):
            res[i] += balls + moves
            moves += balls
            balls += int(boxes[i])

        return res

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res = new int[n];

        int balls = 0, moves = 0;
        for (int i = 0; i < n; i++) {
            res[i] = balls + moves;
            moves += balls;
            balls += boxes.charAt(i) - '0';
        }

        balls = moves = 0;
        for (int i = n - 1; i >= 0; i--) {
            res[i] += balls + moves;
            moves += balls;
            balls += boxes.charAt(i) - '0';
        }

        return res;
    }
}

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> res(n, 0);

        int balls = 0, moves = 0;
        for (int i = 0; i < n; i++) {
            res[i] = balls + moves;
            moves += balls;
            balls += boxes[i] - '0';
        }

        balls = moves = 0;
        for (int i = n - 1; i >= 0; i--) {
            res[i] += balls + moves;
            moves += balls;
            balls += boxes[i] - '0';
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} boxes
     * @return {number[]}
     */
    minOperations(boxes) {
        const n = boxes.length;
        const res = new Array(n).fill(0);

        let balls = 0,
            moves = 0;
        for (let i = 0; i < n; i++) {
            res[i] = balls + moves;
            moves += balls;
            balls += Number(boxes[i]);
        }

        balls = moves = 0;
        for (let i = n - 1; i >= 0; i--) {
            res[i] += balls + moves;
            moves += balls;
            balls += Number(boxes[i]);
        }

        return res;
    }
}

public class Solution {
    public int[] MinOperations(string boxes) {
        int n = boxes.Length;
        int[] res = new int[n];

        int balls = 0, moves = 0;
        for (int i = 0; i < n; i++) {
            res[i] = balls + moves;
            moves += balls;
            balls += boxes[i] - '0';
        }

        balls = moves = 0;
        for (int i = n - 1; i >= 0; i--) {
            res[i] += balls + moves;
            moves += balls;
            balls += boxes[i] - '0';
        }

        return res;
    }
}

func minOperations(boxes string) []int {
    n := len(boxes)
    res := make([]int, n)

    balls, moves := 0, 0
    for i := 0; i < n; i++ {
        res[i] = balls + moves
        moves += balls
        balls += int(boxes[i] - '0')
    }

    balls, moves = 0, 0
    for i := n - 1; i >= 0; i-- {
        res[i] += balls + moves
        moves += balls
        balls += int(boxes[i] - '0')
    }

    return res
}

class Solution {
    fun minOperations(boxes: String): IntArray {
        val n = boxes.length
        val res = IntArray(n)

        var balls = 0
        var moves = 0
        for (i in 0 until n) {
            res[i] = balls + moves
            moves += balls
            balls += boxes[i] - '0'
        }

        balls = 0
        moves = 0
        for (i in n - 1 downTo 0) {
            res[i] += balls + moves
            moves += balls
            balls += boxes[i] - '0'
        }

        return res
    }
}

class Solution {
    func minOperations(_ boxes: String) -> [Int] {
        let n = boxes.count
        var res = [Int](repeating: 0, count: n)
        let chars = Array(boxes)

        var balls = 0
        var moves = 0
        for i in 0..<n {
            res[i] = balls + moves
            moves += balls
            balls += chars[i] == "1" ? 1 : 0
        }

        balls = 0
        moves = 0
        for i in stride(from: n - 1, through: 0, by: -1) {
            res[i] += balls + moves
            moves += balls
            balls += chars[i] == "1" ? 1 : 0
        }

        return res
    }
}

impl Solution {
    pub fn min_operations(boxes: String) -> Vec<i32> {
        let n = boxes.len();
        let bytes = boxes.as_bytes();
        let mut res = vec![0i32; n];

        let mut balls = 0i32;
        let mut moves = 0i32;
        for i in 0..n {
            res[i] = balls + moves;
            moves += balls;
            balls += (bytes[i] - b'0') as i32;
        }

        balls = 0;
        moves = 0;
        for i in (0..n).rev() {
            res[i] += balls + moves;
            moves += balls;
            balls += (bytes[i] - b'0') as i32;
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output list.

Common Pitfalls

Character vs Integer Comparison

The input is a string where boxes contain '0' or '1' as characters, not integers. Comparing boxes[i] == 1 instead of boxes[i] == '1' will always evaluate to false in most languages, causing the algorithm to miss all balls.

Incorrect Order of Operations in Two-Pass

In the optimal prefix sum approach, the order of updating balls, moves, and res[i] matters. Adding the current ball before calculating the result will cause off-by-one errors where the ball at position i incorrectly contributes to its own cost.

Off-by-One in Left/Right Contribution Formula

When using the formula i * leftCount - leftSum for left contribution, using i + 1 or indexing errors in prefix arrays can shift all calculations. Carefully verify that prefix arrays are 0-indexed or 1-indexed and adjust formulas accordingly.