Construct Quad Tree - Leetcode 427 - Python

[@yang5843]

NeetCode is killing it at explaining these problems!

[@fierce2321]

Great explanation. One thing I wanted to note - we dont have to use "isSame" on all elements, we can use recursive call output for that. Here is my solution with complexity O(n^2): class Solution: def construct(self, grid: List[List[int]]) -> 'Node': n = len(grid) def helper(rowSt, colSt, gridSize): if gridSize == 1: return Node(grid[rowSt][colSt], 1, None, None, None, None) childSize = gridSize//2 topLeft = helper(rowSt, colSt, childSize ) topRight = helper(rowSt, colSt+ childSize ,childSize ) bottomLeft = helper(rowSt+childSize, colSt ,childSize ) bottomRight = helper(rowSt+childSize, colSt+childSize ,childSize ) isLeaf = topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and topLeft.val == topRight.val and topLeft.val == bottomLeft.val and topLeft.val == bottomRight.val val = topLeft.val isLeafInt = 0 if isLeaf: isLeafInt = 1 topLeft,topRight,bottomLeft, bottomRight = None, None, None, None root = Node(val, 1 if isLeaf else 0, topLeft, topRight,bottomLeft, bottomRight ) # print(rowSt, colSt, gridSize, ":", root.isLeaf, root.val, topLeft.val, topRight.val,bottomLeft.val, bottomRight.val) return root root = helper(0,0,n) return root

[@ax5344]

The problem description looks likes an essay. I was totally blown away not even wanting to know what it tries to say. Thanks for doing videos on this sort of problems!

[@mouthearnose]

" I was totally blown away not even wanting to know what it tries to say. " So true 🥴😵‍💫 the description of the video made me go insance.

[@JtPark-j6g]

this problem seemed like impossible for me to solve but thanks to your explanations, i was able to fully understand it and implement my own solution in java

[@ajins777]

This explanation was a lot more concise to the point and very articulate and easy to follow. I didn't know if you took my feedback, but if you did then, YOU the MAN!! ✨

[@akhma102]

Thank you so much, Neet. This was very helpful!

[@ferb7o2]

WOW, JUST WOW; had the idea in mind but had no clue how to convert it to code, as always THANK YOU!

[@plontulublalulu]

I didn’t understand this problem until watching this video. Thanks neetcode

[@matusklement5029]

You can actually speed this up to O(n^2) if you'll just check if all the children are leafs. If so, then we'll make a shortcut with their value if all children have that value same.

[@IOrangefriend]

Thanks! 1) First iteration is pointless - you compare value with its own 2) anyway if you want to check all values - it is python - just use any(grid[r][c] != grid[r+i][r+j] for j in range(n) for i in range(n))

[@m.kamalali]

Who else smashed like button before getting into video

[@firezdog]

My question for this one would be why the pruning is actually beneficial. If you don't prune but just use logic to figure out when to dump a recursive sub-result and when to use it, you will recurse until you visit ever square in the grid. But you excuse yourself the n^2 operation of scanning the sub-grid to see if it is the same. In the worst case you have to do all those scans and then you also have to recurse down to the individual cells. But in other cases the overhead for the recursive calls is worse. Still, wouldn't the theoretical big-O be better?

[@pro3757]

We can avoid checking for same values by using the output of the recursive call. Just return a flag if all children have same values. That way each cell is visited only once, taking time complexity down to n^2.

[@yaswanthkosuru]

practice and understanding others coding ==success

[@firezdog]

but in practice it doesn't seem this is more efficient (doesn't get you to the left in Leetcode's tests, even with successive tries to account for their inaccuracy) b/c the overhead for the recursive calls is terrible. Figuring out the exact flag can be a bit tricky too -- at least was for me. But it seems much more conceptually elegant.

[@vietnguyenquoc4948]

Sick explanation and implementation. I hope someday I can be as good as you in implementing the solution...

[@carantesferreira]

It would be really useful if put some disclaimers in the screen when you have this kind of typO ("n" instead of "i" or "j") , I was really frustrated trying to understand why you were adding "n" to the grid coordinates. Thanks for making such great videos with wonderful explanations

[@adityavats3990]

I think we can save the O(n^2) of checking whether quad is full of 0s or 1s.This can be precomputed just once in O(n^2)

[@unofficialshubham9026]

Hey, how we can precompute ? Please elaborate

[@MP-ny3ep]

Thank you , the problem statement was a bit hard to understand , your explanation was too good.

[@DarkMetroid777]

Super easy explanation, thanks!

[@sathwikmadhula9527]

For break statement inside 2 for loops,. Does it break both the for loops or only one ?

[@cesarroa5484]

Do we have to check if the root can be divided?

[@ifychim3189]

Great explanation man thank you !!!

[@roywastaken]

here every day dude!

[@gottuparthiharichandana3381]

Good! But what is the use of this quad tree data structure. Like do we use it in real time implementations?

[@adithyasaish2122]

Amazing Explanation!

[@krateskim4169]

Awesome explanation

[@cinimodmil]

Thanks for this neet! Really neat! To everyone else: does anyone know why we wouldn't go out of bounds when we're adding i and j to r and c respectively i.e., if grid[r][c] != grid[r + i][c + j]? I printed it out n it looks okay doesnt seem to go out of bounds.

[@akashnegi913]

r , c - even though we are adding n at each recursive call, we are also diving it by 2 which will always be with 0, n range i, j - Bounded from 0 to n - 1

[@cinimodmil]

@Akash Negi Ah! Thank you akash!

[@mohithadiyal6083]

Helpful as usual 👍

[@viktoreidrien7110]

neat code indeed man, thank you

[@RV-qf1iz]

how to build logic like you can you make a video on that

[@yang5843]

class Solution { public Node construct(int[][] grid) { return dfs(grid,grid.length,0,0); } Node dfs(int[][] grid, int N, int n, int m) { boolean same = true; for (int i=0;i

[@GFC1337]

Just in time a day before my uber onsite

[@dojoPojo]

How was it ? Did you joined ? What type of ques were asked ?

[@GFC1337]

@@dojoPojo Onsite got canceled because the position got filled, then hiring froze for a bit. My recruiter then got laid off. Recently, however, I contacted a different recruiter and I was able to secure an onsite which should take place in a couple of weeks. Hopefully that doesn't get cancelled as well. Fortunately, my OA + tech screen results are valid for 6 months, which means they will be valid for about 2 more lol.

[@dojoPojo]

@@GFC1337 All the best !

[@alexl2512]

This is not the optimal solution. Recursively break down the block until there is one cell and compose the parent node is the way to go. It's a O(lgn) solution.