329. Longest Increasing Path in a Matrix
Problem Description
This LeetCode problem asks us to find the length of the longest increasing path in a given 2D matrix of integers. The path can be constructed by moving from each cell in one of four directions - left, right, up, or down - but not diagonally. The path must consist of a sequence of numbers where each number is greater than the one before it. As a path cannot wrap around the border of the matrix, once you reach the edge, you cannot go any further in that direction. The goal is to determine the maximum length of such an increasing path.
Intuition
To arrive at the solution, we can use depth-first search (DFS) to explore each possible path from each cell in the matrix. The main idea is to traverse the matrix using DFS to find the longest upward path starting from any given cell. At each cell (i, j), we look up, down, left, and right for any adjacent cells that have a higher value than the current cell, and continue on from there. Each movement represents a potential path, and we use recursion to explore all paths. We need to keep track of the length of the path we've found, and update the maximum length when we discover a longer path.
To improve the efficiency of our search, we can use memoization to store the results of the subproblems that have already been computed. In this code, dfs(i, j) represents the length of the longest path starting from cell (i, j). The @cache decorator from Python's functools module ensures that once we compute dfs(i, j) for a particular cell (i, j), we do not recompute it again - the result is stored and reused.
We iterate through every cell in the matrix, invoking dfs(i, j) to get the length of the longest increasing path starting from that cell, keeping track of the maximum value as we go. By the end of this process, we will have explored all the possible paths and found the longest possible path length in the matrix, which will be our final answer.
Learn more about Depth-First Search, Breadth-First Search, Graph, Topological Sort, Memoization and Dynamic Programming patterns.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
Solution Approach
The solution uses depth-first search (DFS) along with memoization to efficiently find the longest increasing path. Here is a step-by-step explanation of how the solution approach is implemented:
-
We begin by defining a
dfsfunction that takes the coordinates(i, j)of a cell as arguments. This function will return the length of the longest increasing path starting from this cell. To remember the length of paths we've already found, we decorate this function with the@cachedecorator, enabling memoization. -
Within the
dfsfunction, we initialize a variableansto 0 to keep track of the longest path found starting from the given cell. -
We create a loop that iterates over the adjacent cells to the current cell
(i, j). This loop usespairwiseto iterate through the directional offsets(-1, 0, 1, 0, -1)to access the left, right, up, and down neighboring cells by adding these offsets to the current cell's indices. -
For each neighboring cell
(x, y), we check if the cell is within the matrix bounds and if its value is greater than the current cell's value, which would make it a candidate for the increasing path. -
If the adjacent cell
(x, y)meets the conditions, we calldfs(x, y)and updateanswith the maximum value between the currentansand the result ofdfs(x, y). -
After exploring all possible paths from the current cell, we return
ans + 1, with the+ 1accounting for the length of the path including the current cell. -
Outside of the
dfsfunction, we determine the dimensions of the matrixmandn. We then iterate through every cell in the matrix, callingdfs(i, j)for each and finding the maximum value across all cells. This maximum value is the length of the longest increasing path in the matrix. -
We finally return this maximum value as the solution to the problem.
The application of DFS, along with memoization via the @cache decorator, allows us to efficiently avoid recomputation of paths that have already been computed. This makes the algorithm significantly faster, especially for larger matrices, as we are able to reuse previously computed results for the subproblems.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
Example Walkthrough
Let's use a small example to illustrate the solution approach. Suppose we have the following 2D matrix:
1Matrix: 23 4 32 5
We want to find the length of the longest increasing path in this matrix.
Following the solution approach, we apply DFS and memoization as outlined:
-
We define our
dfsfunction with memoization to keep track of the longest path starting from each cell. -
We start with the cell at
(0, 0)which has the value 3. We look at its neighbors(0, 1)with value 4. -
Since 4 is greater than 3, it's a valid step in the increasing path. We call
dfs(0, 1). -
At
(0, 1), with the value 4, the only valid increasing step is to move down to(1, 1)with the value 5. We calldfs(1, 1). -
At
(1, 1), with the value 5, there are no further adjacent cells with larger values, so its longest path is just itself, with a length of 1. The value is memoized. -
Returning to
(0, 1)with value 4, we add 1 for the current cell to the maximum path length we can get by moving from it, which is 1 for the(1, 1)cell. The total is 2, which is memoized for(0, 1). -
Now we go back to the starting cell
(0, 0). With the memoized results, we know the longest path from(0, 1)is of length 2. So for(0, 0), the length is 2 plus the current cell: 3. -
Next, we check the cell
(1, 0). -
The cell
(1, 0)has a value of 2 and only one neighbor(1, 1)with a greater value. We calldfs(1, 1), but this time, the path length is already memoized. -
For
(1, 0), we take the memoized path length of(1, 1), which is 1, and add 1 for the current cell, giving us a total path length of 2. -
Therefore, the possible path lengths starting from each cell are 3 from
(0, 0)and 2 from both(0, 1)and(1, 0). The cell at(1, 1)does not lead to any other cell, so its path length is 1. -
We iterate through each cell in the matrix and choose the maximum length from the results of the
dfscalls. The final result for the longest increasing path in this example is 3, which starts from cell(0, 0)and goes through(0, 1)to(1, 1).
Applying the steps from the solution to this small example matrix demonstrates the increase in efficiency gained from memoization, as we avoid recalculating the longest path from each cell more than once.
Solution Implementation
1from typing import List
2from functools import lru_cache
3
4class Solution:
5 def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
6
7 # Define the dimensions of the matrix
8 rows, cols = len(matrix), len(matrix[0])
9
10 # Define direction vectors for traversing up, down, left, and right
11 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
12
13 # Use memoization to cache the results of previous computations
14 @lru_cache(maxsize=None)
15 def dfs(row: int, col: int) -> int:
16 # Start with the longest path of 1 that includes the current cell
17 max_path_length = 1
18
19 # Explore all possible directions from the current cell
20 for d_row, d_col in directions:
21 new_row, new_col = row + d_row, col + d_col
22
23 # Check if the new position is within bounds and increases in value
24 if 0 <= new_row < rows and 0 <= new_col < cols and matrix[new_row][new_col] > matrix[row][col]:
25 # Recursively find the longest increasing path from the new position
26 max_path_length = max(max_path_length, 1 + dfs(new_row, new_col))
27
28 return max_path_length
29
30 # Iterate over all matrix cells to find the starting point of the longest increasing path
31 max_path = 0
32 for i in range(rows):
33 for j in range(cols):
34 max_path = max(max_path, dfs(i, j))
35
36 return max_path
37
38# Example usage
39# solution = Solution()
40# print(solution.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]])) # Output: 4
411class Solution {
2 private int numRows;
3 private int numCols;
4 private int[][] grid; // Renamed "matrix" to "grid" for clarity
5 private int[][] dp; // Renamed "f" to "dp" for denoting the "dynamic programming" cache
6
7 public int longestIncreasingPath(int[][] matrix) {
8 numRows = matrix.length;
9 numCols = matrix[0].length;
10 dp = new int[numRows][numCols];
11 this.grid = matrix;
12 int longestPath = 0;
13
14 // Iterate over each cell in the matrix
15 for (int i = 0; i < numRows; ++i) {
16 for (int j = 0; j < numCols; ++j) {
17 // Update the longest path found so far
18 longestPath = Math.max(longestPath, dfs(i, j));
19 }
20 }
21
22 return longestPath;
23 }
24
25 private int dfs(int row, int col) {
26 // If the current cell already contains a computed length, return it
27 if (dp[row][col] != 0) {
28 return dp[row][col];
29 }
30
31 // Direction vectors for the 4 adjacent cells (up, right, down, left)
32 int[] directions = {-1, 0, 1, 0, -1};
33
34 // Explore all adjacent cells
35 for (int k = 0; k < 4; k++) {
36 int nextRow = row + directions[k];
37 int nextCol = col + directions[k + 1];
38
39 // Check if the next cell is within bounds and has a larger value than the current cell
40 if (nextRow >= 0 && nextRow < numRows && nextCol >= 0 && nextCol < numCols && grid[nextRow][nextCol] > grid[row][col]) {
41 // Update the length of the longest increasing path from the current cell
42 dp[row][col] = Math.max(dp[row][col], dfs(nextRow, nextCol));
43 }
44 }
45
46 // Increment the stored length by 1 to include the current cell and return it
47 return ++dp[row][col];
48 }
49}
501class Solution {
2public:
3 int longestIncreasingPath(vector<vector<int>>& matrix) {
4 int rows = matrix.size(); // Number of rows in the matrix
5 int cols = matrix[0].size(); // Number of columns in the matrix
6 vector<vector<int>> cache(rows, vector<int>(cols, 0)); // Memoization cache
7 int longestPath = 0; // Initialize the length of the longest path
8 // Directions array representing the four possible movements (up, right, down, left)
9 vector<int> directions = {-1, 0, 1, 0, -1};
10
11 // Depth-first search function to find the longest increasing path
12 function<int(int, int)> dfs = [&](int row, int col) -> int {
13 // If we've already computed this position, return the cached value
14 if (cache[row][col]) {
15 return cache[row][col];
16 }
17 // Check all four possible directions
18 for (int k = 0; k < 4; ++k) {
19 int newRow = row + directions[k]; // Calculate new row position
20 int newCol = col + directions[k + 1]; // Calculate new column position
21 // If the new position is within bounds and is greater than the current cell
22 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] > matrix[row][col]) {
23 // Recursively explore the new position and update the cache
24 cache[row][col] = max(cache[row][col], dfs(newRow, newCol));
25 }
26 }
27 // After exploring all directions, increment the path length by 1 and return
28 return ++cache[row][col];
29 };
30
31 // Iterate through each cell in the matrix
32 for (int i = 0; i < rows; ++i) {
33 for (int j = 0; j < cols; ++j) {
34 // Compute the longest increasing path starting from (i, j)
35 longestPath = max(longestPath, dfs(i, j));
36 }
37 }
38 // Return the length of the longest path after processing all cells
39 return longestPath;
40 }
41};
421// Type definition for the matrix of numbers.
2type Matrix = number[][];
3
4// Cache for storing the length of the longest increasing path from a particular cell.
5let cache: Matrix;
6
7// Directions array representing the movement offsets for the four cardinal directions.
8const directions: [number, number][] = [
9 [-1, 0], // up
10 [0, 1], // right
11 [1, 0], // down
12 [0, -1], // left
13];
14
15/**
16 * Performs a depth-first search to find the longest increasing path from a given cell.
17 * @param row - The row index of the current cell.
18 * @param column - The column index of the current cell.
19 * @param matrix - The input matrix of numbers.
20 * @returns The length of the longest increasing path from the current cell.
21 */
22function dfs(row: number, column: number, matrix: Matrix): number {
23 // If we already computed the longest path from this cell, return the cached value.
24 if (cache[row][column] > 0) {
25 return cache[row][column];
26 }
27
28 // Initialize the maximum length from the current cell to 1 (the cell itself).
29 let maxLength = 1;
30
31 // Explore all possible directions from the current cell.
32 for (const [dx, dy] of directions) {
33 const newRow = row + dx;
34 const newColumn = column + dy;
35
36 // Check if the new cell is within bounds and has a value greater than the current cell.
37 if (
38 newRow >= 0 && newRow < matrix.length &&
39 newColumn >= 0 && newColumn < matrix[0].length &&
40 matrix[newRow][newColumn] > matrix[row][column]
41 ) {
42 // Recursively compute the longest path from the neighboring cell.
43 const length = 1 + dfs(newRow, newColumn, matrix);
44
45 // Update the maximum length if the computed path is longer.
46 maxLength = Math.max(maxLength, length);
47 }
48 }
49
50 // Cache the computed maximum length for the current cell.
51 cache[row][column] = maxLength;
52
53 return maxLength;
54}
55
56/**
57 * Computes the length of the longest increasing path in a matrix.
58 * @param matrix - The input matrix of numbers.
59 * @returns The length of the longest increasing path in the matrix.
60 */
61function longestIncreasingPath(matrix: Matrix): number {
62 // Handle an empty matrix case by returning 0 early.
63 if (matrix.length === 0 || matrix[0].length === 0) {
64 return 0;
65 }
66
67 // Initialize rows and columns counts, and the cache matrix.
68 const rows = matrix.length;
69 const columns = matrix[0].length;
70 cache = Array.from({length: rows}, () => Array(columns).fill(0));
71
72 // The overall maximum length of the longest increasing path.
73 let globalMaxLength = 0;
74
75 // Iterate over each cell in the matrix.
76 for (let i = 0; i < rows; ++i) {
77 for (let j = 0; j < columns; ++j) {
78 // Use DFS to find the longest path from the current cell and update the global maximum.
79 globalMaxLength = Math.max(globalMaxLength, dfs(i, j, matrix));
80 }
81 }
82
83 // Return the global maximum length found.
84 return globalMaxLength;
85}
86Breadth first search can be used to find the shortest path between two nodes in a directed graph.
Time and Space Complexity
Time Complexity
The time complexity of this algorithm is O(m * n) where m is the number of rows and n is the number of columns in the input matrix. This is because in the worst case scenario, we perform a depth-first search (DFS) starting from each cell in the matrix. The memoization using @cache ensures that each cell (i, j) is only processed once for its longest increasing path, and the DFS from that cell terminates once it has explored all increasing paths from that cell. Hence, each cell's DFS contributes O(1) amortized time, and since we have m * n cells, the overall time is O(m * n).
Space Complexity
The algorithm has a space complexity of O(m * n) as well, due to the memoization cache that potentially stores the results for each cell in the matrix. The space required is for the recursive call stack and the cache storage. In the worst case, the recursive call stack could go as deep as m * n if there is an increasing path through every cell. Thus, with the cache and call stack combined, the space complexity is O(m * n).
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.