Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Path in a Matrix
2.
Problem Statement
3.
Approach 1: Using Recursion 
4.
Approach 2: Using Dynamic Programming 
4.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is dynamic programming?
5.2.
Where is dynamic programming used?
5.3.
What are overlapping subproblems?
5.4.
Does dynamic programming have overlapping subproblems?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Longest Increasing Path in a Matrix

Author Shreya Deep
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A matrix is a rectangular array-based representation of numbers arranged in rows and columns. A cell in a matrix is represented using its row number and column number. A cell is in the ith row and jth column, then, we denote its position by (i,j).

In this blog, we’ll learn how to find the longest increasing path in a matrix and get the most efficient solution. The solutions will involve techniques called recursion and dynamic programming. So, it’s suggested that you revise these topics once.

Path in a Matrix

A path in a matrix is a sequence of cells covered in traversing from one cell to another. 

Let’s understand this with the help of an example

Matrix

The above matrix is a 3x3 matrix. If we consider the starting position to be ( 0,1) and the final position to be (2,1). The sequence of cells denoted by the arrows above can be said to be a path, i.e; (0,1) -> (0,2) -> (1,2) -> (1,1) -> (1,0) -> (2,0) -> (2,1)

Problem Statement

Given an N * M matrix, containing distinct numbers, find the length of the longest increasing path in that matrix such that the numbers in the cells along the path are in increasing order with a difference of 1.

Note: You’re allowed to move in 4 directions, left, right, top, and down. From a cell (i,j), you can move to cell (i+1,j), (i,j+1), (i-1,j), and (i,j-1).  

For example: 

INPUT : N = 3, M = 3

Matrix = {{1,2,9},{5,3,8},{4,6,7}}

OUTPUT:  4

The longest increasing path will be 6-7-8-9. All the elements in this path differ by 1 and its length is 4. 

The idea here is to find the longest increasing path starting with each cell. And then among them, we’ll just take the one having the maximum length. 

There are two ways to implement this idea. One uses recursion and another uses dynamic programming. Let’s have a look at them one by one. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Input

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

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

Output

The length of the longest path is: 4 

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;
} 

Input

3 //number of rows

3 // number of column

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

Output   

The length of the longest path is: 4 

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:


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!

Previous article
Expected Swaps to Sort an Array when Probability of Swapping for Every Inversion Pair is Equal
Next article
Minimum Number of Removals to Make a Mountain Array
Live masterclass