Longest increasing path in a matrix

Array Dynamic Programming Depth-First Search Breadth-First Search Graph Theory Topological Sort Memoization Matrix

56.3% acceptance

Jan 12, 2026

9490

146

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).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
    if matrix.is_empty() || matrix[0].is_empty() {
      return 0;
    }
    
    let m = matrix.len();
    let n = matrix[0].len();
    let mut memo = vec![vec![0; n]; m];
    let mut max_len = 0;
    
    fn dfs(matrix: &Vec<Vec<i32>>, memo: &mut Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
      if memo[i][j] != 0 {
        return memo[i][j];
      }
      
      let m = matrix.len();
      let n = matrix[0].len();
      let mut max_path = 1;
      let dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)];
      
      for (dx, dy) in dirs.iter() {
        let ni = i as i32 + dx;
        let nj = j as i32 + dy;
        
        if ni >= 0 && ni < m as i32 && nj >= 0 && nj < n as i32 {
          let ni = ni as usize;
          let nj = nj as usize;
          if matrix[ni][nj] > matrix[i][j] {
            max_path = max_path.max(1 + dfs(matrix, memo, ni, nj));
          }
        }
      }
      
      memo[i][j] = max_path;
      max_path
    }
    
    for i in 0..m {
      for j in 0..n {
        max_len = max_len.max(dfs(&matrix, &mut memo, i, j));
      }
    }
    
    max_len
  }
}