Leet Code — Minimum Number of Operations to Move All Balls to Each Box

This is an medium problem with the description being:

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.

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 ith 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:

1) First box: you will have to move one ball from the second box to the first box in one operation.

2) Second box: you will have to move one ball from the first box to the second box in one operation.

3) 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'.

This problem at first glance can be done by making two iterations first one accounting for the index that you want to check and the second is to gather where the pivot is, if is doable or not (1 or 0) and how many jumps would be needed using Math.abs to get the absolute number (positive) between first index and the second one.

Also you would want to skip the index that you are on the second iteration since there is no jump there.

class Solution {
    public int[] minOperations(String boxes) {

        final int[] result = new int[boxes.length()];

        for(int i=0;i<boxes.length();i++){

            int totalJumps = 0;

            for(int j=0;j<boxes.length();j++) {

                final char pivot = boxes.charAt(j);

                if(i==j || pivot == '0') continue; // ignoring pivot index when same or when zero

                // get how many jumps would be needed from the current index j and pivot index
                final int jumps = Math.abs(i-j); 

                totalJumps += jumps; // on total for that specific position
            }

            result[i] = totalJumps; // adding on result array
        }

        return result;
    }
}

Runtime: 157 ms, faster than 41.90% of Java online submissions for Minimum Number of Operations to Move All Balls to Each Box.

Memory Usage: 43.5 MB, less than 89.72% of Java online submissions for Minimum Number of Operations to Move All Balls to Each Box.

This works fine, but is not the one with most performance since there is two iterations, making quadratic on n operations, O(n²).

A better one, O(n) only, picks up on your brain, but is doable.

In this process what would will do is iterate the String and account for each of the indexes if they will jump or not, add on the result and on the next one you will use the previous information, aggregate on the next index and add up on the total amount of operations and so on.

But since you have to account for both sides of it (considering that when you are in the middle of the String) you will have to do for left and right side.

And this is what would look like:

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

        // moving from beggining to the end, accounting the left boxes
        for(int i=0,totalOperations=0,moves=0;i<boxes.length();i++){
            result[i] += totalOperations; // receiving the operations from previous moves
            moves += boxes.charAt(i)=='1' ? 1 : 0; // + an extra move if the current is one and will be movable
            totalOperations += moves; // adding the moves of this one on the total operation
        }


        // moving from end to beginning, accounting the right boxes
        for(int i=boxes.length()-1,totalOperations=0,moves=0;i>=0;i--){
            result[i] += totalOperations; // receiving the operations from previous moves
            moves += boxes.charAt(i)=='1' ? 1 : 0; // + an extra move if the current is one and will be movable
            totalOperations += moves; // adding the moves of this one on the total operation
        }

        return result;
    }
}

Runtime: 4 ms, faster than 82.31% of Java online submissions for Minimum Number of Operations to Move All Balls to Each Box.

Memory Usage: 43.7 MB, less than 79.84% of Java online submissions for Minimum Number of Operations to Move All Balls to Each Box.

Looks like bit weird, but try to use a paper to run manual tests, and understand each part of the process to get to know how this gets done.

It makes sense performance wise since you don’t have to iterate inside another iteration and one accounts for the left ones and the other right ones.

Also comparing the results, is way faster than the first one, so is worth to think about this when you get into a similar situation.

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)