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
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
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"?
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.
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?
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
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!
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
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)
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
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]; } }
Dynamic Programming Playlist: ruclips.net/video/73r3KWiEvyk/видео.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
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
This is an awesome explanation! Very well done. Keep up the amazing work! :)
Thanks!
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.
Thank you so much! This channel is now my to-go channel for leetcode videos! Keep it up dude!
Thank you. I wanna cry.
Same bruh
Very good ASMR, I fell asleep and had a sweet dream :P
This is amazing, you broke it down so easily and perfectly, thank you bro
I think u should have implemented the dp solution as u explained it so that would have made more sense literally!
Thanks for showing the recursive solution. Big help.
completely understood great video
That's a really great solutio. The DP solution without the recursion took me longer to write. This is much cleaner and neet :P
What would be the Time Complexity if we don't use the cache in the Top-Down Recursive approach?
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.
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?
"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.
thanks for the illustrative explanation
Beautiful explanation
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
Brilliant explanation!
the best question if we do repeated works if we can slice it into subproblem
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.
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
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!
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
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.
and what to do if its asking for a maximal rectangle of 0's .. I don't understand
Thanks mate ,there is bottom up shit every where with no top down approch
This guy is awesome
Great explanation
great video
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
i like u thank u
This question is the same idea as the robot walking the matrix
can we do it with dfs?
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
asked it's variation find second largest square in my Amazon interview
kudos on your pronunciation of Huawei! (๑•̀ㅂ•́)و👍
Will this logic work for rectangles ?
no
You're lit.
i guess the order in which u filled cell is wrong, your final answer may be correct
what is O(n) and space ?
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];
}
}
Cute!
I cant point out a fault in anyone your videos wont be surprised of you become associated to a coding bootcamp.
this is the least detailed explanation video of yours. Disappointing.
Why are we taking min in the transitions? Disappointing.