329. Longest Increasing Path in a Matrix

HardDepth-First SearchBreadth-First SearchGraphTopological SortMemoizationArrayDynamic ProgrammingMatrix

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.

Flowchart Walkthrough

Let's analyze leetcode 329. Longest Increasing Path in a Matrix using the algorithm flowchart. Here's a step-by-step walkthrough:

First, let's refer to the Flowchart to determine the suitable algorithm:

Is it a graph?

Yes: The matrix can be treated like a graph where each cell is a node, and there is an edge to another cell if it is next (up, down, left, right) and the value is increasing.

Is it a tree?

No: The graph does not necessarily form a hierarchy or a tree structure, as cells can connect in complex patterns beyond parent-child relationships.

Is the problem related to directed acyclic graphs (DAGs)?

Yes: Each directed edge points from a lower value to a higher one, ensuring no cycles can exist based solely on increasing values, forming a DAG.

Does the problem involve topological sorting?

No: Although the problem forms a DAG, it is not looking for a sorting of elements but a longest path.

Is the problem related to shortest paths?

No: The problem involves finding the longest path based on conditions (increasing values), not the "shortest path" in terms of distance or cost.

Does the problem involve connectivity?

No: While connectivity is inherent in defining paths, the problem's main challenge is the path length and order rather than just connectivity.

Does the problem have small constraints?

Yes: The main constraint is to find the longest increasing path, which may require exploring multiple potential paths and backtracking if needed.

Conclusion: Based on following through the flowchart, we conclude that this problem is suited to using DFS combined with backtracking, specifically adapted to handle the increases and caching for efficiency.

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.

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 dfs function 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 @cache decorator, enabling memoization.
Within the dfs function, we initialize a variable ans to 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 uses pairwise to 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 call dfs(x, y) and update ans with the maximum value between the current ans and the result of dfs(x, y).
After exploring all possible paths from the current cell, we return ans + 1, with the + 1 accounting for the length of the path including the current cell.
Outside of the dfs function, we determine the dimensions of the matrix m and n. We then iterate through every cell in the matrix, calling dfs(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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have the following 2D matrix:

Matrix:
3 4
2 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 dfs function 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 call dfs(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 call dfs(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 dfs calls. 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
41

1class 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}
50

1class 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};
42

1// 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}
86

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don't know