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.

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

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

[@shadowsw8020]

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

[@chenzhuo9]

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

[@RahulGupta-do5rv]

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

[@NeetCode]

Thanks!

[@symbol767]

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

[@princeanthony8525]

Thanks for showing the recursive solution. Big help.

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

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

[@sharabiani]

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

[@smitvora379]

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

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

[@mandy1339]

Thank you. I wanna cry.

[@DavidWoodMusic]

Same bruh

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

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

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

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

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

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

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

[@pumpkinpie798]

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

[@akashsuri377]

completely understood great video

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

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

[@魏好晨]

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

[@adeniyiadeboye3300]

thanks for the illustrative explanation

[@stoup8778]

such a good explanation

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

[@sravansainath7980]

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

[@abhishekrbhat8919]

Beautiful explanation

[@middleagedprogrammer-hl6oz]

Brilliant explanation!

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

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

[@jhanvisaraswat6976]

can we do it with dfs?

[@sidazhong2019]

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

[@ShivangiSingh-wc3gk]

Will this logic work for rectangles ?

[@ninjaLoveTheWorld]

no

[@AnnieBox]

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

[@dollyvishwakarma2]

Great explanation

[@maheshchandra4115]

This guy is awesome

[@lifeofamrit3745]

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

[@takeobeats]

i like u thank u

[@rishabsharma5307]

great video

[@VarunKaushal-zx9zq]

thank you

[@chiru4969]

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

[@breakthecode8323]

You're lit.

[@elainatiller3379]

what is O(n) and space ?

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

[@sinarb2884]

Cute!

[@chaitanyagupta6668]

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

[@shauncrasta619]

Why are we taking min in the transitions? Disappointing.