Teaching Kids Programming – Longest Increasing Path in a Matrix via Top Down Dynamic Programming Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right.

Constraints1
n, m ≤ 500 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5

matrix = [     [1, 3, 5],     [0, 4, 6],     [2, 2, 9] ]

matrix = [
    [1, 3, 5],
    [0, 4, 6],
    [2, 2, 9]
]

Output
6

Explanation
The longest path is [0, 1, 3, 5, 6, 9]

Due to the strictly increasing condition, there cannot be any cycles
Question yourself on what will be the longest increasing path if I start from each cell (consider each cell as a starting point and traverse)
Keep a track of the longest increasing path from each cell. Compute this value once and use it whenever required.

Longest Increasing Path in a Matrix via Top Down Dynamic Programming Algorithm

Let f(r, c) represent the length of the longest strictly increasing path that starts at location (r, c). Then we can iterate over each possible location and check which one has the longest strictly increasing path.

For each (r, c) coordinate, we check the neighbour numbers at four directions, and if the neighbour number is bigger than current, we can add one more number to the longest path starting at the neighbour. We need to remember the values that we have calculated to bring down the time complexity for the f function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def solve(self, matrix):
        rows = len(matrix)        
        if not rows:
            return 0
        cols = len(matrix[0])
        if not cols:
            return 0
        @cache
        def f(r, c):
            ans = 1
            for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[r][c] < matrix[nr][nc]:
                    ans = max(ans, 1 + f(nr, nc))
            return ans
        ans = 1
        for r in range(rows):
            for c in range(cols):
                ans = max(ans, f(r, c))
        return ans

class Solution:
    def solve(self, matrix):
        rows = len(matrix)        
        if not rows:
            return 0
        cols = len(matrix[0])
        if not cols:
            return 0
        @cache
        def f(r, c):
            ans = 1
            for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[r][c] < matrix[nr][nc]:
                    ans = max(ans, 1 + f(nr, nc))
            return ans
        ans = 1
        for r in range(rows):
            for c in range(cols):
                ans = max(ans, f(r, c))
        return ans

The time complexity is O(N) where N is the number of numbers in the matrix as we calculate each f(r, c) exactly once. The space complexity is O(N) as we use the @cache to do the memoization. This is Top Down Dynamic Programming Algorithm which is implemented via Recursion with Memoization.

–EOF (The Ultimate Computing & Technology Blog) —