OpenSource Internship opportunity by OpenGenus for programmers. Apply now.
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
 Problem Statement
 Key Takeaways
 Approach 1: BFS
 Approach 2: DepthFirst Search (DFS)
 Approach 3: Dynamic Programming
 Approach 4: Toposort
 RealWorld Examples
Problem Statement
Given a twodimensional 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. DepthFirst 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. BreadthFirst 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:BreadthFirst 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 breadthfirst traversal to find the longest increasing path starting from that cell.We record the maximum flood path length of all nodes.
Intutive Explanation:
 Start from any cell and explore adjacent cells with larger values.
 Use BFS to systematically search all possible paths.
 Record the length of increasing paths while exploring.
 Maintain a maximum path length encountered during the process.
 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:

Create a queue for BFS and initialize a variable
maxLength
to 0. This variable will store the length of the longest increasing path found. 
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. 
Initialize a queue with pairs of coordinates (row, column) of all cells in the matrix.

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.

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

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

Dequeue cell
(0, 0)
with a value of 9. Examine valid neighbors:
(0, 1)
and(1, 0)
.  For
(0, 1)
, the value is the same (9), so no increase in path length.  For
(1, 0)
, the value is 6, so the path length becomes 1 (from9
to6
).
 Examine valid neighbors:

Dequeue cell
(0, 1)
with a value of 9. Examine valid neighbors:
(0, 2)
and(1, 1)
.  For
(0, 2)
, the value is 4, so the path length becomes 1 (from9
to4
).  For
(1, 1)
, the value is the same (9), so no increase in path length.
 Examine valid neighbors:

Dequeue cell
(0, 2)
with a value of 4. Examine the valid neighbor
(1, 2)
.  For
(1, 2)
, the value is 8, so the path length becomes 1 (from4
to8
).
 Examine the valid neighbor

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: DepthFirst Search (DFS)
One way to approach this problem is by using DepthFirst Search (DFS). We start at each cell in the matrix and perform a depthfirst 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:
 Start from any cell and explore adjacent cells with larger values.
 Use DFS to calculate the length of increasing paths.
 Store path lengths using memoization to avoid redundancy.
 Record the maximum path length encountered during the process.
 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:

Initialize a variable
maxPathLength
to 0. This variable will store the length of the longest increasing path found. 
Iterate through each cell in the matrix.

For each cell, perform a depthfirst 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. 
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:

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

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

We maintain a memoization table (
memo
) to avoid redundant calculations. Thememo
table stores the length of the longest increasing path starting from each cell. Initially, all entries in thememo
table are set to 1.
Now, let's perform DFS from the topleft 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:
 Choose a cell as the starting point.
 Use DFS to explore and calculate path lengths.
 Store lengths in a memoization table to avoid redundancy.
 Keep track of the maximum path length encountered.
 Repeat for all cells.
 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:

Initialize a variable
maxPathLength
to 0. This variable will store the length of the longest increasing path found. 
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.

Iterate through each cell in the matrix.

For each cell, perform a depthfirst 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.

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 celldp[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. SetmaxLength
to 0 initially.
Step 2: Dynamic Programming (DP) Using DFS
Now, let's perform dynamic programming using a DepthFirst Search (DFS) approach to find the longest increasing path from each cell in the matrix.
Starting from Cell (0, 0)
with Value 9

We start DFS from cell
(0, 0)
with a value of9
. 
The
dfs
function explores neighboring cells that have greater values and are valid moves (up, down, left, and right). 
It moves right to cell
(0, 1)
with a value of9
. Since the value is the same, it doesn't increase the path length. 
It moves down to cell
(1, 0)
with a value of6
. This is a valid move as6
is less than9
, so it increases the path length by1
. 
From cell
(1, 0)
, it continues the DFS. It moves right to cell(1, 1)
with a value of6
. Again, it increases the path length by1
. 
Now, it explores all directions from
(1, 1)
but finds no valid moves with greater values. 
The DFS from cell
(0, 0)
returns a path length of2
.
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 of2
.  DFS from cell
(0, 2)
returns a path length of1
.  DFS from cell
(1, 0)
returns a path length of2
.  DFS from cell
(1, 1)
returns a path length of1
.  DFS from cell
(1, 2)
returns a path length of1
.  DFS from cell
(2, 0)
returns a path length of2
.  DFS from cell
(2, 1)
returns a path length of1
.  DFS from cell
(2, 2)
returns a path length of1
.
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:
 Treat the matrix as a graph, with each cell as a node.
 Calculate indegrees for each node to create a Directed Acyclic Graph (DAG).
 Start with nodes having zero indegrees.
 Perform topological sort to find the longest path.
 Keep track of the maximum path length encountered.
 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:

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)
ifmatrix[x][y]
is greater thanmatrix[i][j]
. This step creates the DAG. 
Create an array
inDegree
to keep track of the indegrees (the number of incoming edges) for each node. Initialize all indegrees to 0 initially. 
Initialize a queue and add all nodes (cells) with an indegree of 0 to the queue. These are the nodes with no incoming edges.

Initialize a variable
maxPathLength
to 0. This variable will store the length of the longest path found. 
Perform topological sort as follows:
 Dequeue a node from the queue.
 For each of its neighbors, decrease their indegree by 1 because we've processed an edge.
 If the indegree of a neighbor becomes 0, enqueue that neighbor.
 While processing each node, keep track of the maximum path length found.

Continue this process until the queue is empty.

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 thanmatrix[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 indegrees for each node (cell). All indegrees are initially 0.
Step 3: Initialize the Queue
 Enqueue nodes
(0,0)
,(0,1)
, and(2,0)
since they have no incoming edges (indegree 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 indegrees 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 indegrees 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 InDegrees and Build the Graph
 Initialize
inDegree
and create a graph.  Calculate indegrees 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 indegrees 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 indegrees 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 indegrees 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 indegrees 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 indegrees 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 indegrees 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 indegrees 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 indegrees 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.
RealWorld Examples

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.

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.

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.

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.

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.