Find the longest path in a matrix with given constraints

Last Updated : 16 Dec, 2024

Given an n*m matrix where all numbers are distinct, the task is to find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.
We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.

Example:

Input:
n = 3, m = 3
matrix[][] = [[1 2 9],
[5 3 8],
[4 6 7]]
Output: 4
Explanation: The longest increasing path is [6, 7, 8, 9].
Input:
n = 3, m = 3
matrix[][] = [[3 4 5],
[6 7 8],
[10 2 1]]
Output: 3
Explanation: The longest increasing path is [3, 4, 5].

Table of Content

Using Depth First Search - O((nm)^(nm)) Time and O(n*m) Space

The idea is to perform a depth-first search (DFS) from every cell in the matrix, exploring all possible paths that satisfy the strictly increasing condition. For each cell, we will recursively try moving in all four directions (up, down, left, right), keeping track of the current path length and ensuring that the next cell has a strictly higher value than the current cell.

C++

// C++ program to find the longest path // in a matrix with given constraints #include <bits/stdc++.h> using namespace std; int longestPath(int i, int j, vector<vector<int>> &matrix) {  int ans = 1;  vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // Check for all 4 directions  for (auto d : dir) {  int x = i + d[0];  int y = j + d[1];  // If new cells are valid and  // increasing by 1.  if (x >= 0 && x < matrix.size() && y >= 0 &&   y < matrix[0].size() && matrix[x][y] == matrix[i][j] + 1) {  ans = max(ans, 1 + longestPath(x, y, matrix));  }  }  return ans; } int longestIncreasingPath(vector<vector<int>> &matrix) {  int ans = 0;  // Find length of longest path  // from each cell i, j  for (int i = 0; i < matrix.size(); i++) {  for (int j = 0; j < matrix[0].size(); j++) {  int val = longestPath(i, j, matrix);  ans = max(ans, val);  }  }  return ans; } int main() {  vector<vector<int>> matrix = {{1, 2, 9}, {5, 3, 8}, {4, 6, 7}};  cout << longestIncreasingPath(matrix);  return 0; }

Java

// Java program to find the longest path  // in a matrix with given constraints import java.util.*; class GfG {  static int longestPath(int i, int j, int[][] matrix) {  int ans = 1;    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};    // Check for all 4 directions  for (int[] d : dir) {  int x = i + d[0];  int y = j + d[1];    // If new cells are valid and   // increasing by 1.  if (x >= 0 && x < matrix.length && y >= 0 &&   y < matrix[0].length && matrix[x][y] == matrix[i][j] + 1) {  ans = Math.max(ans, 1 + longestPath(x, y, matrix));  }  }    return ans;  }  static int longestIncreasingPath(int[][] matrix) {  int ans = 0;    // Find length of longest path   // from each cell i, j  for (int i = 0; i < matrix.length; i++) {  for (int j = 0; j < matrix[0].length; j++) {  int val = longestPath(i, j, matrix);  ans = Math.max(ans, val);  }  }    return ans;  }  public static void main(String[] args) {  int[][] matrix = {  {1, 2, 9},  {5, 3, 8},  {4, 6, 7}  };  System.out.println(longestIncreasingPath(matrix));  } }

Python

# Python program to find the longest path  # in a matrix with given constraints def longestPath(i, j, matrix): ans = 1 dir = [[-1, 0], [1, 0], [0, -1], [0, 1]] # Check for all 4 directions for d in dir: x = i + d[0] y = j + d[1] # If new cells are valid and  # increasing by 1. if x >= 0 and x < len(matrix) and y >= 0 and \ y < len(matrix[0]) and matrix[x][y] == matrix[i][j] + 1: ans = max(ans, 1 + longestPath(x, y, matrix)) return ans def longestIncreasingPath(matrix): ans = 0 # Find length of longest path  # from each cell i, j for i in range(len(matrix)): for j in range(len(matrix[0])): val = longestPath(i, j, matrix) ans = max(ans, val) return ans if __name__ == "__main__": matrix = [ [1, 2, 9], [5, 3, 8], [4, 6, 7] ] print(longestIncreasingPath(matrix))

// C# program to find the longest path  // in a matrix with given constraints using System; class GfG {  static int longestPath(int i, int j, int[][] matrix) {  int ans = 1;    int[][] dir = new int[][] {  new int[] {-1, 0}, new int[] {1, 0},   new int[] {0, -1}, new int[] {0, 1}  };    // Check for all 4 directions  foreach (var d in dir) {  int x = i + d[0];  int y = j + d[1];    // If new cells are valid and   // increasing by 1.  if (x >= 0 && x < matrix.Length && y >= 0 &&   y < matrix[0].Length && matrix[x][y] == matrix[i][j] + 1) {  ans = Math.Max(ans, 1 + longestPath(x, y, matrix));  }  }    return ans;  }  static int longestIncreasingPath(int[][] matrix) {  int ans = 0;    // Find length of longest path   // from each cell i, j  for (int i = 0; i < matrix.Length; i++) {  for (int j = 0; j < matrix[0].Length; j++) {  int val = longestPath(i, j, matrix);  ans = Math.Max(ans, val);  }  }    return ans;  }  static void Main(string[] args) {  int[][] matrix = new int[][] {  new int[] {1, 2, 9},  new int[] {5, 3, 8},  new int[] {4, 6, 7}  };  Console.WriteLine(longestIncreasingPath(matrix));  } }

JavaScript

// JavaScript program to find the longest path  // in a matrix with given constraints function longestPath(i, j, matrix) {  let ans = 1;    const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];    // Check for all 4 directions  for (const d of dir) {  const x = i + d[0];  const y = j + d[1];    // If new cells are valid and   // increasing by 1.  if (x >= 0 && x < matrix.length && y >= 0 &&   y < matrix[0].length && matrix[x][y] === matrix[i][j] + 1) {  ans = Math.max(ans, 1 + longestPath(x, y, matrix));  }  }    return ans; } function longestIncreasingPath(matrix) {  let ans = 0;    // Find length of longest path   // from each cell i, j  for (let i = 0; i < matrix.length; i++) {  for (let j = 0; j < matrix[0].length; j++) {  const val = longestPath(i, j, matrix);  ans = Math.max(ans, val);  }  }    return ans; } const matrix = [  [1, 2, 9],  [5, 3, 8],  [4, 6, 7] ]; console.log(longestIncreasingPath(matrix));

Output

Using DFS and Memoization - O(nm) Time and O(nm) Space

The idea is to use memoization to avoid recomputing same subproblems. In the recursive solution, multiple recursive calls can explore the same cell multiple times from different paths, leading to exponential time complexity.
For example, if a cell can be reached through multiple different paths, the recursive DFS will recompute the maximum path length for that cell each time it is encountered, resulting in repeated and unnecessary calculations.
Memoization solves this by storing the maximum path length for each cell after its first computation, allowing immediate retrieval of previously calculated results and preventing redundant recursive calls.

Step by step approach:

Create a memoization matrix[][] memo of size n*m, initialized with -1 to indicate no computations have been made yet.
Each memo[i][j] will store the maximum path length starting from cell (i, j).
If a cell's maximum path length is not yet computed (memo[i][j] == -1), perform the DFS exploration.
During DFS, explore all four adjacent cells that satisfy the strictly increasing condition of difference 1.
When a valid path is found from a cell, store its maximum path length in memo[i][j].
If a cell's maximum path length is already computed, directly return the memoized value.

C++

// C++ program to find the longest path  // in a matrix with given constraints #include <bits/stdc++.h> using namespace std; int longestPath(int i, int j, vector<vector<int>> &matrix,  vector<vector<int>> &memo) {    // If value is memoized  if (memo[i][j] != -1) {  return memo[i][j];  }    int ans = 1;    vector<vector<int>> dir = {{-1,0}, {1,0}, {0, -1}, {0, 1}};    // Check for all 4 directions  for (auto d: dir) {  int x = i+d[0];  int y = j+d[1];    // If new cells are valid and   // increasing by 1.  if (x>=0 && x<matrix.size() && y>=0 &&   y<matrix[0].size() && matrix[x][y]==matrix[i][j]+1) {  ans = max(ans, 1+longestPath(x, y, matrix, memo));  }  }    return memo[i][j] = ans; } int longestIncreasingPath(vector<vector<int>>& matrix) {  int ans = 0;    int n = matrix.size(), m = matrix[0].size();  vector<vector<int>> memo(n, vector<int>(m, -1));    // Find length of longest path   // from each cell i, j  for (int i=0; i<matrix.size(); i++) {  for (int j=0; j<matrix[0].size(); j++) {  int val = longestPath(i, j, matrix, memo);  ans = max(ans, val);  }  }    return ans; } int main() {  vector<vector<int>> matrix =   {{1, 2, 9},  {5, 3, 8},  {4, 6, 7}};  cout << longestIncreasingPath(matrix);  return 0; }

Java

// Java program to find the longest path  // in a matrix with given constraints import java.util.Arrays; class GfG {  static int longestPath(int i, int j, int[][] matrix, int[][] memo) {    // If value is memoized  if (memo[i][j] != -1) {  return memo[i][j];  }  int ans = 1;  int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // Check for all 4 directions  for (int[] d : dir) {  int x = i + d[0];  int y = j + d[1];  // If new cells are valid and  // increasing by 1.  if (x >= 0 && x < matrix.length && y >= 0 &&  y < matrix[0].length && matrix[x][y] == matrix[i][j] + 1) {  ans = Math.max(ans, 1 + longestPath(x, y, matrix, memo));  }  }  return memo[i][j] = ans;  }  static int longestIncreasingPath(int[][] matrix) {  int ans = 0;  int n = matrix.length, m = matrix[0].length;  int[][] memo = new int[n][m];  for (int[] row : memo) {  Arrays.fill(row, -1);  }  // Find length of longest path  // from each cell i, j  for (int i = 0; i < matrix.length; i++) {  for (int j = 0; j < matrix[0].length; j++) {  int val = longestPath(i, j, matrix, memo);  ans = Math.max(ans, val);  }  }  return ans;  }  public static void main(String[] args) {  int[][] matrix = {  {1, 2, 9},  {5, 3, 8},  {4, 6, 7}  };  System.out.println(longestIncreasingPath(matrix));  } }

Python

# Python program to find the longest path  # in a matrix with given constraints def longestPath(i, j, matrix, memo): # If value is memoized if memo[i][j] != -1: return memo[i][j] ans = 1 dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Check for all 4 directions for dx, dy in dir: x, y = i + dx, j + dy # If new cells are valid and  # increasing by 1. if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and\ matrix[x][y] == matrix[i][j] + 1: ans = max(ans, 1 + longestPath(x, y, matrix, memo)) memo[i][j] = ans return ans def longestIncreasingPath(matrix): n, m = len(matrix), len(matrix[0]) memo = [[-1 for _ in range(m)] for _ in range(n)] ans = 0 # Find length of longest path  # from each cell i, j for i in range(n): for j in range(m): ans = max(ans, longestPath(i, j, matrix, memo)) return ans if __name__ == "__main__": matrix = [ [1, 2, 9], [5, 3, 8], [4, 6, 7] ] print(longestIncreasingPath(matrix))

// C# program to find the longest path  // in a matrix with given constraints using System; class GfG {  static int longestPath(int i, int j, int[,] matrix, int[,] memo) {    // If value is memoized  if (memo[i, j] != -1) {  return memo[i, j];  }  int ans = 1;  int[,] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };  // Check for all 4 directions  for (int k = 0; k < dir.GetLength(0); k++) {  int x = i + dir[k, 0];  int y = j + dir[k, 1];  // If new cells are valid and   // increasing by 1.  if (x >= 0 && x < matrix.GetLength(0) && y >= 0 &&  y < matrix.GetLength(1) && matrix[x, y] == matrix[i, j] + 1) {  ans = Math.Max(ans, 1 + longestPath(x, y, matrix, memo));  }  }  return memo[i, j] = ans;  }  static int longestIncreasingPath(int[,] matrix) {  int n = matrix.GetLength(0), m = matrix.GetLength(1);  int[,] memo = new int[n, m];  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  memo[i, j] = -1;  }  }  int ans = 0;  // Find length of longest path   // from each cell i, j  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  ans = Math.Max(ans, longestPath(i, j, matrix, memo));  }  }  return ans;  }  static void Main(string[] args) {  int[,] matrix = {  { 1, 2, 9 },  { 5, 3, 8 },  { 4, 6, 7 }  };  Console.WriteLine(longestIncreasingPath(matrix));  } }

JavaScript

// JavaScript program to find the longest path  // in a matrix with given constraints function longestPath(i, j, matrix, memo) {  // If value is memoized  if (memo[i][j] !== -1) {  return memo[i][j];  }  let ans = 1;  const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];  // Check for all 4 directions  for (let [dx, dy] of dir) {  let x = i + dx;  let y = j + dy;  // If new cells are valid and   // increasing by 1.  if (x >= 0 && x < matrix.length && y >= 0 &&  y < matrix[0].length && matrix[x][y] === matrix[i][j] + 1) {  ans = Math.max(ans, 1 + longestPath(x, y, matrix, memo));  }  }  memo[i][j] = ans;  return ans; } function longestIncreasingPath(matrix) {  const n = matrix.length, m = matrix[0].length;  const memo = Array.from({ length: n }, () => Array(m).fill(-1));  let ans = 0;  // Find length of longest path   // from each cell i, j  for (let i = 0; i < n; i++) {  for (let j = 0; j < m; j++) {  ans = Math.max(ans, longestPath(i, j, matrix, memo));  }  }  return ans; } const matrix = [  [1, 2, 9],  [5, 3, 8],  [4, 6, 7] ]; console.log(longestIncreasingPath(matrix));