LC-1769 Medium LeetCode

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

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 90% Topics: Array, String, Prefix Sum

Reading material

Arrays & Hashing 12 min Strings 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def minOperations(self, boxes):
        """
        :type boxes: str
        :rtype: List[int]
        """
        result = [0]*len(boxes)
        for direction in (lambda x:x, reversed):
            cnt = accu = 0
            for i in direction(xrange(len(boxes))):
                result[i] += accu
                if boxes[i] == '1':
                    cnt += 1
                accu += cnt
        return result

Solution from kamyu104/LeetCode-Solutions · MIT