from collections import defaultdict, Counter
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix:
            return 0
        h = len(matrix)
        w = len(matrix[0])
        neighbors = defaultdict(list)
        in_deg = Counter()
        longest_length = Counter()

        ds = [(0, -1), (0, 1), (1, 0), (-1, 0)]
        starts = set(xrange(h * w))
        for x, row in enumerate(matrix):
            for y, v in enumerate(row):
                for dx, dy in ds:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < h and 0 <= ny < w:
                        if matrix[nx][ny] > v:
                            neighbors[x * w + y].append(nx * w + ny)
                            in_deg[nx * w + ny] += 1
                            starts.discard(nx * w + ny)
        for start in starts:
            longest_length[start] = 1

        q = list(starts)
        ans = 1
        for v in q:
            for neighbor in neighbors[v]:
                longest_length[neighbor] = max(longest_length[neighbor], longest_length[v] + 1)
                ans = max(longest_length[neighbor], ans)
                in_deg[neighbor] -= 1
                if in_deg[neighbor] == 0:
                    q.append(neighbor)
        return ans

from collections import Counter
class Solution(object):
    def dfs(self, dp, matrix, x, y, w, h):
        v = matrix[x][y]
        if dp[x, y] == 0:
            dp[x, y] = 1 + max(
                0 if x == 0 or matrix[x - 1][y] <= v else self.dfs(dp, matrix, x - 1, y, w, h),
                0 if y == 0 or matrix[x][y - 1] <= v else self.dfs(dp, matrix, x, y - 1, w, h),
                0 if x == h - 1 or matrix[x + 1][y] <= v else self.dfs(dp, matrix, x + 1, y, w, h),
                0 if y == w - 1 or matrix[x][y + 1] <= v else self.dfs(dp, matrix, x, y + 1, w, h)
            )

        return dp[x, y]

    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix:
            return 0
        h = len(matrix)
        w = len(matrix[0])
        ans = 1
        starts = set(xrange(h * w))
        dp = Counter()
        for x, row in enumerate(matrix):
            for y, v in enumerate(row):
                ans = max(ans, self.dfs(dp, matrix, x, y, w, h))
        return ans

Add py solution for 329. Longest Increasing Path in a Matrix
Add py solution for 329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Approach 2:
    Top down search

- from collections import defaultdict, Counter
+ from collections import Counter
  class Solution(object):
+     def dfs(self, dp, matrix, x, y, w, h):
+         v = matrix[x][y]
+         if dp[x, y] == 0:
+             dp[x, y] = 1 + max(
+                 0 if x == 0 or matrix[x - 1][y] <= v else self.dfs(dp, matrix, x - 1, y, w, h),
+                 0 if y == 0 or matrix[x][y - 1] <= v else self.dfs(dp, matrix, x, y - 1, w, h),
+                 0 if x == h - 1 or matrix[x + 1][y] <= v else self.dfs(dp, matrix, x + 1, y, w, h),
+                 0 if y == w - 1 or matrix[x][y + 1] <= v else self.dfs(dp, matrix, x, y + 1, w, h)
+             )
+ 
+         return dp[x, y]
+ 
      def longestIncreasingPath(self, matrix):
          """
          :type matrix: List[List[int]]
          :rtype: int
          """
          if not matrix:
              return 0
          h = len(matrix)
          w = len(matrix[0])
+         ans = 1
-         neighbors = defaultdict(list)
-         in_deg = Counter()
-         longest_length = Counter()
- 
-         ds = [(0, -1), (0, 1), (1, 0), (-1, 0)]
          starts = set(xrange(h * w))
+         dp = Counter()
          for x, row in enumerate(matrix):
              for y, v in enumerate(row):
+                 ans = max(ans, self.dfs(dp, matrix, x, y, w, h))
-                 for dx, dy in ds:
-                     nx, ny = x + dx, y + dy
-                     if 0 <= nx < h and 0 <= ny < w:
-                         if matrix[nx][ny] > v:
-                             neighbors[x * w + y].append(nx * w + ny)
-                             in_deg[nx * w + ny] += 1
-                             starts.discard(nx * w + ny)
-         for start in starts:
-             longest_length[start] = 1
- 
-         q = list(starts)
-         ans = 1
-         for v in q:
-             for neighbor in neighbors[v]:
-                 longest_length[neighbor] = max(longest_length[neighbor], longest_length[v] + 1)
-                 ans = max(longest_length[neighbor], ans)
-                 in_deg[neighbor] -= 1
-                 if in_deg[neighbor] == 0:
-                     q.append(neighbor)
          return ans
  
Add py solution for 329. Longest Increasing Path in a Matrix
## Code Before:
from collections import defaultdict, Counter
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix:
            return 0
        h = len(matrix)
        w = len(matrix[0])
        neighbors = defaultdict(list)
        in_deg = Counter()
        longest_length = Counter()

        ds = [(0, -1), (0, 1), (1, 0), (-1, 0)]
        starts = set(xrange(h * w))
        for x, row in enumerate(matrix):
            for y, v in enumerate(row):
                for dx, dy in ds:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < h and 0 <= ny < w:
                        if matrix[nx][ny] > v:
                            neighbors[x * w + y].append(nx * w + ny)
                            in_deg[nx * w + ny] += 1
                            starts.discard(nx * w + ny)
        for start in starts:
            longest_length[start] = 1

        q = list(starts)
        ans = 1
        for v in q:
            for neighbor in neighbors[v]:
                longest_length[neighbor] = max(longest_length[neighbor], longest_length[v] + 1)
                ans = max(longest_length[neighbor], ans)
                in_deg[neighbor] -= 1
                if in_deg[neighbor] == 0:
                    q.append(neighbor)
        return ans

## Instruction:
Add py solution for 329. Longest Increasing Path in a Matrix
## Code After:
from collections import Counter
class Solution(object):
    def dfs(self, dp, matrix, x, y, w, h):
        v = matrix[x][y]
        if dp[x, y] == 0:
            dp[x, y] = 1 + max(
                0 if x == 0 or matrix[x - 1][y] <= v else self.dfs(dp, matrix, x - 1, y, w, h),
                0 if y == 0 or matrix[x][y - 1] <= v else self.dfs(dp, matrix, x, y - 1, w, h),
                0 if x == h - 1 or matrix[x + 1][y] <= v else self.dfs(dp, matrix, x + 1, y, w, h),
                0 if y == w - 1 or matrix[x][y + 1] <= v else self.dfs(dp, matrix, x, y + 1, w, h)
            )

        return dp[x, y]

    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix:
            return 0
        h = len(matrix)
        w = len(matrix[0])
        ans = 1
        starts = set(xrange(h * w))
        dp = Counter()
        for x, row in enumerate(matrix):
            for y, v in enumerate(row):
                ans = max(ans, self.dfs(dp, matrix, x, y, w, h))
        return ans
