LeetCode 329. Longest Increasing Path in a Matrix

December 12, 2020

hardLeetCode

Inputs to be concerned about:

negatives
0s

Edge cases:

empty inputs

This looks like a graph problem. If we define $G=(V,E)$ , where:

$V = v_{ij}$ for $0 \leq i \lt |matrix|$ and $0 \leq j \lt |matrix[i]|$
$E = (u,v)$ for $u$ $\epsilon$ $V$ , $v$ $\epsilon$ $neighbors(u)$ $\epsilon$ $V$ and $val(u) \lt val(v)$

Now we need to find the longest path in the directed graph.

We can do a DFS from each vertex and track the max path length. DFS is $O(V+E)$ , but we have at most 4 edges per vertex in this graph, so this DFS is $O(V)$ . Since we do it $V$ times, the runtime is $O(V^2)$ . With caching, the DFS only has to touch each vertex once, so the total runtime is $O(V)$ = $O(mn)$ .

from typing import Dict, List, Tuple
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_example1(self):
        self.assertEqual(self.s.longestIncreasingPath(
            [
              [9,9,4],
              [6,6,8],
              [2,1,1]
            ]
        ), 4)

    def test_example2(self):
        self.assertEqual(self.s.longestIncreasingPath(
            [
                [3,4,5],
                [3,2,6],
                [2,2,1]
            ]
        ), 4)

    def test_empty(self):
        self.assertEqual(self.s.longestIncreasingPath([]), 0)
        self.assertEqual(self.s.longestIncreasingPath([[]]), 0)

class Solution:

    def _dfs(self, i: int, j: int, g: List[List[int]], c: Dict[Tuple[int,int],int]) -> int:
        if (i, j) in c:
            return c[(i,j)]
        pMax = 1
        c[(i,j)] = pMax
        for (iN,jN) in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            if iN < 0 or iN >= len(g) or jN < 0 or jN >= len(g[iN]):
                continue
            if g[iN][jN] <= g[i][j]:
                continue
            pMax = max(pMax, 1+self._dfs(iN, jN, g, c))
        c[(i,j)] = pMax
        return pMax

    def longestIncreasingPath(self, g: List[List[int]]) -> int:
        pCache = {}
        pMax = 0
        for i in range(len(g)):
            for j in range(len(g[i])):
                pMax = max(pMax, self._dfs(i, j, g, pCache))
        return pMax

if __name__ == "__main__":
    unittest.main()