LeetCode 1769: Minimum Number of Operations to Move All Balls to Each Box Solution

Master LeetCode problem 1769 (Minimum Number of Operations to Move All Balls to Each Box), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

Array String Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can iterate through the boxes and calculate the number of operations needed to move balls to each box. For each box, we calculate the total operations needed by iterating through all boxes and accumulating the distances to move balls to the current box. We can optimize this process by pre-calculating the total distances for all boxes to the left and right separately and then summing them up.

Initialize arrays prefixSumLeft and prefixSumRight to store the total distances to move balls to the left and right for each box respectively.
Iterate through the boxes from left to right and calculate the prefix sum of distances to the left for each box.
Iterate through the boxes from right to left and calculate the prefix sum of distances to the right for each box.
Finally, iterate through all boxes and calculate the total operations needed for each box by summing the distances to the left and right.

Time Complexity

The time complexity of this solution is O(n) where n is the number of boxes.

Space Complexity

The space complexity of this solution is O(n) for storing prefix sums.

Solution Code

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] prefixSumLeft = new int[n];
        int[] prefixSumRight = new int[n];
        
        int leftCount = 0, leftOps = 0;
        for (int i = 0; i < n; i++) {
            prefixSumLeft[i] = leftOps;
            leftCount += boxes.charAt(i) - '0';
            leftOps += leftCount;
        }
        
        int rightCount = 0, rightOps = 0;
        for (int i = n - 1; i >= 0; i--) {
            prefixSumRight[i] = rightOps;
            rightCount += boxes.charAt(i) - '0';
            rightOps += rightCount;
        }
        
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = prefixSumLeft[i] + prefixSumRight[i];
        }
        
        return answer;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1769 (Minimum Number of Operations to Move All Balls to Each Box)?

This page provides optimized solutions for LeetCode problem 1769 (Minimum Number of Operations to Move All Balls to Each Box) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1769 (Minimum Number of Operations to Move All Balls to Each Box)?

The time complexity for LeetCode 1769 (Minimum Number of Operations to Move All Balls to Each Box) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1769 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1769 in Java, C++, or Python.

Back to LeetCode Solutions