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

Опубликовано: 15 Ноябрь 2022
на канале: Shaheer Shukur

Leetcode hard problem 329. Longest Increasing Path in a Matrix, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/longest...
Solution (Python Code): https://github.com/shaheershukur/Leet...

#leetcode #python #solution

Problem Statement:
Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given an m x n matrix containing positive integers including zero.
and from this matrix, we need to find out the longest strictly increasing path by moving in any 4 directions. ie, we can move up, down, left and right from each cell of the matrix.
for example, this path of length 7 is longest increasing path in this matrix.

one interesting thing to note here in this problem is that, since we can move in any 4 directions, there can be many paths from each cell of the matrix, and hence there can be many overlapping paths.
for example, lets take these 2 paths starting from the cell containing value 2.
here we can see that this part of the path, ie the path starting from the cell 6 is overlapping, and therefore we are actually computing it twice.

since in this problem, there are overlapping and repeating subproblems, this problem is a perfect candidate for dynamic programming.
so what we will do is, for each cell in the matrix, whenever we find out the longest increasing path from that cell, we will store that result for future use, in the corresponding cell of a new matrix. we can call this new matrix 'paths'.

for example, for the first cell 5, to form an increasing path, there is only 1 direction we can choose. ie towards right.
so the longest path from cell 5 is 1 + the longest path from cell 6.

from cell 6, we can only move in one direction. ie towards the right.
so, the longest path from cell 6 is 1 + the longest path from cell 8.

from cell 8, we can only move in one direction. ie towards the right.
so, the longest path from cell 8 is 1 + the longest path from cell 9.

from cell 9, we cannot create anymore increasing path, and therefore we cannot move forward to any direction.
so, the longest increasing path we can have for cell 9 is 1.

lets update it in the 'paths' matrix.
accordingly, for cell 8, longest path is 1+1 = 2,
for cell 6, the longest path is 1+2 = 3,
for cell 5, the longest path is 1+3 = 4.

now, for cell 3, we can move only in 1 direction. ie, upward direction,
and the longest increasing path from cell 3 is 1 + the longest path from cell 5.
since we already have previously computed result for cell 5, we can reuse it.
so, the longest increasing path from cell 3 is 1+4 = 5

now, for cell 2, we can move in two different directions. upward and left.
if we move in upward direction, the length of path will be 1 + longest path from cell 6, which is 1+3 = 4.
if we move in the left direction, then the length of path will be 1 + longest path from cell 3, which is 1+5 = 6.
since we are looking for the longest increasing path, we will choose the left direction.
so the longest increasing path from cell 2 is 6.

now, for cell 1, we can move in three different directions. upward, left and right.
if we move towards right, the length of path for cell 1 is 1 + longest path from cell 7.
since we have not yet found out the longest path for cell 7, we need to first find that out.
from cell 7, we can only move in one direction. ie, upward.
so, the longest path from cell 7 is 1 + longest path from cell 9, which gives, 1+1 = 2.
now for cell 1, length of path taken through the righ direction is 1+2 = 3.

if we move upward, the length of path will be 1 + longest path from cell 8, which gives 1+2 = 3.
and lastly, if we move towards left, the length of the path will be 1 + longest path from cell 2, which gives 1+6 = 7.
among these 3, the longest path is 7, so we will choose that one.

so, by the end of the traversal, we have the longest path from each cell of the matrix, and we will return the maximum among them.
lets code the solution now.

for traversing through the matrix, we need to know the number of rows and columns.
we will store it in these variables m and n.

for storing the longest increasing path from each cell of the given matrix, we need to create a new matrix of the same size.
we will fill it with zeros initially.