Longest Increasing Path in a Matrix
Problem Description
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. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example 1:
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]]
Output: 1
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 231 - 1
Solve it on LeetCode
Approaches
1. Depth-First Search (DFS) with Memoization
Intuition:
The problem can be solved using a depth-first search approach with memoization. For each cell, we perform a DFS to find the longest increasing path starting from that cell. To avoid recomputing the result for a cell that has already been computed, we use memoization to store the result of the longest path for each cell.
Code:
- Time Complexity: O(m * n): We explore each cell once, memoizing the results, thus preventing redundant computations.
- Space Complexity: O(m * n): The space due to recursive stack and memoization table.
2. Topological Sorting (Kahn's Algorithm)
Intuition:
Imagine the matrix as a directed graph where an edge points from node u to node v if v can be reached from u (i.e., v is greater than u). The nodes have a direction based on increasing values. We can utilize Kahn's algorithm for topological sorting to iterate layers of increasing values starting from zero in-degree nodes.
Code:
- Time Complexity: O(m * n): We process each cell several times as we decrement in-degrees and enqueue new nodes.
- Space Complexity: O(m * n): The space used by the in-degree table and queue.