Problem

Given an integer matrix, find the length of the longest increasing path.

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

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return4
The longest increasing path is[1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return4
The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

tags: DFS, topological sort, memoization (dynamic programming)

Solution

summary: not so much topological sort. But dfs, and record into visited dictionary as we finish processing this vertex.

Time complexity: O(rowNum * colNum)

1. use a map visited where key is (row, col) tuple, and value is the longest increasing path starting at that coordinate
   1. note, we only store the (row, col) tuple into visited dictionary after we finish processing the dfsVisit()
2. for each dfsVisit.
   1. find all valid neighbors to visit and go through each of them
   2. if they are bigger than current matrix[row][col]
      1. if this neighbor is visited
         1. res = max(res, neighbor res + 1)
      2. not visited
         1. dfsVisit(neightbor, ancestor + (row, col)

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if matrix == None or matrix == []:
            return 0

        visited = {} # stores (row,col) as key, L.I.P as value. Kinda like DP
        rowNum = len(matrix)
        colNum = len(matrix[0])
        returnRes = 0
        for row in range(rowNum):
            for col in range(colNum):
                if (row, col) not in visited:
                    res = self.dfsVisit(row, col, matrix, visited, [(row, col)])
                    visited[(row, col)] = res
                    returnRes = max(returnRes, res)
                else:
                    returnRes = max(returnRes, visited[(row, col)])

        return returnRes

    # visit the coordinate (row, col) in the matrix, and starting from it, go to all four directions
    # in each directional visit, do dfsVisit to deeper level, 
    # the base return case is when dfs hit the boundary of the matrix and return res = 1,
    # and it backtracks from there
    def dfsVisit(self, row, col, matrix, visited, ancestors):
        res = 1
        for (row2, col2) in self.findValidCoord(row, col, matrix, ancestors):
            if matrix[row][col] >= matrix[row2][col2]:
                continue
            if (row2, col2) in visited:
                res = max(res, visited[(row2,col2)] + 1)
            else:
                temp = self.dfsVisit(row2, col2, matrix, visited, ancestors + [(row2 , col2)])
                visited[(row2,col2)] = temp
                res = max(res, temp + 1)
        return res

    def findValidCoord(self, row, col, matrix, ancestors):
        rowNum = len(matrix)
        colNum = len(matrix[0])
        coords = []
        if (row - 1, col) not in ancestors and row - 1 >= 0:
            coords.append((row - 1, col))

        if (row, col-1) not in ancestors and col - 1 >= 0:
            coords.append((row, col - 1))

        if (row + 1, col) not in ancestors and row + 1 < rowNum:
            coords.append((row + 1, col))

        if (row, col + 1) not in ancestors and col + 1 < colNum:
            coords.append((row, col + 1))
        return coords