Maximal Square - Top Down Memoization - Leetcode 221

[@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

[@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.

[@jrose2082]

watched this twice then went to implement it myself and accidentally did the bottom up solution because i had such a true understanding of the problem. they need to replace DSA in college with just your youtube channel 😂

[@chenzhuo9]

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

[@shadowsw8020]

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

[@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

[@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.

[@RahulGupta-do5rv]

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

[@NeetCode]

Thanks!

[@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

[@mandy1339]

Thank you. I wanna cry.

[@DavidWoodMusic]

Same bruh

[@symbol767]

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

[@sureshgangavarapu7382]

O(n*m) space soln is pretty simple to understand, but it would be great if you could explain O(n+m) space solution

[@princeanthony8525]

Thanks for showing the recursive solution. Big help.

[@smitvora379]

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

[@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

[@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.

[@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

[@akashsuri377]

completely understood great video

[@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!

[@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

[@stoup8778]

such a good explanation

[@abhishekrbhat8919]

Beautiful explanation

[@魏好晨]

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

[@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.

[@sharabiani]

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

[@adeniyiadeboye3300]

thanks for the illustrative explanation

[@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?

[@middleagedprogrammer-hl6oz]

Brilliant explanation!

[@sravansainath7980]

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

[@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]; } }

[@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

[@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.

[@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.

[@sidazhong2019]

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

[@maheshchandra4115]

This guy is awesome

[@pumpkinpie798]

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

[@VarunKaushal-zx9zq]

thank you

[@dollyvishwakarma2]

Great explanation

[@lifeofamrit3745]

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

[@AnnieBox]

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

[@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

[@rishabsharma5307]

great video

[@jhanvisaraswat6976]

can we do it with dfs?

[@takeobeats]

i like u thank u

[@chiru4969]

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

[@ShivangiSingh-wc3gk]

Will this logic work for rectangles ?

[@ninjaLoveTheWorld]

no

[@breakthecode8323]

You're lit.

[@ZachAdamPerez-y2q]

Max square

[@tombrady7390]

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

[@elainatiller3379]

what is O(n) and space ?

[@sinarb2884]

Cute!

[@shauncrasta619]

Why are we taking min in the transitions? Disappointing.

[@chaitanyagupta6668]

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