DevExCode

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

ArrayStringPrefix Sum

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.

View Leetcode Problem
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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question