Longest Increasing Path in a Matrix

HARD

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:

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

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
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] <= 2³¹ - 1

Approaches

Checkout 2 different approaches to solve Longest Increasing Path in a Matrix. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Depth First Search

This approach explores every possible increasing path starting from every cell in the matrix. For each cell, it performs a Depth First Search (DFS) to find the longest path originating from it. The overall maximum length found among all starting cells is the answer.

Algorithm

Initialize a global variable maxLength to 0.
Create a main function that iterates through every cell (i, j) of the matrix.
For each cell, call a recursive DFS helper function, dfs(row, col), to compute the length of the longest increasing path starting at that cell.
Update maxLength = max(maxLength, result from dfs).
The dfs(row, col) function works as follows: a. Initialize maxPathFromCell to 1 (for the cell itself). b. Explore the four adjacent neighbors (up, down, left, right). c. For each neighbor (nextRow, nextCol) that is within the matrix boundaries and has a value matrix[nextRow][nextCol] > matrix[row][col], make a recursive call: 1 + dfs(nextRow, nextCol). d. Update maxPathFromCell with the maximum length found among all valid neighbors. e. Return maxPathFromCell.
After iterating through all cells, return maxLength.

We define a main function that iterates through every cell (i, j) of the matrix. For each cell, it calls a recursive DFS helper function, dfs(row, col), to compute the length of the longest increasing path starting at (row, col). The main function keeps track of the maximum length found so far and updates it after each DFS call.

The dfs(row, col) function explores the four adjacent neighbors (up, down, left, right). For each neighbor (nextRow, nextCol) that is within the matrix boundaries and has a value greater than matrix[row][col], it makes a recursive call. The length of the path starting from (row, col) is 1 + max(length of paths from valid neighbors). The base case for the recursion is a cell from which no further increasing path can be formed; in this case, the path length is 1 (the cell itself).

This method is straightforward but highly inefficient because it repeatedly calculates the longest path for the same cells multiple times. For example, the longest path from cell A might be needed to calculate the path from cell B, and also later for the path from cell C.

class Solution {
    private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        m = matrix.length;
        n = matrix[0].length;
        int maxLength = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLength = Math.max(maxLength, dfs(matrix, i, j));
            }
        }
        return maxLength;
    }

    private int dfs(int[][] matrix, int row, int col) {
        int maxPath = 1;
        for (int[] dir : dirs) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) {
                maxPath = Math.max(maxPath, 1 + dfs(matrix, newRow, newCol));
            }
        }
        return maxPath;
    }
}

Complexity Analysis

Time Complexity: O((m*n) * 4^(m*n)) - This is a loose upper bound, but the complexity is exponential. From each cell, the search can branch out, and the same subproblems (finding the longest path from a particular cell) are solved repeatedly. This leads to an exponential number of function calls.Space Complexity: O(m * n) - The space is dominated by the recursion stack depth, which in the worst case (a path that visits every cell) can be the total number of cells in the matrix.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Extremely inefficient due to a massive number of redundant computations.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest matrices.

Code Solutions

Checking out 3 solutions in different languages for Longest Increasing Path in a Matrix. Click on different languages to view the code.

class Solution {
private
  int m;
private
  int n;
private
  int[][] matrix;
private
  int[][] f;
public
  int longestIncreasingPath(int[][] matrix) {
    m = matrix.length;
    n = matrix[0].length;
    f = new int[m][n];
    this.matrix = matrix;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = Math.max(ans, dfs(i, j));
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (f[i][j] != 0) {
      return f[i][j];
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k];
      int y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
        f[i][j] = Math.max(f[i][j], dfs(x, y));
      }
    }
    return ++f[i][j];
  }
}

Video Solution

Watch the video walkthrough for Longest Increasing Path in a Matrix

Algorithms:

Depth-First SearchBreadth-First SearchTopological Sort

Patterns:

Dynamic ProgrammingMemoization

Data Structures:

ArrayMatrixGraph

Companies:

DoorDash |Nvidia |Citadel |DE Shaw |