Tutorialspoint.dev

Longest Increasing Path in Matrix

Given a matrix of N rows and M columns. From m[i][j], we can move to m[i+1][j], if m[i+1][j] > m[i][j], or can move to m[i][j+1] if m[i][j+1] > m[i][j]. The task is print longest path length if we start from (0, 0).

Examples:

Input : N = 4, M = 4
        m[][] = { { 1, 2, 3, 4 },
                  { 2, 2, 3, 4 },
                  { 3, 2, 3, 4 },
                  { 4, 5, 6, 7 } };
Output : 7
Longest path is 1 2 3 4 5 6 7.

Input : N = 2, M =2
        m[][] = { { 1, 2 },
                  { 3, 4 } };
Output :3
Longest path is either 1 2 4 or 
1 3 4.



The idea is to use dynamic programming. Maintain the 2D matrix, dp[][], where dp[i][j] store the value of length of longest increasing sequence for sub matrix starting from ith row and j-th column.
Let the longest increasing sub sequence values for m[i+1][j] and m[i][j+1] be known already as v1 and v2 respectively. Then the value for m[i][j] will be max(v1, v2) + 1.
We can start from m[n-1][m-1] as base case with length of longest increasing sub sequence be 1, moving upwards and leftwards updating the value of cells. Then the LIP value for cell m[0][0] will be the answer.

Below is the implementation of this approach:

C++

// CPP program to find longest increasing
// path in a matrix.
#include <bits/stdc++.h>
#define MAX 10
using namespace std;
  
// Return the length of LIP in 2D matrix
int LIP(int dp[][MAX], int mat[][MAX], int n, int m, int x, int y)
{
  // If value not calculated yet.
  if (dp[x][y] < 0)
  {
    int result = 0;
      
    // If reach bottom left cell, return 1.
    if (x == n-1 && y == m-1)
     return dp[x][y] = 1;
       
    // If reach the corner of the matrix.
    if (x == n-1 || y == m-1)
      result = 1;
      
    // If value greater than below cell.
    if (mat[x][y] < mat[x+1][y])
      result = 1 + LIP(dp, mat, n, m, x+1, y);
        
    // If value greater than left cell.
    if (mat[x][y] < mat[x][y+1])
      result = max(result, 1 + LIP(dp, mat, n, m, x, y+1));
        
    dp[x][y] = result;
  }
  
  return dp[x][y];
}
  
// Wrapper function
int wrapper(int mat[][MAX], int n, int m)
{
  int dp[MAX][MAX];
  memset(dp, -1, sizeof dp);
    
  return LIP(dp, mat, n, m, 0, 0);
}
  
// Driven Program
int main()
{
  int mat[][MAX] = {
                    { 1, 2, 3, 4 },
                    { 2, 2, 3, 4 },
                    { 3, 2, 3, 4 },
                    { 4, 5, 6, 7 },
                  };
    int n = 4, m = 4;    
    cout << wrapper(mat, n, m) << endl;
  
    return 0;
}

Java

// Java program to find longest increasing
// path in a matrix.
import java.util.*;
  
class GFG {
      
    // Return the length of LIP in 2D matrix
    static int LIP(int dp[][], int mat[][], int n,
                        int m, int x, int y)
    {
      // If value not calculated yet.
      if (dp[x][y] < 0)
      {
        int result = 0;
           
        // If reach bottom left cell, return 1.
        if (x == n-1 && y == m-1)
         return dp[x][y] = 1;
            
        // If reach the corner of the matrix.
         if (x == n-1 || y == m-1)
          result = 1;
           
        // If value greater than below cell.
         if (x + 1 < n && mat[x][y] < mat[x+1][y])
          result = 1 + LIP(dp, mat, n, m, x+1, y);
             
        // If value greater than left cell.
         if (y + 1 < m && mat[x][y] < mat[x][y+1])
          result = Math.max(result, 1
                    LIP(dp, mat, n, m, x, y+1));
             
        dp[x][y] = result;
      }
       
      return dp[x][y];
    }
      
    // Wrapper function
    static int wrapper(int mat[][], int n, int m)
    {
      int dp[][] = new int[10][10];
      for(int i = 0; i < 10; i++)
          Arrays.fill(dp[i],-1);
       
      return LIP(dp, mat, n, m, 0, 0);
    }
      
    /* Driver program to test above function */
    public static void main(String[] args) 
    {
        int mat[][] = {
                          { 1, 2, 3, 4 },
                          { 2, 2, 3, 4 },
                          { 3, 2, 3, 4 },
                          { 4, 5, 6, 7 },
                                         };
        int n = 4, m = 4;    
        System.out.println(wrapper(mat, n, m));
              
        }
}
  
// This code is contributed by Arnav Kr. Mandal.    

Python3

# Python3 program to find longest
# increasing path in a matrix.
MAX = 20
  
# Return the length of
# LIP in 2D matrix 
def LIP(dp, mat, n, m, x, y):
      
    # If value not calculated yet.
    if (dp[x][y] < 0):
        result = 0
          
        # If reach bottom left cell, 
        # return 1.
        if (x == n - 1 and y == m - 1):
            dp[x][y] = 1
            return dp[x][y]
  
        # If reach the corner 
        # of the matrix.
        if (x == n - 1 or y == m - 1):
            result = 1 
  
        # If value greater than below cell. 
        elif (mat[x][y] < mat[x + 1][y]):
            result = 1 + LIP(dp, mat, n, 
                             m, x + 1, y)
  
        # If value greater than left cell.
        elif (mat[x][y] < mat[x][y + 1]):
            result = max(result, 1 + LIP(dp, mat, n, 
                                         m, x, y + 1))
        dp[x][y] = result
    return dp[x][y]
  
# Wrapper function 
def wrapper(mat, n, m):
    dp = [[7 for i in range(MAX)]
             for i in range(MAX)]
    return LIP(dp, mat, n, m, 0, 0)
  
# Driver Code
mat = [[1, 2, 3, 4 ], 
       [2, 2, 3, 4 ], 
       [3, 2, 3, 4 ], 
       [4, 5, 6, 7 ]]
n = 4
m = 4
print(wrapper(mat, n, m))
  
# This code is contributed 
# by Sahil Shelangia

C#

// C# program to find longest increasing 
// path in a matrix. 
using System;
  
public class GFG
      
    // Return the length of LIP in 2D matrix 
    static int LIP(int [,]dp, int [,]mat, int n, 
                        int m, int x, int y) 
    
    // If value not calculated yet. 
    if (dp[x,y] < 0) 
    
        int result = 0; 
          
        // If reach bottom left cell, return 1. 
        if (x == n - 1 && y == m - 1) 
        return dp[x, y] = 1; 
              
        // If reach the corner of the matrix. 
        if (x == n - 1 || y == m - 1) 
        result = 1; 
          
        // If value greater than below cell. 
        if (x + 1 < n && mat[x, y] < mat[x + 1, y]) 
        result = 1 + LIP(dp, mat, n, m, x + 1, y); 
              
        // If value greater than left cell. 
        if (y + 1 < m && mat[x, y] < mat[x, y + 1]) 
        result = Math.Max(result, 1 + 
                    LIP(dp, mat, n, m, x, y + 1)); 
              
        dp[x, y] = result; 
    
      
    return dp[x,y]; 
    
      
    // Wrapper function 
    static int wrapper(int [,]mat, int n, int m) 
    
        int [,]dp = new int[10, 10]; 
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 10; j++)
            {
                dp[i, j] = -1;
            }
        }   
  
        return LIP(dp, mat, n, m, 0, 0); 
    
      
    /* Driver code */
    public static void Main() 
    
        int [,]mat= {   { 1, 2, 3, 4 }, 
                        { 2, 2, 3, 4 }, 
                        { 3, 2, 3, 4 }, 
                        { 4, 5, 6, 7 }, }; 
        int n = 4, m = 4; 
        Console.WriteLine(wrapper(mat, n, m)); 
    
  
/* This code contributed by PrinciRaj1992 */


Output:

7

Time Complexity: O(N*M).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter