Construct Quad Tree - Leetcode 427 - Python
VloĆŸit
- Äas pĆidĂĄn 27. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đ„· Discord: / discord
đŠ Twitter: / neetcode1
đź Support the channel: / neetcode
â BLIND-75 PLAYLIST: âą Two Sum - Leetcode 1 -...
đĄ DYNAMIC PROGRAMMING PLAYLIST: âą House Robber - Leetco...
Problem Link: leetcode.com/problems/constru...
0:00 - Read the problem
0:50 - Drawing Explanation
7:00 - Coding Explanation
leetcode 427
#neetcode #leetcode #python
NeetCode is killing it at explaining these problems!
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
WOW, JUST WOW; had the idea in mind but had no clue how to convert it to code, as always THANK YOU!
Super easy explanation, thanks!
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!! âš
Amazing Explanation!
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!
I didnât understand this problem until watching this video. Thanks neetcode
Helpful as usual đ
Awesome explanation
neat code indeed man, thank you
Great explanation man thank you !!!
Sick explanation and implementation. I hope someday I can be as good as you in implementing the solution...
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.
For break statement inside 2 for loops,. Does it break both the for loops or only one ?
here every day dude!
Who else smashed like button before getting into video
Thank you , the problem statement was a bit hard to understand , your explanation was too good.
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?
Good! But what is the use of this quad tree data structure. Like do we use it in real time implementations?
Do we have to check if the root can be divided?
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)
Hey, how we can precompute ? Please elaborate
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.
practice and understanding others coding ==success
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.
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
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.
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
@Akash Negi Ah! Thank you akash!
how to build logic like you can you make a video on that
Just in time a day before my uber onsite
How was it ?
Did you joined ? What type of ques were asked ?
@@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.
@@GFC1337 All the best !
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
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.