Longest Increasing Path in a Matrix

Approach 1: Using Recursion 

So for finding the longest increasing path let’s say from the cell (i,j), we just find the longest increasing path from the cells (i+1,j), (i-1,j), (i,j+1), and (i,j-1) and add 1 to the ones from these four where the value in the cell is just one greater than than the value in the cell (i,j). Then take the maximum among all the four of them. 

Likewise, we’ll get the answer for every cell and then we just need to see which cell has the maximum answer. 

You must have noticed that in this approach, we’ll need to call the recursive function each time, and therefore, there will be many overlapping subproblems and the time complexity of the recursive approach will be exponential. 

Below is the code of this approach.

// Program to find the longest path in a matrix
#include <bits/stdc++.h>
using namespace std;

// This function will return the length of the longest path beginning with the cell matrix[i][j].
int Longest(int i, int j, vector<vector<int>>&matrix,int n,int m)
{
    if (i < 0 || i >= n || j < 0 || j >= n)//if the cell is out of the matrix return 0
        return 0;


    // Variables a,b,c,d will store the path lengths of all the four directions respectively.
    int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;

    // For all the four directions, we check if the cell in that direction is valid,
    // and the value in it is just 1 greater than the value is the current (i,j) cell,
    // then we find the answer for that cell and add 1 to it. 
    if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
        a = 1 + Longest(i, j + 1, matrix,n,m);

    if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
        b = 1 + Longest(i, j - 1, matrix,n,m);

    if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
        c = 1 + Longest(i - 1, j, matrix,n,m);

    if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
        d = 1 + Longest(i + 1, j, matrix,n,m);

    // If cells in all the four directions are just not valid or not differ from this cell by 1, 
    // then we just take this cell itself, so the length is 1. And we compare the other answers with this 1 also. 
    return max({a,b,c,d,1});// maximum of all these will be the answer for (i,j). 
}

// This function returns the length of the longest path beginning from any cell
int longest_path_length(int n,int m,vector<vector<int>>&matrix)
{
    int ans = 1; // Initialize the answer by 1 because 1 is the minimum length always possible.

    // Find longest path beginning from all cells
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {


          ans=max(ans,Longest(i, j, matrix, n,m));
          // Update ans if the current cell's answer is greater than the current answer. 
        }
    }
    return ans;
}


int main()
{
    int n,m;
    cin>>n>>m;  // input the value of n and m
    vector<vector<int>>matrix(n,vector<int>(m));
    for(int i = 0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>matrix[i][j];  // input the values of matrix
        }
    }
    cout << "The length of the longest path is: "
        << longest_path_length(n,m,matrix); 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

3 //number of rows
3 // number of column

//matrix
1 2 9
5 3 8
4 6 7

You can also try this code with Online C++ Compiler

Run Code

Output

The length of the longest path is: 4 

You can also try this code with Online C++ Compiler

Run Code

To optimize this, we use dynamic programming.

Approach 2: Using Dynamic Programming 

In this solution, we just try to optimize the previous idea by storing the results of cells in a 2-D dp array, so that we can use them later when needed. 

(Also check out Types of Matrix)

The steps of this approach involve: 

1. Input the n and m values and the matrix.
2. Create a 2-D dp vector and initialize the values in it to -1.
3. Find the dp[i][j] value for each cell (i,j) where the dp value is still -1.
4. For doing step 3, we have made another function that calculates the value for cell (i,j) by looking at the dp[i][j] value. 
   1. If the dp[i][j] is not -1, then we’ve already calculated the answer for this cell and we’ll just return it.
   2. Otherwise, we call the same function for adjacent cells in the directions which are valid, i.e; inside the matrix and the value in it differing by 1 from the value in the current cell. Then we add 1 to the returned answers for these cells.
   3. If no cell is valid, then the answer is 1 because the cell (i,j) will itself form a path. 
   4. The maximum of these will give the answer for cell (i,j). 
5. While calculating the dp[i][j] for each cell, we keep updating the ans to the maximum of ans and dp[i][j].
6. Once we’re done with all the cells, our ans variable contains the required length so we return it.

Below is the code for the above-discussed approach.

// Program to find the longest path in a matrix
#include <bits/stdc++.h>
using namespace std;

// This function will return the length of the longest path beginning with the cell matrix[i][j].
int Longest(int i, int j, vector<vector<int>>&matrix,vector<vector<int>>&dp,int n,int m)
{
    if (i < 0 || i >= n || j < 0 || j >= n)//if the cell is out of the matrix return 0
        return 0;

    if (dp[i][j] != -1)//If we've already found out the answer for this i,j, then just return the calculated answer
        return dp[i][j];

    // Variables a,b,c,d will store the path lengths of all the four directions respectively.
    int a = INT_MIN, b = INT_MIN, c = INT_MIN, d = INT_MIN;

    // For all the four directions, we check if the cell in that direction is valid,
    // and the value in it is just 1 greater than the value is the current (i,j) cell,
    // then we find the answer for that cell and add 1 to it. 
    if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
        a = 1 + Longest(i, j + 1, matrix, dp,n,m);

    if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
        b = 1 + Longest(i, j - 1, matrix, dp,n,m);

    if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
        c = 1 + Longest(i - 1, j, matrix, dp,n,m);

    if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
        d = 1 + Longest(i + 1, j, matrix, dp,n,m);

    // If cells in all the four directions are just not valid or not differ from this cell by 1, 
    // then we just take this cell itself, so the length is 1. And we compare the other answers with this 1 also. 
    return dp[i][j] = max({a,b,c,d,1});// maximum of all these will be the answer for (i,j). 
                                      //therefore, stored in dp[i][j].
}

// This function returns length of the longest path beginning from any cell
int longest_path_length(int n,int m,vector<vector<int>>&matrix)
{
    int ans = 1; // Initialize the answer by 1 because 1 is the minimum length always possible.

    // Create the dp vector and initialise the values by -1.
    vector<vector<int>>dp(n,vector<int>(m,-1));

    // Find longest path beginning from all cells
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == -1)
                Longest(i, j, matrix, dp,n,m);

            // Update ans if the current cell's answer is greater than the current answer. 
            ans = max(ans, dp[i][j]);
        }
    }

    return ans;
}


int main()
{
    int n,m;
    cin>>n>>m;     // input the value of n and m
    vector<vector<int>>matrix(n,vector<int>(m));
    for(int i = 0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>matrix[i][j];   // input the values of matrix
        }
    }
    cout << "The length of the longest path is: "
        << longest_path_length(n,m,matrix);
    return 0;
} 

You can also try this code with Online C++ Compiler

Run Code

Input

3 //number of rows

3 // number of column

//matrix
1 2 9
5 3 8
4 6 7

You can also try this code with Online C++ Compiler

Run Code

Output   

The length of the longest path is: 4 

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time complexity

The time complexity O(n*m), where n is the number of rows and m is the number of columns.

Reason: Because we’re calculating the values of all the cells once and there are a total of n*m cells.

Space complexity

O(n*m), where n is the number of rows and m is the number of columns.

Reason: We’re storing the values of all cells which will take O(n*m) space and the matrix itself will take another O(m*n) space. Thus the total space complexity is O(2(m*n)), which is nearly equal to the O(m*n).

Check out this problem - Count Inversions

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is an optimization method used in various programming problems.

Where is dynamic programming used?

Dynamic programming is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

What are overlapping subproblems?

A problem is said to have overlapping subproblems if it can be divided into smaller problems that are reused multiple times.

Does dynamic programming have overlapping subproblems?

Yes, dynamic programming is only used in problems where there are overlapping subproblems.

Conclusion

In this article, we’ve discussed the longest increasing path in a matrix problem. Here a very important method has been used which is called dynamic programming. This is a very important topic and there are numerous interesting problems related to this topic. 

Recommended Problems:

• Tower of Hanoi 
• Minimum cost to convert to the given string 
• Wildcard pattern matching 
• Rod cutting problem
• Path With Minimum Effort
• Top Dynamic Programming Questions 

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, Interview For Product Based Companies, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. 

Do check out some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Happy Coding!