Skip to content

Latest commit

 

History

History
87 lines (64 loc) · 3.96 KB

026.md

File metadata and controls

87 lines (64 loc) · 3.96 KB

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

Difficulty: 🟡 Medium

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.

Examples:

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

Solutions

O(n^2) solution in Python3 (Naive approach)

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        length = len(boxes)
        result = []
        for i in range(length):
            count = 0
            for j in range(length):
                if i == j:
                    continue
                count += abs(j-i) * (1 if boxes[j] == "1" else 0)
            result.append(count)
        return result

The given solution calculates the minimum number of operations for each box by iterating through each box and counting the number of operations required to move all the balls to that box.

The algorithm works as follows:

  1. Initialize an empty array result to store the minimum number of operations for each box.
  2. Iterate through each box from left to right using the index i.
    • Initialize a variable count to 0 to keep track of the number of operations.
    • Iterate through each box from left to right using the index j.
      • If i is equal to j, skip the current iteration.
      • Calculate the distance between i and j using abs(j-i).
      • If the box at index j contains a ball ('1'), increment the count by the calculated distance.
    • Append the count to the result array.
  3. Return the result array, which contains the minimum number of operations for each box.

The algorithm calculates the minimum number of operations for each box by iterating through each box and counting the number of operations required to move all the balls to that box. It skips the current box during the inner loop and increments the count by the distance between the current and inner boxes if the inner box contains a ball.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n^2), where n is the length of the boxes string. The algorithm has a nested loop structure where it iterates through each box for each box, resulting in a quadratic time complexity.

The space complexity of the algorithm is O(n) as it uses additional space to store the result array, which has the same length as boxes.

Summary

The given solution calculates the minimum number of operations for each box by iterating through each box and counting the number of operations required to move all the balls to that box. It has a time complexity of O(n^2) and a space complexity of O(n), making it an efficient solution for the problem at hand. NB: If you want to get community points please suggest solutions in other languages as merge requests.