Using the minimum number of operations, move all balls to the ith box.

Answer

This interview question concentrates on using JavaScript operations within arrays.

There are n boxes. You are given binary string boxes of length n. If boxes[i] is â€œ1â€, it means the ith box contains 1 ball, and If boxes[i] is â€œ0â€, it means the ith box does not contain any ball.
In one operation, you can move a ball from one box to one of its adjacent boxes. So if the ball is currently in the ith box, you can move it to either (i + 1)st box or (i - 1)st box. Note that, after doing so, some boxes may have more than 1 ball.
Return an array result of size n, where result[i] is the minimum number of operations required to move all the balls to the ith box.

/*Example*/

boxes = "110"
expected output = [1, 1, 3]
0th box:- one operation needed to move the ball from the second box.
1st box:- one operation needed to move the ball from the first box.
2nd box:- two operations needed to move the ball from the first box, and one operation needed to move the ball from the second box.

boxes = "001011"
expected output = [11, 8, 5, 4, 3, 4]

Solution:

We can do it in two passes:

â— In the first pass, for the ith box, we calculate the number of operations required to move all the balls from boxes left of the ith box.

So after the first pass, the result array for example 2 will be:
[0, 0, 0, 1, 2, 4]

The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the left side of the ith box.

â— In the second pass, for the ith box, we calculate the number of operations required to move all the balls from boxes right of the ith box.

So after the first pass, the result array for example 2 will be:
[11, 8, 5, 4, 1, 0]

The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the right side of the ith box.
Adding both the result arrays will give us the answer.

/**
 * @param {string} boxes
 * @return {number[]}
 */
function minimumOperations(boxes) {
    const n = boxes.length
    const result = new Array(n).fill(0)
    
    let ballsCount = 0
    let operationsCount = 0
    
    for (let i = 0; i < n; i++) {
        result[i] += operationsCount
        if (boxes[i] === "1") ballsCount++
        operationsCount += ballsCount
    }
    
    ballsCount = 0
    operationsCount = 0
    
    for (let i = n - 1; i >= 0; i--) {
        result[i] += operationsCount
        if (boxes[i] === "1") ballsCount++
        operationsCount += ballsCount
    }
    
    return result
}

Time complexity- O(n)
Space complexity- O(1)

Written by on May 22nd, 2021

Next Question

How to Answer: Using the minimum number of operations, move all balls to the ith box.

Advice and answer examples written specifically for a JavaScript Intermediate Level Arrays job interview.

2. Using the minimum number of operations, move all balls to the ith box.

This interview question concentrates on using JavaScript operations within arrays.

There are n boxes. You are given binary string boxes of length n. If boxes[i] is â€œ1â€, it means the ith box contains 1 ball, and If boxes[i] is â€œ0â€, it means the ith box does not contain any ball.
In one operation, you can move a ball from one box to one of its adjacent boxes. So if the ball is currently in the ith box, you can move it to either (i + 1)st box or (i - 1)st box. Note that, after doing so, some boxes may have more than 1 ball.
Return an array result of size n, where result[i] is the minimum number of operations required to move all the balls to the ith box.

/*Example*/

boxes = "110"
expected output = [1, 1, 3]
0th box:- one operation needed to move the ball from the second box.
1st box:- one operation needed to move the ball from the first box.
2nd box:- two operations needed to move the ball from the first box, and one operation needed to move the ball from the second box.

boxes = "001011"
expected output = [11, 8, 5, 4, 3, 4]

Solution:

We can do it in two passes:

â— In the first pass, for the ith box, we calculate the number of operations required to move all the balls from boxes left of the ith box.

So after the first pass, the result array for example 2 will be:
[0, 0, 0, 1, 2, 4]

The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the left side of the ith box.

â— In the second pass, for the ith box, we calculate the number of operations required to move all the balls from boxes right of the ith box.

So after the first pass, the result array for example 2 will be:
[11, 8, 5, 4, 1, 0]

The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the right side of the ith box.
Adding both the result arrays will give us the answer.

/**
 * @param {string} boxes
 * @return {number[]}
 */
function minimumOperations(boxes) {
    const n = boxes.length
    const result = new Array(n).fill(0)
    
    let ballsCount = 0
    let operationsCount = 0
    
    for (let i = 0; i < n; i++) {
        result[i] += operationsCount
        if (boxes[i] === "1") ballsCount++
        operationsCount += ballsCount
    }
    
    ballsCount = 0
    operationsCount = 0
    
    for (let i = n - 1; i >= 0; i--) {
        result[i] += operationsCount
        if (boxes[i] === "1") ballsCount++
        operationsCount += ballsCount
    }
    
    return result
}

Time complexity- O(n)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

Next Question