Maximal Square - Top Down Memoization - Leetcode 221
Vložit
- čas přidán 7. 08. 2024
- 🚀 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 - Věda a technologie
Dynamic Programming Playlist: czcams.com/video/73r3KWiEvyk/video.html
Fire explanation, I appreciate you showed the top-down solution instead of jumping to the bottom up solution that no one understands
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
Thank you so much! This channel is now my to-go channel for leetcode videos! Keep it up dude!
This is amazing, you broke it down so easily and perfectly, thank you bro
This is an awesome explanation! Very well done. Keep up the amazing work! :)
Thanks!
That's a really great solutio. The DP solution without the recursion took me longer to write. This is much cleaner and neet :P
Thanks for showing the recursive solution. Big help.
Very good ASMR, I fell asleep and had a sweet dream :P
completely understood great video
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
had the same problem and was wondering why. thanks. you saved me tons of time.
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"?
leetcode 1770,1143 are pretty similar problems, and they are all categorized as multi dimentional dynamic programming problems
thanks for the illustrative explanation
Brilliant explanation!
Beautiful explanation
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.
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.
I think u should have implemented the dp solution as u explained it so that would have made more sense literally!
Thank you. I wanna cry.
Same bruh
What would be the Time Complexity if we don't use the cache in the Top-Down Recursive approach?
Great explanation
Such a beautiful explanation. Just wondering how did you identify that looking right, down and diagonal would help.
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.
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.
the best question if we do repeated works if we can slice it into subproblem
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!
great video
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
He is not God, he is my NanShen~~~(✿◡‿◡)
thanks for the solution
I recently started working on python, and used to code only in Java for all interviews. This explanation showed me ho python is superior!
dude i just implemented the solution in java after watching this video, what are u talking about ?? lol
Thanks mate ,there is bottom up shit every where with no top down approch
This guy is awesome
can we do it with dfs?
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
awesome thanks for the solution
and what to do if its asking for a maximal rectangle of 0's .. I don't understand
Can u add more interview questions related to dynamic programming ?
Definitely! I always shy away from DP because it takes me forever to record, but they are some of my favorite problems to solve.
i like u thank u
"it's actually a pretty simple problem"
Me who took almost 1 hour and still couldn't figure out even the recurrence relation : 👀'
Simple doesnt mean easy. I also struggled with this one and it took a blow to my confidence.
try to redo question 62, it's exactly the same.
This question is the same idea as the robot walking the matrix
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?
Will this logic work for rectangles ?
no
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
kudos on your pronunciation of Huawei! (๑•̀ㅂ•́)و👍
asked it's variation find second largest square in my Amazon interview
You're lit.
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
Max square
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];
}
}
i guess the order in which u filled cell is wrong, your final answer may be correct
what is O(n) and space ?
Cute!
I cant point out a fault in anyone your videos wont be surprised of you become associated to a coding bootcamp.
Why are we taking min in the transitions? Disappointing.
this is the least detailed explanation video of yours. Disappointing.