Maximal Square - Top Down Memoization - Leetcode 221

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/maximal...
0:00 - Read the problem
1:15 - Drawing solution
12:50 - Coding solution
leetcode 221
This question was identified as a Google interview question from here: github.com/xizhengszhang/Leet...
#neetcode #memoization #python

[@NeetCode]

Dynamic Programming Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@U2L1ve]

Fire explanation, I appreciate you showed the top-down solution instead of jumping to the bottom up solution that no one understands

[@geekydanish5990]

Bottom up solution class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: dp = [[0 for j in range(len(matrix[0])+1)] for i in range(len(matrix)+1)] max_side = 0 for i in range(len(matrix)-1,-1,-1): for j in range(len(matrix[0])-1,-1,-1): if matrix[i][j] == "1": dp[i][j] = 1 + min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1]) max_side = max(max_side,dp[i][j]) return max_side**2

[@chenzhuo9]

Thank you so much! This channel is now my to-go channel for leetcode videos! Keep it up dude!

[@symbol767]

This is amazing, you broke it down so easily and perfectly, thank you bro

[@princeanthony8525]

Thanks for showing the recursive solution. Big help.

[@RahulGupta-do5rv]

This is an awesome explanation! Very well done. Keep up the amazing work! :)

[@NeetCode]

Thanks!

[@hirak123456]

That's a really great solutio. The DP solution without the recursion took me longer to write. This is much cleaner and neet :P

[@jacobgarwin5616]

Is this really top down? When I tried this problem (which I struggled with greatly) I attempted to break down the largest square into smaller squares (i.e. each square is composed of 4 smaller sub-squares) and then making the recursive calls on each of these until you reach a base case of a single square. I thought the approach that I was taking would be considered top down. This seems like you are really building from the bottom up but just using a recursive function to replace the loop structure. Regardless, your answer is better. With my approach I couldn't find a way to intuitively think about memoizing past results. Do you have any advice on how I could recognize early on in the problem whether a top-down vs. bottom-up approach would be better? I spent like 2 hours on the top down answer only to get a brute force recursive approach and then struggled to implement memoization.

[@mdlwlmdd2dwd30]

I think you have to study how dp works first. It seems like you are confusing about dp in general. you can solve it top down or bottom up either way and if you understand DP problem in general, bottom-up is always ideal when it comes to scalability. You can only so much put on the stack calls, right? recognizing top down vs bottomup shouldnt be issue, it seems more like you recognize what recurrence relation is pertained to this problem is the real issue.

[@adeniyiadeboye3300]

thanks for the illustrative explanation

[@akashsuri377]

completely understood great video

[@middleagedprogrammer-hl6oz]

Brilliant explanation!

[@slambam4592]

Btw, I wanted to point out a possible bug someone may make. At first, I originally wrote line 20 as: cache[r, c] = 1 + helper(aux(r, c + 1), helper(r + 1, c + 1), helper(r + 1, c)) to make it more concise, but it was failing half the tests. However, I realized that it was because you ALWAYS want to make recursive calls to the right diag down. By putting those recursive calls inside the if statement, you only make those recursive calls when you hit a '1'. If you hit a '0', your recursive functions stops there, and it doesnt call any more. Thats why you have to keep them separate

[@seol1500]

had the same problem and was wondering why. thanks. you saved me tons of time.

[@abhishekrbhat8919]

Beautiful explanation

[@vedantshinde2277]

Great Explanation! If this was asked in an interview and I hadn't solved it, do you have any tips on how to go about solving it? Does this problem have a parent "classic problem"?

[@zihaoyan4741]

leetcode 1770,1143 are pretty similar problems, and they are all categorized as multi dimentional dynamic programming problems

[@sharabiani]

What would be the Time Complexity if we don't use the cache in the Top-Down Recursive approach?

[@shadowsw8020]

Very good ASMR, I fell asleep and had a sweet dream :P

[@dollyvishwakarma2]

Great explanation

[@smitvora379]

I think u should have implemented the dp solution as u explained it so that would have made more sense literally!

[@rishabsharma5307]

great video

[@pumpkinpie798]

and what to do if its asking for a maximal rectangle of 0's .. I don't understand

[@ShivangiSingh-wc3gk]

Such a beautiful explanation. Just wondering how did you identify that looking right, down and diagonal would help.

[@dartm0]

To form a square you need to check those. If one of those is 0 then you can only make a square with the one you are at.

[@mandy1339]

Thank you. I wanna cry.

[@DavidWoodMusic]

Same bruh

[@maheshchandra4115]

This guy is awesome

[@handlerhandle123]

This is great but I noticed how Leetcode has a O(n) space solution and this solution has O(mn) space even though this is much clearer...I hope this solution would be good enough!

[@dARKf3n1Xx]

There is a way to deconstruct this problem into 1D (maximal area of a histogram) and then find the max of those results as our final area.

[@user-kc9ed9bx1g]

the best question if we do repeated works if we can slice it into subproblem

[@Briansilasluke]

I recently started working on python, and used to code only in Java for all interviews. This explanation showed me ho python is superior!

[@shaiksohel4247]

dude i just implemented the solution in java after watching this video, what are u talking about ?? lol

[@jhanvisaraswat6976]

can we do it with dfs?

[@takeobeats]

i like u thank u

[@techandmore12]

Why not just start at the last column, go from right to left and then go up and reapeat until you reach the first row? Much more intuitive and same time complexity. Also, why not just modify the matrix itself to save space?

[@sravansainath7980]

Thanks mate ,there is bottom up shit every where with no top down approch

[@edwardteach2]

U a God, my implementation with 2 for-loops: class Solution(object): def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ dp = {} max_value = 0 rows = len(matrix) cols = len(matrix[0]) def dfs(r,c): if r < 0 or c < 0 or r >= rows or c >= cols or matrix[r][c] == "0": return 0 if (r,c) in dp: return dp[(r,c)] right = dfs(r, c + 1) diag = dfs(r + 1, c + 1) bot = dfs(r + 1, c) dp[(r,c)] = 1 + min(right, diag, bot) return dp[(r,c)] for r in range(rows): for c in range(cols): if matrix[r][c] == "1": max_value = max(max_value, dfs(r,c)) return max_value ** 2

[@AnnieBox]

He is not God, he is my NanShen~~~(✿◡‿◡)

[@arrows8367]

thanks for the solution

[@orangethemeow]

I tried the bottom up solution, keep updating matrix class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: m, n = len(matrix), len(matrix[0]) maxLen = 0 for c in range(n): maxLen = max(maxLen, int(matrix[m-1][c])) for r in range(m): maxLen = max(maxLen, int(matrix[r][n-1])) for r in range (m - 2, -1, -1): for c in range(n - 2, -1, -1): if matrix[r][c] == "1": matrix[r][c] = (1 + min(int(matrix[r+1][c]), int(matrix[r][c+1]), int(matrix[r+1][c+1]))) elif matrix[r][c] == "0": matrix[r][c] = 0 maxLen = max(maxLen, matrix[r][c]) return maxLen ** 2

[@sagarpotnis1215]

awesome thanks for the solution

[@nikhildinesan5259]

Can u add more interview questions related to dynamic programming ?

[@NeetCode]

Definitely! I always shy away from DP because it takes me forever to record, but they are some of my favorite problems to solve.

[@ujjawal.pandey]

"it's actually a pretty simple problem" Me who took almost 1 hour and still couldn't figure out even the recurrence relation : 👀'

[@mandy1339]

Simple doesnt mean easy. I also struggled with this one and it took a blow to my confidence.

[@sidazhong2019]

try to redo question 62, it's exactly the same.

[@breakthecode8323]

You're lit.

[@ShivangiSingh-wc3gk]

Will this logic work for rectangles ?

[@ninjaLoveTheWorld]

no

[@fieworjohn5697]

my code isn't passing the first testcase. can someone help spot the bug: class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: ROWS, COLS = len(matrix), len(matrix[0]) cache = {} def fn(r, c): if r >= ROWS or c >= COLS: return 0 if (r, c) not in cache: down = fn(r+1, c) right = fn(r, c+1) diagonal = fn(r+1, c+1) cache[(r, c)] = 0 if matrix[r][c] == "1": cache[(r, c)] = 1 + min(down, right, diagonal) return cache[(r, c)] fn(0, 0) return max(cache.values()) ** 2

[@sidazhong2019]

This question is the same idea as the robot walking the matrix

[@lifeofamrit3745]

asked it's variation find second largest square in my Amazon interview

[@AnnieBox]

kudos on your pronunciation of Huawei! (๑•̀ㅂ•́)و👍

[@mashab9129]

I solved it in the below way which passes : var maximalSquare = function(matrix) { const n = matrix.length, m = matrix[0].length; const dp = Array(n+1).fill().map(el => Array(m+1).fill(0)); let max = 0 for (let i = 1; i

[@alexbox92]

Java code: import java.util.Arrays; public class MaximalSquare { static int ROWS; static int COLS; static char[][] matrix; static int maxLength = 0; //Key: row, Value: column static int[][] cache; static int maximalDPTopDown(char[][] matrix) { MaximalSquare.matrix = matrix; ROWS = matrix.length; COLS = matrix[0].length; cache = new int[ROWS][COLS]; for(int i = 0; i < ROWS; i++) { Arrays.fill(cache[i], -1); } helper(0, 0); //top left element return maxLength * maxLength; } static int helper(int row, int col) { //Base case if(row >= ROWS || col >= COLS) { return 0; } if(cache[row][col] == -1) { //True if NOT in the cache int down = helper(row + 1, col); //Check Down int right = helper(row, col + 1); //Right position int diag = helper(row + 1, col + 1); //Check Diagonally cache[row][col] = 0; if(matrix[row][col] == '1') { // //Takes the minimum off all of these 3 values: down, right and diag cache[row][col] = 1 + Math.min(down, Math.min(right, diag)); maxLength = Math.max(cache[row][col], maxLength); } } return cache[row][col]; } }

[@chiranjeevisingadi1474]

i guess the order in which u filled cell is wrong, your final answer may be correct

[@user-gf7bf7us1p]

Max square

[@elainatiller3379]

what is O(n) and space ?

[@sinarb2884]

Cute!

[@tombrady7390]

I cant point out a fault in anyone your videos wont be surprised of you become associated to a coding bootcamp.

[@shauncrasta619]

Why are we taking min in the transitions? Disappointing.

[@chaitanyagupta6668]

this is the least detailed explanation video of yours. Disappointing.