Longest Increasing Path in a Matrix - Leetcode 329

Показать описание

0:00 - Read the problem
3:20 - Drawing Explanation
11:32 - Coding Explanation

leetcode 329

#dfs #memoization #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

NeetCode

Рекомендации по теме

Комментарии

The way you make hard problems look so easy is amazing, thanks!

premraja

10+ years coding and I still enjoy watching ur videos.

rommeltito

the first hard problem i've gotten without first viewing the solution ... feels good & hard work + Neetcode videos pays off :)

djx

My code was kinda the same, but yours is a lot cleaner. That's something I really appreciate. Thanks for the great content. :)

freshlyminted

dude i got an approach before but i wasn't sure of its implementation when i saw urs it's not totally same but the iteration part was missing in my approach now i got that thx dude appreciated it

shaikadam

Thanks for all your videos, they helped me so much. I landed my dream job. Please keep up ur channel! Merry Christmas!

mingchenma

Pls keep uploading....I am learning a lot.
You are my guide

girirajrdx

Beautiful solution. Looking forward to more such videos

ngneerin

When you said it is a doable hard, I figured lets try this till I get it accepted and after a bit of back and forth, I was able to get my code accepted.
This is my C++ implementation:

class Solution {
public:
int n, m;
int drow[4]={-1, 0, 1, 0}, dcol[4]={0, 1, 0, -1};

bool isValid(int &row, int &col){
return row>=0 && row<n && col>=0 && col<m;
}

void solve(int row, int col, vector<vector<int>> &dp, vector<vector<int>> &matrix){
int ans=0;

for(int i=0;i<4;i++){
int nrow=row+drow[i], ncol=col+dcol[i];

if(!isValid(nrow, ncol) || continue;

// figure out the sub answer first
if(dp[nrow][ncol]==-1) solve(nrow, ncol, dp, matrix);

// update the ans
ans=max(ans, dp[nrow][ncol]);
}

dp[row][col]=1+ans;
}

int matrix) {
n=matrix.size(), m=matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, -1));

// using DP as cache to make sure each element is visited once
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dp[i][j]==-1){
solve(i, j, dp, matrix);
}
}
}

int ans=1;

// finding out the max in the dp cache
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ans=max(ans, dp[i][j]);
}
}

return ans;
}
};

sauravchandra

I literally search all the youtube I didnt find a guy explaining better than you
Keep on..

rezajeffrey

this one made me feel good about myself, cuz I knew right away it's a grid DFS with memoized storage

minciNashu

The Gold Standard of Leetcode tutorials

jamespolemeni

If you want a bottom up DP solution, you can sort the values of the matrix in descending order (i used a heap, but a sorted array would work too) and process them in that order. You'll be guaranteed to have already calculated the LIPs of your larger neighbours as you visit each element, so you don't need DFS/recursion. Same time and space complexity of course.

dkcan

i think we can directly write this statement right.
res = 1+max(dfs(r+1, c, matrix[r][c]), dfs(r-1, c, matrix[r][c]), dfs(r, c+1, matrix[r][c]), dfs(r, c-1, matrix[r][c]))
instead of those 5 lines of code??

sakethkumarpeddi

Neet what are you thoughts on spaced repetition? Not writing the entire solution and memorizing it... instead, it would be cards in front: statement of the problem, back: Pattern (two pointers, DFS, etc) and any comments, maybe even drawings. Ideally this would help with just pattern recognition over time but wondering if you think it would be useless/ too much memorizing. Would use Anki for reference, thoughts?

Septix

very clean code !! like the way you use dictionary as cache

vincentlius

This was the best explanation, you made the problem so easy. Thank you!

BeingAsh

Small addition, implement backtracking to slightly improve the running time. P.S. Solved this problem on my own in just 20 minutes. Can't stop thanking you.

jitbanerjee

Merry Christmas, let do some neetcode today

NhanSleeptight

Thanks man any tips to approach problem like u do?

AryanSingh-zvch

Longest Increasing Path in a Matrix - Leetcode 329

Longest Increasing Path in a Matrix - Leetcode 329

Leetcode - Longest Increasing Path in a Matrix (Python)

Longest Increasing Path in a Matrix | Live Coding with Explanation | Leetcode - 329

3288. Length of the Longest Increasing Path (Leetcode Hard)

Longest Increasing Path in a Matrix: 329 interview question @ google, apple, amazon, meta, microsoft

329. Longest Increasing Path in a Matrix - Day 19/31 Leetcode May Challenge

Leetcode 329. Hard || Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix (DFS + Memoization)

329. Longest Increasing Path in a Matrix (Leetcode Hard)

LeetCode 329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix - Day 10/30 Leetcode April Challenge

Google Coding Interview Tutorial - Longest Increasing Path in a Matrix [LeetCode 329]

How to Crush Leetcode 329: Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix - DFS + Memoization - Python

Longest Increasing Path in a Matrix - LeetCode 329 - Python

LONGEST INCREASING PATH IN A MATRIX (Leetcode) - Code & Whiteboard

Leetcode - 329. Longest Increasing Path in a Matrix | Topological order

Leetcode Hard Graph Series | Problem 1 | Longest Increasing Path In a Matrix

Longest Increasing Path in a Matrix | Leetcode 329 | DP

Longest Increasing Path in Matrix | Graph | Dynamic Programming | Leetcode | Algorithm Unlock

329. Longest Increasing Path in a Matrix | LeetCode Hard | Python Solution | Dynamic Programming

3288. Length of the Longest Increasing Path | Step By Step Solution | Briefly Explained With Example

LONGEST INCREASING PATH IN A MATRIX | PYTHON | LEETCODE # 329

Leetcode 329 Longest Increasing Path in a Matrix