Push Dominoes - Leetcode 838 - Python

[@ygwg6145]

Great video! To avoid the worst case O(n^2) and get a pure O(n) solution, just find and handle intervals occupied by “.” in one pass using sliding window. This method passed all tests.

[@vdyb745]

Appreciate your posting these videos even with a full time job !! Awesome !!!

[@vinayakgandhi5690]

Great video as always! I approached the same way, it is pretty much Breadth First Search with time where we check the state for each passing second until there is no new falling domino. I was also surprised to not find this simple and intuitive approach in Leetcode official solution.

[@ANZalliance]

This is definitely a fun and interesting problem, thanks for the detailed thought process and continual commitment to helping out the community! :)

[@pekarna]

The other solution I thought of (I always pause and think one up) is: 1) Run through the string, identifying the clusters that will collapse together - the last R before the next L. 2) At the same time, mark the successive R's and .'s as R, and successive L's and .'s as L. 3) Collapse the identified clusters symmetrically. 4) Take care of the edges.

[@mdazharuddin4684]

Yes, I also thought the same sliding window type. This seems easier than the queue solution.

[@infiseem]

@@mdazharuddin4684 But how do you code that down. Even I thought this, but it is difficult to code it. Are you doing a binary search to find the index where 'R' is?

[@TragicGFuel]

@@infiseem no, no need to binary search, you just have two pointers, one finds a R or L, then the other starts moving to find the next R or L, once both are found subtract their indices to find out how many " . " Are in between, and then update them accordingly by moving the first pointer towards the second one, repeat and finish off by handling the edges

[@Phantom_G_G]

I code in java but to understand the gist I come to your channel. It's super fun bro.

[@numberonep5404]

A drawing really comes in handy in this problem! Thanks for your great explanation as always :)

[@CostaKazistov]

Perfect walkthrough of this interesting LC problem

[@avinashchaurasiya6497]

Excellent explanation keep it up

[@trivedikumarb]

you are the best and glad to find you...

[@theghostwhowalk]

Great explanation. Thanks!

[@rommeltito123]

Ahh....my early morning dose of code!

[@laurieho1931]

Nice! I forgot that Python does lazy evaluation so lines 16 and 17 don't throw an error, gonna start using thanks :)

[@stewartzayat7526]

Most languages I know have short circuit boolean expression evaluation, but otherwise eager evaluation - the only exception I can think of is haskell which uses lazy evaluation all around. Yes, you can work around it by using iterators in python and some built in functions are also lazy, but most things in python are strictly evaluated.

[@YT.Nikolay]

The ending is epic :D

[@kristinashiryaginasalini1626]

Excellent explanation!👏

[@siqb]

Hey. I find your videos amazing but I have to take exception to this one :p This is not the simplest solution mate. A simple parse where you identify the left and right "posts" i.e. dots between two alphabets and resolving what happens to them based on what's on each end is the simplest solution.

[@sylviawong6790]

Thanks for the great explanations. Can you please do leetcode 790 as well?

[@live8dog]

So we are defying physics?!

[@bigbussington4755]

yes

[@malkeetsapien4852]

Beautiful !

[@_7__716]

I'm using JavaScript and if i use an array to act as a queue always get tle. Any suggestions?

[@halahmilksheikh]

Same here. 41/43 cases passed due to TLE

[@halahmilksheikh]

I fixed it. Still very slow but passes. You can remove the direction in the array pushed into the queue. All you need is the index.

[@geekydanish5990]

Don't use js ;-}

[@vidro3]

What do you mean? Js is the best

[@play005517]

Brilliant solution! my first thought was actually to use a two-pointer solution (because I just bunged your videos discussing two-pointer 😋) it took O(n) time and O(1) space (the algorithm is in place by nature, but in python or other immutable string you kind of forced to convert to an array of characters) the idea is very simple, just three lines: 1) the fast pointer stops when it encounters either R or L. 2) If it's an R, move the slow pointer here and find the next R or L; If its an R again or the end of string, fill the gap with Rs, else move to the next iteration. 3) If it's an L, check if the slow pinter is a dot, if so fill the gap with Ls; if the slow pinter is an R, fill the gap with Rs and Ls, and potentially a middle dot. class Solution: def pushDominoes(self, dominoes: str) -> str: dominoes = list(dominoes) slow, fast = 0, 0 while fast < len(dominoes): if dominoes[fast] == "R": # R...L # R.R.R # RR... # "R...." slow = fast fast += 1 while fast < len(dominoes) and dominoes[fast] == ".": fast += 1 if ( fast == len(dominoes) # end of string or fast < len(dominoes) and dominoes[fast] == "R" ): # R.... fast == len(dominoes) # R...R dominoes[fast] == "R" # RR... dominoes[fast] == "R" dominoes[slow:fast] = ["R"] * (fast - slow) slow = fast # else: # R...L will be addressed in the next iteration elif dominoes[fast] == "L": if dominoes[slow] == "R": # if (fast - slow) % 2 == 0 # .R...L. # 0123456 # 5 - 1 = 4 # there will be a middle domino # otherwise # .R..L. # 012345 # 4 - 1 = 3 # so there will be no middle domino middle = int((fast - slow) % 2 == 0) dominoes[slow + 1 : fast] = ( ["R"] * ((fast - slow) // 2 - middle) + ["."] * middle + ["L"] * ((fast - slow) // 2 - middle) ) slow = fast + 1 fast += 1 else: # L...L # ....L dominoes[slow:fast] = ["L"] * (fast - slow) slow = fast + 1 fast += 1 else: # . fast += 1 return "".join(dominoes)

[@realbillnye]

Hey neet, what would be the intuition when we first see this problem, that we should think of using a queue? What came to my mind was recursion but definitely not the idea of a queue.

[@michael-pasquale]

You know every L or R domino could knock down its neighbor in the first second, so you need to check these dominoes first. Everything in the initial queue represents the first second of L/R dominos to check. If a dominos knocks down its neighbor, that means you’ll have to check this domino in the next second, after first checking all dominoes in the current second. Put this newly knocked down domino in the back of the queue so you’ll check it later. The queue is helpful in keeping the dominoes you check in order by second. In general, a queue is useful for processing work (in this case, looking at a tilted domino and it’s neighbor) in a certain order.

[@numberonep5404]

Personally, when i see TONS of rules I just know it's either a sliding window problem or stack/queue problem, cause the description is literally trying to describe a somewhat complexe model for something thats kinda "alive" or "moving"... Ofc starting with the brute force is the best option if there is nothing too obvious and it is certainly useful to translate the rules described in code :)

[@SANJAYSINGH-jt4hf]

Java Soln: class Solution { public String pushDominoes(String dominoes) { ArrayDeque que = new ArrayDeque(); char [] list = dominoes.toCharArray(); for(int i=0;i0 && list[index-1]=='.'){ que.add(new Pair(index-1,'L')); list[index-1]='L'; } else if(ch=='R' && index+1

[@amandubey5287]

The video ended abruptly Was that only for me ?

[@sakshamp4488]

i wasnt able to pass 5 t.c , neetcode always makes me think that i am kind of stupid.

[@vudat1710]

Do I watch him too much so we came up with exactly the same solution?

[@vietha9165]

how about finding the standing dominoes?

[@marcelohuerta2727]

do you use any AI algorith?

[@abhicasm9237]

lol best ending

[@杨熙-v6v]

Java version solution, only need to save the index of each domino in the queue. class Solution { public String pushDominoes(String dominoes) { Queue queue = new LinkedList(); char[] chars = dominoes.toCharArray(); for (int i = 0; i < chars.length; i++) { if (chars[i] != '.') { // init status queue.offer(i); } } while (!queue.isEmpty()) { // simulate status iteration int idx = queue.poll(); char domino = chars[idx]; if (domino == 'L' && idx > 0 && chars[idx - 1] == '.') { // adjacent left domino just fall left chars[idx - 1] = 'L'; queue.offer(idx - 1); // update next iteration status } if (domino == 'R') { // right falling should judge if there is counteraction if (idx + 1 < chars.length && chars[idx + 1] == '.') { if (idx + 2 < chars.length && chars[idx + 2] == 'L') { // there is counteraction queue.poll(); // we should pop the left falling domino. } else { chars[idx + 1] = 'R'; queue.offer(idx + 1); // update next iteration status } } } } return String.valueOf(chars); } }

[@brahm_and_coding]

return "".join(dominoes) missed