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

0:00 - Read the problem
0:30 - Drawing Explanation
14:30 - Coding Explanation

leetcode 1769

#neetcode #leetcode #python

[FifaHades]

O(n) is the biggest enemy of the interview, great video!

[aadil]

I solved it in O(n) by myself without looking at the solution or watching this video. Without you, I wouldn't have gotten here. I used to struggle with even easy problems in the beginning, but you improved me. Thank you so much for your kindness!

[STACYEMMA-ye]

Did it in O(n^2), came here for O(n) solution

[soupayt]

Nice video! I didn't think of it as product of array except self, but you're correct that this is basically the same problem. I calculated the left side and right side prefix & suffix on the fly instead when building the solution array, but still the same!

class Solution:
def minOperations(self, boxes: str) -> List[int]:
# You can simplify this problem to keeping track of the distance between the current box and the boxes on the left and right with a non-zero
# amount of balls. We can use a running prefix sum to pull this off. We keep track of the number of 1's on the left and right sides and can adjust the left and right sums accordingly with that after each iteration.
boxes = [int(b) for b in boxes]
left = 0
right = 0
left_ones = 0
right_ones = 0
res = []

# precalculate right
for i, box in enumerate(boxes):
if box == 1:
right_ones += 1
right += i

for i, box in enumerate(boxes):
res.append(left + right)

if box == 1:
left_ones += 1
right_ones -= 1

left += left_ones
right -= right_ones
return res

[Kaviarasu_S]

I rewrote NeetCode's approch and I personally I find it more easy to understand
def minOperations(self, boxes: str) -> List[int]:
res = [0] * len(boxes)

balls, moves = 0, 0
for i in range(len(boxes)):
moves += balls
res[i] += moves
balls += int(boxes[i])

balls, moves = 0, 0
for i in range(len(boxes) - 1, -1, -1):
moves += balls
res[i] += moves
balls += int(boxes[i])

return res

[ramez]

Solved it in o(n^2) after that optimized it to o(n) and came here to see that i thought about it the same way neet did
seems hardwork and consistency pays off
thanks alot neet 🔥🔥

[AjayKumar-gssg]

Navdeep can you please explain solutions for yesterday's contest problems ? @neetcode

[indian_geocacher]

I have one question @Neetcode Can you please explain how did you know that the problem will be this one as you have published the solution at 00:00 as soon as the problem appeared, is it prerecorded for all the problems and you just post it?

[dixittilaji]

came here after solving a problem with a n^2 approach, I knew it there has to be optimized way haha, love your videos man!

[rode_atharva]

yesterday solved by myself using brute force. after listening that "you might be genius if you haven't seen the pattern and come up with the solution by yourself !". but i actually know the pattern of dynamic programming (so can't say am i genious or not 😅).. you are genoius. beacause of "you" and "codestory-with-mik" i am able to come at this level !
.... here is my solution

class Solution:
def minOperations(self, boxes: str) -> List[int]:
count = 0
ans_left = [0] * len(boxes)
ans_right = [0] * len(boxes)
for i in range(len(boxes)):
if i != 0:
ans_left[i] = ans_left[i-1] + count
if boxes[i] == '1':
count += 1
count = 0
for i in range(len(boxes)-1, -1, -1):
if i != len(boxes)-1:
ans_right[i] = ans_right[i+1] + count
if boxes[i] == '1':
count += 1
for i in range(len(ans_left)):
ans_left[i] += ans_right[i]

return ans_left

[sauravsingh]

Did somebody count how many times he said balls during the video

[sri_harsha_dv]

Explanation felt little confusing while building the right part of the array and in solution where moves should be updated before balls.

I was able to solve this problem surprisingly. Moves variable is not necessary atleast in the first array of your solution. My solution is one pass by building these left and right arrays. The intuition is that the right array is built using complete opposite steps of the left array. Only tricky part is understanding the indexing for the right array.

Solution:
def minOperations(self, boxes: str) -> List[int]:
length = len(boxes)
left, right = [0]*length, [0]*length
left_count = right_count = 0
for i in range(length):
if i:
left[i] = left[i-1]+left_count
right[length-i-1] = right[length-i]+right_count
if boxes[i] == "1":
left_count += 1
if boxes[length-i-1] == "1":
right_count += 1
return [l+r for l, r in zip(left, right)]

[Kaviarasu_S]

I think this problems solution approch is similar to Leetcode 135. Candy

[TheSmashten]

Hey Neetcode can you please do LC #37 (Sudoku Solver)? I can't even submit the editorial solutions for Python

[adilansari-hqge]

Recording on the eve of christmas, Big hug to you Bro, Thank you for all hthe ard work, effort, dedication and motivation.

[fdasfsadfsdfa]

Does it count as O(n) if, in this video, the problem is actually solved in O(n + n)?

[myyfstz]

thanks boss, but that's a fuckin magic you did, most of the vid i thought what is he talking about, but in the end it kinda all made sense

[andybnhquang]

How many days until that leetcode tshirt lol

[freecourseplatformenglish]

After solving yeserday's question this was a cakewalk.

[leechaolan]

like if you are here after finishing it with Brute force