How hard is LeetCode 329. Longest Increasing Path in a Matrix?

LeetCode 329. Longest Increasing Path in a Matrix is rated Hard on LeetCode.

What is the time complexity of LeetCode 329. Longest Increasing Path in a Matrix?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 329. Longest Increasing Path in a Matrix?

The Python solution on this page uses O(m \times n) auxiliary space.

Longest Increasing Path in a Matrix — LeetCode 329 Python Solution

HardDepth-First SearchBreadth-First SearchGraphTopological SortMemoizationArrayDynamic ProgrammingMatrix

Problem: #329
Pattern: Topological Sort
Reading time: 2 min
Source: leetcode.com

The problem

Given an m x n integers matrix, return the length of the longest increasing path in matrix. From each cell, you can either move in four directions: left, right, up, or down.

Example

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Python solution

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            ans = 0
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    ans = max(ans, dfs(x, y))
            return ans + 1

        m, n = len(matrix), len(matrix[0])
        return max(dfs(i, j) for i in range(m) for j in range(n))

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 329. Longest Increasing Path in a Matrix is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

On a study list

This problem is on NeetCode 150.

Frequently asked questions

How hard is LeetCode 329. Longest Increasing Path in a Matrix?: LeetCode 329. Longest Increasing Path in a Matrix is rated Hard on LeetCode.
What is the time complexity of LeetCode 329. Longest Increasing Path in a Matrix?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 329. Longest Increasing Path in a Matrix?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 329. Longest Increasing Path in a Matrix cover?: LeetCode 329. Longest Increasing Path in a Matrix is tagged Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization, Array, Dynamic Programming and Matrix on LeetCode.