Leetcode: 329. Longest Increasing Path in a Matrix

By the problem's constraints, we should only consider going from a cell \((i, j)\) to \((x, y)\) if \((x, y)\) is adjacent to \((i, j)\) and its value is greater than the value of \((i, j)\). In the following example, if we want to discover the biggest path that ends on 9 at \((0, 0)\), we must first find the longest paths ending on 6 \((0, 2)\) and 4 \((1, 0)\). So, there is an order which the cells should be processed.

Can we pre-process the input in a way to make easy to solve the problem? Given the cells ordered by their values, it is possible to compute the longest path ending on them by extending the longest paths that ended on their smaller neighbors (which by the order was already processed).

With \(N\) as the number of rows and \(M\) and number of columns,

• time complexity: \(O(N \times (M + log(N)))\), and
• space complexity: \(O(N \times M)\).

from typing import List


def solve(m):
    N = len(m)
    M = len(m[0])

    cells = []
    for i in range(N):
        for j in range(M):
            cells.append((m[i][j], i, j))
    cells = list(sorted(cells))

    dp = [[1] * M for _ in range(N)]
    ans = 1
    for v, i, j in cells:
        for di, dj in [(+0, +1), (+0, -1), (+1, +0), (-1, +0)]:
            if 0 <= i + di < N and 0 <= j + dj < M and m[i][j] > m[i + di][j + dj]:
                dp[i][j] = max(dp[i][j], 1 + dp[i + di][j + dj])
                ans = max(ans, dp[i][j])
    return ans


assert solve([[9, 9, 4], [6, 6, 8], [2, 1, 1]]) == 4
assert solve([[3, 4, 5], [3, 2, 6], [2, 2, 1]]) == 4
assert solve([[1]]) == 1


class Solution:
    def longestIncreasingPath(self, m: List[List[int]]) -> int:
        return solve(m)

• Practice #020: Leetcode
• Leetcode: 2328. Number of Increasing Paths in a Grid