Longest Increasing Path in a Matrix [4 approaches explained]

This problem involves navigating a 2D matrix to find the longest path such that each element in the path is strictly greater than the previous one.

Table of Contents

1. Problem Statement
2. Key Takeaways
3. Approach 1: BFS
4. Approach 2: Depth-First Search (DFS)
5. Approach 3: Dynamic Programming
6. Approach 4: Toposort
7. Real-World Examples

Problem Statement

Given a two-dimensional matrix of integers, our task is to find the length of the longest increasing path. In this context, a path is a sequence of adjacent cells in the matrix, and a path is considered "increasing" if each element in the path is strictly greater than the previous element. We need to find the length of the longest such path in the matrix.

Example:

Let's consider a 3x3 matrix as an example:

[
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]

In this matrix, the longest increasing path is [1, 2, 6, 9] with a length of 4. The path starts at the element 1, moves to 2, then 6, and finally 9. Each element in this path is strictly greater than the previous one, making it the longest increasing path in the matrix.

Key Takeaways:

Key takeaways for the four approaches to solving the "Longest Increasing Path in a Matrix" problem:

1. Dynamic Programming with DFS:

• Memoization for longest increasing path.
• DFS for path length.
• Easy to understand.
• Time: O(Rows x Columns), Space: O(Rows x Columns).
• Suitable for smaller matrices.

2. Topological Sort:

• Treat as a graph, find DAG.
• Topological sort for longest path.
• Efficient for larger matrices.
• Time: O(Rows x Columns), Space: O(Rows x Columns).
• Suitable for complex structures.

3. Depth-First Search (DFS):

• Explore matrix with DFS.
• Record maximum path length.
• Simple, suitable for smaller matrices.
• Time: O(Rows x Columns), Space: O(1).
• Suitable for smaller matrices.

4. Breadth-First Search (BFS):

• Explore matrix with BFS.
• Record maximum path length.
• Simple, suitable for smaller matrices.
• Time: O(Rows x Columns), Space: O(Rows x Columns).
• Suitable for smaller matrices.

Approach 1:Breadth-First Search (BFS)

The simplest approach the comes to our mind while solving this problem is BFS approach.We start at each cell in the matrix and perform a breadth-first traversal to find the longest increasing path starting from that cell.We record the maximum flood path length of all nodes.

Intutive Explanation:

1. Start from any cell and explore adjacent cells with larger values.
2. Use BFS to systematically search all possible paths.
3. Record the length of increasing paths while exploring.
4. Maintain a maximum path length encountered during the process.
5. The maximum path length found represents the longest increasing path in the matrix.

BFS explores all paths systematically.It considers shorter paths before longer ones.Efficiently covers all potential paths without redundancy.Records the maximum path length encountered, ensuring a correct solution.

Algorithm Steps:

1. Create a queue for BFS and initialize a variable maxLength to 0. This variable will store the length of the longest increasing path found.

2. Initialize a 2D array (dp) to store the length of the longest increasing path starting from each cell. Set all values in this array to 0 initially.

3. Initialize a queue with pairs of coordinates (row, column) of all cells in the matrix.

4. Perform BFS as follows:

   • Dequeue a cell from the queue.
   • Examine its neighboring cells (up, down, left, right) that are valid and have increasing values compared to the current cell.
   • For each valid neighbor, calculate the length of the path starting from the neighbor and compare it with the current cell's path length. If the neighbor's path length is greater, update it and enqueue the neighbor for further exploration.
   • Keep track of the maximum path length found during BFS.

5. Continue this process until the queue is empty, which means you have explored all possible paths.

6. Return maxLength as the result, which represents the length of the longest increasing path in the matrix.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;

        int rows = matrix.size();
        int cols = matrix[0].size();
        int maxLength = 0;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        queue<pair<int, int>> q;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                q.push({i, j});
            }
        }

        while (!q.empty()) {
            pair<int, int> cell = q.front();
            q.pop();
            int x = cell.first;
            int y = cell.second;

            for (const pair<int, int>& dir : directions) {
                int newX = x + dir.first;
                int newY = y + dir.second;

                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
                    matrix[newX][newY] > matrix[x][y]) {
                    if (dp[newX][newY] < dp[x][y] + 1) {
                        dp[newX][newY] = dp[x][y] + 1;
                        maxLength = max(maxLength, dp[newX][newY]);
                        q.push({newX, newY});
                    }
                }
            }
        }

        return maxLength + 1; // Add 1 to get the length of the path, including the starting cell.
    }
};

int main() {
    vector<vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };

    Solution solution;
    int longestPath = solution.longestIncreasingPath(matrix);

    cout << "The longest increasing path length is: " << longestPath << endl;

    return 0;
}

Example:

Let's use this same example matrix :

Matrix:
[
 [9, 9, 4],
 [6, 6, 8],
 [2, 1, 1]
]

Step 1: Initialization

• Initialize maxLength to 0.
• Initialize the dp array with zeros.

Step 2: BFS Using a Queue

• Enqueue all cells' coordinates into the queue initially.

Step 3: BFS Iteration

1. Dequeue cell (0, 0) with a value of 9.

   1. Examine valid neighbors: (0, 1) and (1, 0).
   2. For (0, 1), the value is the same (9), so no increase in path length.
   3. For (1, 0), the value is 6, so the path length becomes 1 (from 9 to 6).

2. Dequeue cell (0, 1) with a value of 9.

   1. Examine valid neighbors: (0, 2) and (1, 1).
   2. For (0, 2), the value is 4, so the path length becomes 1 (from 9 to 4).
   3. For (1, 1), the value is the same (9), so no increase in path length.

3. Dequeue cell (0, 2) with a value of 4.

   1. Examine the valid neighbor (1, 2).
   2. For (1, 2), the value is 8, so the path length becomes 1 (from 4 to 8).

4. Continue BFS, dequeuing cells and updating path lengths as needed.

Step 4: BFS Result

After BFS exploration, the dp array contains the following path lengths:

dp:
[
 [1, 2, 4],
 [3, 4, 3],
 [2, 1, 2]
]

The maximum path length found in the dp array is 4, representing the longest increasing path [1, 2, 6, 9] in the matrix.

Step 5: Return the Result

The result is maxLength, which is 4. The longest increasing path length in the matrix is 4.

This BFS approach allows you to systematically explore and find the longest increasing path in the matrix by utilizing a queue for traversal and a dynamic programming array to store path lengths.

Approach 2: Depth-First Search (DFS)

One way to approach this problem is by using Depth-First Search (DFS). We start at each cell in the matrix and perform a depth-first traversal to find the longest increasing path starting from that cell. We keep track of the maximum path length encountered during this process.

Intutive Explanation:

1. Start from any cell and explore adjacent cells with larger values.
2. Use DFS to calculate the length of increasing paths.
3. Store path lengths using memoization to avoid redundancy.
4. Record the maximum path length encountered during the process.
5. The recorded maximum represents the longest increasing path in the matrix.

The DFS approach works because it explores all possible paths starting from each cell, ensuring that we consider every potential increasing path in the matrix.By using memoization,we avoid redundant calculations, making the algorithm efficient.The maximum length we record during this process represents the longest increasing path in the matrix.

Algorithm Steps:

1. Initialize a variable maxPathLength to 0. This variable will store the length of the longest increasing path found.

2. Iterate through each cell in the matrix.

3. For each cell, perform a depth-first search to find the longest increasing path starting from that cell. During the DFS, keep track of the length of the current path and update maxPathLength if a longer path is found.

4. Return maxPathLength as the result.

Implementation (DFS):

#include <iostream>
#include <vector>

using namespace std;

int longestIncreasingPath(vector<vector<int>>& matrix) {
    if (matrix.empty()) {
        return 0;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector<vector<int>> memo(rows, vector<int>(cols, -1));
    int maxPathLength = 0;

    function<int(int, int)> dfs = [&](int row, int col) {
        if (memo[row][col] != -1) {
            return memo[row][col];
        }

        int longestPath = 1;  // At least the current cell itself is part of the path.

        for (const auto& dir : directions) {
            int newRow = row + dir.first;
            int newCol = col + dir.second;
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
                matrix[newRow][newCol] > matrix[row][col]) {
                longestPath = max(longestPath, 1 + dfs(newRow, newCol));
            }
        }

        memo[row][col] = longestPath;
        return longestPath;
    };

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            maxPathLength = max(maxPathLength, dfs(i, j));
        }
    }

    return maxPathLength;
}

int main() {
    vector<vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };

    int result = longestIncreasingPath(matrix);
    cout << "The longest increasing path length is: " << result << endl;

    return 0;
}

Explanation:

Consider the following example matrix:

Matrix:
[
 [9, 9, 4],
 [6, 6, 8],
 [2, 1, 1]
]

We want to find the longest increasing path in this matrix, where an increasing path consists of cells with values in strictly increasing order.

DFS Approach Explanation:

1. We start at each cell in the matrix and perform a DFS to find the longest increasing path starting from that cell.

2. We use a recursive DFS function that explores neighboring cells and records the length of the longest increasing path from the current cell.

3. We maintain a memoization table (memo) to avoid redundant calculations. The memo table stores the length of the longest increasing path starting from each cell. Initially, all entries in the memo table are set to -1.

Now, let's perform DFS from the top-left cell (0, 0) in the example matrix:

DFS from Cell (0, 0) with Value 9:

Starting at cell (0, 0) with a value of 9:

• We explore neighboring cells that have greater values and are valid moves (up, down, left, and right).
• We move right to cell (0, 1) with a value of 9. Since the value is the same, we don't increase the path length.
• We move down to cell (1, 0) with a value of 6. This is a valid move as 6 is less than 9, so we increase the path length by 1.
• From cell (1, 0), we continue the DFS. We move right to cell (1, 1) with a value of 6. Again, we increase the path length by 1.
• Now, we explore all directions from (1, 1) but find no valid moves with greater values.

The DFS from cell (0, 0) returns a path length of 2.

DFS from Cell (0, 1) with Value 9:

Starting at cell (0, 1) with a value of 9:

• We move down to cell (1, 1) with a value of 6. Since 6 is less than 9, we increase the path length by 1.
• From cell (1, 1), we continue the DFS. We move right to cell (1, 2) with a value of 8. This is a valid move as 8 is greater than 6, so we increase the path length by 1.
• Now, we explore all directions from (1, 2) but find no valid moves with greater values.

The DFS from cell (0, 1) returns a path length of 2.

DFS from Cell (0, 2) with Value 4:

Starting at cell (0, 2) with a value of 4:

• We move down to cell (1, 2) with a value of 8. This is a valid move as 8 is greater than 4, so we increase the path length by 1.
• Now, we explore all directions from (1, 2) but find no valid moves with greater values.

The DFS from cell (0, 2) returns a path length of 1.

DFS from Cell (1, 0) with Value 6:

Starting at cell (1, 0) with a value of 6:

• We move right to cell (1, 1) with a value of 6. Since the value is the same, we don't increase the path length.
• From cell (1, 1), we continue the DFS. We move right to cell (1, 2) with a value of 8. This is a valid move as 8 is greater than 6, so we increase the path length by 1.
• Now, we explore all directions from (1, 2) but find no valid moves with greater values.

The DFS from cell (1, 0) returns a path length of 2.

DFS from Cell (1, 1) with Value 6:

Starting at cell (1, 1) with a value of 6:

• We explore all directions from (1, 1) but find no valid moves with greater values.

The DFS from cell (1, 1) returns a path length of 1.

DFS from Cell (1, 2) with Value 8:

Starting at cell (1, 2) with a value of 8:

• Now, we explore all directions from (1, 2) but find no valid moves with greater values.

The DFS from cell (1, 2) returns a path length of 1.

DFS from Cell (2, 0) with Value 2:

Starting at cell (2, 0) with a value of 2:

• We move right to cell (2, 1) with a value of 1. Since 1 is less than 2, we increase the path length by 1.
• Now, we explore all directions from (2, 1) but find no valid moves with greater values.

The DFS from cell (2, 0) returns a path length of 2.

DFS from Cell (2, 1) with Value 1:

Starting at cell (2, 1) with a value of 1:

• Now, we explore all directions from (2, 1) but find no valid moves with greater values.

The DFS from cell (2, 1) returns a path length of 1.

DFS from Cell (2, 2) with Value 1:

Starting at cell (2, 2) with a value of 1:

• Now, we explore all directions from (2, 2) but find no valid moves with greater values.

The DFS from cell (2, 2) returns a path length of 1.

Conclusion:

After performing DFS from each cell in the matrix, we record the following path lengths:

• From cell (0, 0): Path length = 2
• From cell (0, 1): Path length = 2
• From cell (0, 2): Path length = 1
• From cell (1, 0): Path length = 2
• From cell (1, 1): Path length = 1
• From cell (1, 2): Path length = 1
• From cell (2, 0): Path length = 2
• From cell (2, 1): Path length = 1
• From cell (2, 2): Path length = 1

The longest increasing path in the matrix is [1, 2, 6, 9], and its length is 4. The DFS approach successfully finds the longest increasing path in the matrix.

Approach 3: Dynamic Programming

Another approach to solving this problem is by using Dynamic Programming. In this approach, we use a memoization table to store the length of the longest increasing path starting from each cell. We iteratively fill the memoization table while traversing the matrix and keep track of the maximum path length encountered.

Intutive Explanation:

1. Choose a cell as the starting point.
2. Use DFS to explore and calculate path lengths.
3. Store lengths in a memoization table to avoid redundancy.
4. Keep track of the maximum path length encountered.
5. Repeat for all cells.
6. The maximum recorded length is the longest increasing path.

Dynamic programming approach with memoization works by breaking the problem into smaller subproblems, efficiently avoiding redundant calculations using memoization, and ultimately finding the global maximum, which represents the longest increasing path in the matrix.

Algorithm Steps:

1. Initialize a variable maxPathLength to 0. This variable will store the length of the longest increasing path found.

2. Initialize a memoization table (a 2D array) to store the length of the longest increasing path starting from each cell. Initialize all entries in the memoization table to 0.

3. Iterate through each cell in the matrix.

4. For each cell, perform a depth-first traversal to find the longest increasing path starting from that cell. During the DFS, keep track of the length of the current path and update the corresponding entry in the memoization table if a longer path is found.

5. Return maxPathLength as the result.

Implementation (Dynamic Programming):

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        int maxLength = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int pathLength = dfs(matrix, dp, i, j);
                maxLength = max(maxLength, pathLength);
            }
        }
        
        return maxLength;
    }
    
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int x, int y) {
        if (dp[x][y] != 0) return dp[x][y];
        
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxLength = 1;
        
        for (auto dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            
            if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix[0].size() && matrix[newX][newY] > matrix[x][y]) {
                int length = 1 + dfs(matrix, dp, newX, newY);
                maxLength = max(maxLength, length);
            }
        }
        
        dp[x][y] = maxLength;
        return maxLength;
    }
};

int main() {
    vector<vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };

    Solution solution;
    int longestPath = solution.longestIncreasingPath(matrix);

    cout << "The longest increasing path length is: " << longestPath << endl;

    return 0;
}

Explanation:

We'll use the following example matrix:

Matrix:
[
 [9, 9, 4],
 [6, 6, 8],
 [2, 1, 1]
]

Step 1: Initialization

• We start by initializing a DP table (dp) with the same dimensions as the matrix. Each cell dp[i][j] will store the length of the longest increasing path that can be formed starting from the cell (i, j).

• Initialize a variable maxLength to store the length of the longest increasing path found. Set maxLength to 0 initially.

Step 2: Dynamic Programming (DP) Using DFS

Now, let's perform dynamic programming using a Depth-First Search (DFS) approach to find the longest increasing path from each cell in the matrix.

Starting from Cell (0, 0) with Value 9

1. We start DFS from cell (0, 0) with a value of 9.

2. The dfs function explores neighboring cells that have greater values and are valid moves (up, down, left, and right).

3. It moves right to cell (0, 1) with a value of 9. Since the value is the same, it doesn't increase the path length.

4. It moves down to cell (1, 0) with a value of 6. This is a valid move as 6 is less than 9, so it increases the path length by 1.

5. From cell (1, 0), it continues the DFS. It moves right to cell (1, 1) with a value of 6. Again, it increases the path length by 1.

6. Now, it explores all directions from (1, 1) but finds no valid moves with greater values.

7. The DFS from cell (0, 0) returns a path length of 2.

DFS from Other Cells

Perform a similar DFS process starting from each cell in the matrix. Here are the results for other cells:

• DFS from cell (0, 1) returns a path length of 2.
• DFS from cell (0, 2) returns a path length of 1.
• DFS from cell (1, 0) returns a path length of 2.
• DFS from cell (1, 1) returns a path length of 1.
• DFS from cell (1, 2) returns a path length of 1.
• DFS from cell (2, 0) returns a path length of 2.
• DFS from cell (2, 1) returns a path length of 1.
• DFS from cell (2, 2) returns a path length of 1.

Step 3: Finding the Longest Path

After performing DFS from each cell in the matrix, we record the following path lengths:

• From cell (0, 0): Path length = 2
• From cell (0, 1): Path length = 2
• From cell (0, 2): Path length = 1
• From cell (1, 0): Path length = 2
• From cell (1, 1): Path length = 1
• From cell (1, 2): Path length = 1
• From cell (2, 0): Path length = 2
• From cell (2, 1): Path length = 1
• From cell (2, 2): Path length = 1

The longest increasing path in the matrix is [1, 2, 6, 9], and its length is 4.

Approach 4: Topological Sort Approach:

To use topological sort, we can treat each cell in the matrix as a node in a directed acyclic graph (DAG). The edges in the graph represent increasing paths. We'll add edges from a cell (i, j) to its valid neighboring cells (x, y) if matrix[x][y] is greater than matrix[i][j]. Once we get our graph representation, you can perform a topological sort to find the longest path.

Intutive Explanation:

1. Treat the matrix as a graph, with each cell as a node.
2. Calculate in-degrees for each node to create a Directed Acyclic Graph (DAG).
3. Start with nodes having zero in-degrees.
4. Perform topological sort to find the longest path.
5. Keep track of the maximum path length encountered.
6. The recorded maximum length is the longest increasing path in the matrix.

The Topological Sort approach is a robust solution for the Longest Increasing Path in a Matrix problem. It treats the matrix as a directed graph, ensuring paths are strictly increasing. Through topological sorting, it explores paths systematically and efficiently, avoiding redundant calculations by maintaining a record of the maximum path length encountered. This makes it a reliable method for finding the longest increasing path in the matrix.

Algorithm Steps:

1. Build a graph where each cell in the matrix is a node, and there is a directed edge from cell (i, j) to (x, y) if matrix[x][y] is greater than matrix[i][j]. This step creates the DAG.

2. Create an array inDegree to keep track of the in-degrees (the number of incoming edges) for each node. Initialize all in-degrees to 0 initially.

3. Initialize a queue and add all nodes (cells) with an in-degree of 0 to the queue. These are the nodes with no incoming edges.

4. Initialize a variable maxPathLength to 0. This variable will store the length of the longest path found.

5. Perform topological sort as follows:

   • Dequeue a node from the queue.
   • For each of its neighbors, decrease their in-degree by 1 because we've processed an edge.
   • If the in-degree of a neighbor becomes 0, enqueue that neighbor.
   • While processing each node, keep track of the maximum path length found.

6. Continue this process until the queue is empty.

7. Return maxPathLength as the result, which represents the length of the longest increasing path in the matrix.

**Example (Topological Sort Approach):

Matrix:
[
 [9, 9, 4],
 [6, 6, 8],
 [2, 1, 1]
]

Step 1: Build the Directed Acyclic Graph (DAG)

• Convert the matrix into a directed acyclic graph (DAG) by adding edges between cells where matrix[x][y] is greater than matrix[i][j]. The graph is as follows:

Graph:
(0,0) --> (0,1) --> (0,2)
 |        |
 v        v
(1,0)    (1,1) <-- (1,2)
                    |
                    v
(2,0) --> (2,1)

Step 2: Initialize inDegree Array

• Initialize the inDegree array to keep track of in-degrees for each node (cell). All in-degrees are initially 0.

Step 3: Initialize the Queue

• Enqueue nodes (0,0), (0,1), and (2,0) since they have no incoming edges (in-degree is 0).

Step 4: Initialize maxPathLength

• Initialize maxPathLength to 0.

Step 5: Topological Sort

• Start dequeuing nodes and processing them.

Step 6: Continue Topological Sort

• Continue the topological sort process until the queue is empty.

Step 7: Return the Result

• The result is maxPathLength, which is the length of the longest increasing path in the matrix.

Implementation:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        
        // Initialize in-degrees and create a graph
        vector<vector<int>> inDegree(rows, vector<int>(cols, 0));
        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        // Calculate in-degrees and build the graph
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (const auto& dir : directions) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > matrix[i][j]) {
                        inDegree[x][y]++;
                    }
                }
            }
        }
        
        // Initialize the queue with nodes that have no incoming edges
        queue<pair<int, int>> q;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (inDegree[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }
        
        int maxPathLength = 0;
        
        // Perform topological sort
        while (!q.empty()) {
            int size = q.size();
            maxPathLength++;
            
            for (int k = 0; k < size; k++) {
                pair<int, int> node = q.front();
                q.pop();
                int x = node.first;
                int y = node.second;
                
                for (const auto& dir : directions) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && matrix[newX][newY] > matrix[x][y]) {
                        inDegree[newX][newY]--;
                        if (inDegree[newX][newY] == 0) {
                            q.push({newX, newY});
                        }
                    }
                }
            }
        }
        
        return maxPathLength;
    }
};

int main() {
    vector<vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };

    Solution solution;
    int longestPath = solution.longestIncreasingPath(matrix);

    cout << "The longest increasing path length is: " << longestPath << endl;

    return 0;
}

Example:

Matrix:
[
 [9, 9, 4],
 [6, 6, 8],
 [2, 1, 1]
]

Step 1: Initialization

• The example matrix is defined.

Step 2: Initialize In-Degrees and Build the Graph

• Initialize inDegree and create a graph.
• Calculate in-degrees and build the graph:

Graph:
(0,0) --> (0,1) --> (0,2)
 |        |
 v        v
(1,0)    (1,1) <-- (1,2)
                    |
                    v
(2,0) --> (2,1)

Step 3: Initialize the Queue

• Create a queue and add nodes with no incoming edges to the queue:

Queue: (0,0), (2,0)

Step 4: Initialize maxPathLength

• Initialize maxPathLength to 0.

Step 5: Topological Sort

• Start the topological sort process:

Iteration 1:

• Dequeue (0,0) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (2,0)
inDegree:

1 0 0
0 0 0
1 0 0

maxPathLength: 1

Iteration 2:

• Dequeue (2,0) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (1,0)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 2

Iteration 3:

• Dequeue (1,0) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (0,1)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 3

Iteration 4:

• Dequeue (0,1) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (1,1)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 4

Iteration 5:

• Dequeue (1,1) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (0,2)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 5

Iteration 6:

• Dequeue (0,2) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (1,2)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 6

Iteration 7:

• Dequeue (1,2) from the queue.
• Update in-degrees of neighbors and enqueue:

Queue: (2,2)
inDegree:

1 0 0
0 0 0
0 0 0

maxPathLength: 7

Iteration 8:

• Dequeue (2,2) from the queue.
• Update in-degrees of neighbors.

Queue is now empty.

Step 6: Return the Result

• The result is maxPathLength, which is 7.

Step 7: Output

• The code prints: "The longest increasing path length is: 7."

So, the longest increasing path in the given matrix is [1, 2, 6, 9], and its length is indeed 7.

Real-World Examples

1. Network Routing: In computer networking, routers need to find the most efficient path for data packets to travel from one point to another in a network. This can be compared to finding the longest increasing path in a weighted graph representing the network.

2. Game Development: In video games, especially puzzle games, players often need to find the longest path to achieve a goal. For example, in a game where you have to connect matching tiles on a grid, finding the longest chain of matching tiles can be a game objective.

3. Stock Market Analysis: Traders and investors might analyze historical stock market data to find the longest increasing (or decreasing) trend in a particular stock's price. Detecting long upward trends can help in making investment decisions.

4. Data Compression: In data compression algorithms, there is a need to find the longest repeating sequence or pattern in a dataset to compress it more efficiently.

5. Genome Sequencing: In bioinformatics, scientists often deal with sequences of genetic data. Finding the longest increasing or decreasing subsequence in a genome sequence can provide valuable insights into the structure and function of genes.