Construct Quad Tree | Leetcode 427 | Recursion

Timestamps:
Problem discussion: 00:00
Approach: 07:30
dry run: 09:41
code explanation:16:25
time and space complexity: 19:35
Optimized approach: 21:50
code explanation of optimized approach: 26:16

Time Complexity : O(n*n)
Space Complexity : O(logn)


Please like, share and subscribe if you found the video useful. Feel free to ask in comments section if you have any doubts. :)

#DataStructuresAndAlgorithms
#Leetcode
#interviewpreparation
#AyushiSharma
Construct Quad Tree solution
Construct Quad Tree Leetcode
Construct Quad Tree C++
Construct Quad Tree Java
Construct Quad Tree Python

🔥🔥🔥🔥👇👇👇

Checkout the series: 🔥🔥🔥
LIKE | SHARE | SUBSCRIBE 🔥🔥😊

[vasachisenjubean]

I liked the explanation. Explained in a very beginner friendly manner ! Thank you !

[mdshaqlain]

Wow! Question was just lengthy optimization was the main thing.Thanks dii

[rajchaurasiya]

Thank you so much for explain, thank you soo much ❤

[Rubotk]

Was stuck for a while. Great technique at end of the video.

[vibhavsharma]

Thanks for explanation of this question. It seems easy now.
Thanks 👍

[forgedinstudies]

Beautifully! explained.
Was stuck in this since evening.

[sgcreations]

Here is the Code
bool isSame( vector<vector<int>>& grid, int x, int y, int n )
{
for( int i = x ; i < x + n ; i++ )
{
for( int j = y ; j < y + n ; j++ )
{
if( grid[i][j] != grid[x][y] )
{
return false ;
}
}
}

return true ;
}
Node* solve( vector<vector<int>>& grid, int x, int y, int n )
{

if(isSame( grid, x, y, n ))
{

return new Node( grid[x][y], true ) ;
}
else{

Node* root = new Node( false, false ) ;
root->topLeft = solve( grid, x, y, n/2 ) ;
root->topRight = solve( grid, x , y + n/2, n/2 ) ;
root->bottomLeft = solve( grid, x + n/2 , y, n/2 ) ;
root->bottomRight = solve( grid, x + n/2, y+n/2, n/2 ) ;
return root ;
}


}
Node* grid) {

return solve( grid, 0, 0, grid.size() ) ;

}