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

Input: The input consists of a binary string `boxes` representing the state of boxes, where '0' means empty and '1' means a ball is present.

Example: boxes = '101'

Constraints:

• 1 <= n <= 2000

• boxes[i] is either '0' or '1'.

Output: Return an array `answer` where each `answer[i]` is the minimum number of operations needed to move all the balls to the ith box.

Example: Output: [1, 1, 2]

Constraints:

• The result should be an array of size `n`.

Goal: The goal is to calculate the minimum number of operations needed to move all balls to each box, considering the initial arrangement of the balls.

Steps:

• Initialize an array `res` to store the result, with initial values set to 0.

• For each box, calculate the total number of operations required to move the balls from all other boxes to this box.

• Optimize the solution by iterating over the string twice (once from left to right and once from right to left).

Goal: The problem involves calculating a minimum number of operations for each box, considering the input constraints.

Steps:

• 1 <= n <= 2000

• boxes[i] is either '0' or '1'.

Assumptions:

• The input string will always have at least one box (n >= 1).

• The input will contain only '0' or '1' characters.

• Input: boxes = '101'

• Explanation: In this case, we calculate the operations needed for each box: 1 for the first box, 1 for the second box, and 2 for the third box.

• Input: boxes = '001010'

• Explanation: Here, we calculate the number of operations for each box, considering how far the balls need to move.

Approach: The problem can be solved by calculating the minimum number of moves for each box by iterating over the string in both directions.

Observations:

• The problem requires calculating how many balls need to move to each box, considering their initial positions.

• Using two sweeps (left to right and right to left) allows us to calculate the operations in linear time.

Steps:

• Initialize an array `res` to hold the result.

• Iterate from left to right to accumulate the number of operations required to move balls to each box.

• Iterate from right to left to accumulate the number of operations required for the boxes in reverse order.

Empty Inputs:

• The input string will not be empty as per the problem constraints.

Large Inputs:

• The solution should efficiently handle strings of length up to 2000.

Special Values:

• If all boxes are empty, the result will be an array of zeros.

Constraints:

• The input will always be valid as per the problem constraints.

vector<int> minOperations(string boxes) {
    vector<int> res(boxes.length()); 
    for (int i = 0, ops = 0, cnt = 0; i < boxes.length(); ++i) {
        res[i] += ops;
        cnt += boxes[i] == '1' ? 1 : 0;
        ops += cnt;
    }
    for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {
        res[i] += ops;
        cnt += boxes[i] == '1' ? 1 : 0;
        ops += cnt;
    }
    return res;
}

1 : Function Definition

vector<int> minOperations(string boxes) {

Define the function `minOperations`, which takes a string `boxes` and returns a vector of integers. The vector represents the number of operations required for each box.

2 : Variable Initialization

    vector<int> res(boxes.length());

Initialize a result vector `res` with the size equal to the length of the `boxes` string. This vector will hold the number of operations for each box.

3 : Loop Initialization

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

Start the first loop to process the `boxes` string from left to right. Variables `ops` (operations counter) and `cnt` (count of balls encountered) are initialized to 0.

4 : Result Update

        res[i] += ops;

Update the result vector `res[i]` by adding the current number of operations (`ops`) for the current box `i`.

5 : Ball Count Update

        cnt += boxes[i] == '1' ? 1 : 0;

If the current box contains a ball ('1'), increment the counter `cnt` by 1.

6 : Operations Update

        ops += cnt;

Add the number of balls encountered so far (`cnt`) to the total number of operations (`ops`).

7 : Loop Initialization

    for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {

Start the second loop to process the `boxes` string from right to left. Re-initialize the `ops` and `cnt` variables.

8 : Result Update

        res[i] += ops;

Update the result vector `res[i]` by adding the current number of operations (`ops`) for the current box `i`.

9 : Ball Count Update

        cnt += boxes[i] == '1' ? 1 : 0;

If the current box contains a ball ('1'), increment the counter `cnt` by 1.

10 : Operations Update

        ops += cnt;

Add the number of balls encountered so far (`cnt`) to the total number of operations (`ops`).

11 : Return Statement

    return res;

Return the `res` vector, which contains the minimum operations required for each box.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: We iterate over the string twice (once from left to right and once from right to left), so the time complexity is O(n).

Best Case: O(n)

Worst Case: O(n)

Description: We use additional space for the result array, which stores the number of operations for each box.

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

Explore →