We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Move All Balls to Each Box

Number: 1895

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, TikTok

Problem Description

Given a binary string where each character represents a box (with '1' indicating the presence of a ball and '0' for empty), determine an output array where each element at index i is the minimum number of operations needed to move all balls from their original positions to box i. In one operation, a ball can move to an adjacent box (i.e., from index j to j-1 or j+1).

Key Insights

  • For any target box, the cost is the sum of the absolute distances from every other box that contains a ball.
  • A naive approach would loop through each target box and each ball, leading to O(n^2) time complexity.
  • By performing two passes (one from the left and one from the right), we can efficiently calculate the cumulative operations required for each box in O(n) time.
  • In the left-to-right pass, keep track of the number of balls encountered so far and the cumulative cost needed to shift balls one position right.
  • Similarly, the right-to-left pass accumulates the cost of shifting balls left.
  • Combining both pass results in the desired answer.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (for the output array)

Solution

The solution uses a two-pass approach:

  1. First, traverse from left to right. As you move, maintain a counter of balls encountered (left_count) and a running cost (left_ops) which represents the cumulative moves required for all balls to reach that point. Assign left_ops to the answer array at each index before updating.
  2. Next, traverse from right to left with similar logic using right_count and right_ops. Accumulate the cost in the answer array.
  3. This results in each answer index containing the sum of operations needed from both directions to gather all balls at that index.

This approach avoids recalculating distances from scratch for each index by maintaining cumulative information, serving as a dynamic programming technique applied in two directions.

Code Solutions

# Python solution for the problem

def minOperations(boxes: str) -> [int]:
    n = len(boxes)
    answer = [0] * n

    # left-to-right pass: count operations required moving balls from left side
    left_count = 0      # number of balls encountered so far from the left
    left_ops = 0        # cumulative cost
    for i in range(n):
        # assign current cumulative left operations for the i-th box
        answer[i] = left_ops
        # if the current box contains a ball, increment left_count
        if boxes[i] == '1':
            left_count += 1
        # every ball seen so far will move one extra step for the next index
        left_ops += left_count

    # right-to-left pass: add operations required moving balls from right side
    right_count = 0     # number of balls encountered so far from the right
    right_ops = 0       # cumulative cost
    for i in range(n-1, -1, -1):
        # add current cumulative right operations for the i-th box
        answer[i] += right_ops
        # if current box contains a ball, increment right_count
        if boxes[i] == '1':
            right_count += 1
        # every ball seen so far will move one extra step for the previous index
        right_ops += right_count

    return answer

# Example usage:
#print(minOperations("110"))  # Expected output: [1, 1, 3]
← Back to All Questions