Find longest increasing path in a matrix
The problem of finding the longest increasing path in a matrix involves finding the longest sequence of elements in a matrix such that each element is greater than its adjacent elements and the sequence is maximally long. In other words, we need to find the longest path in the matrix where each element is strictly increasing.
Problem Statement
Given a matrix of size ROW x COL, our task is to find the longest increasing path in the matrix. We need to identify the starting position (r, c) in the matrix and then find the longest increasing path starting from that position.
For example, consider the following matrix:
8 0 1 2 7 8 10 10 11 3 1 4 6 7 21 19 18 5 14 9 10 25 20 17 16 13 12 11
If we choose the starting position as (0, 0), the longest increasing path in this matrix would be:
8 - - - - - - 10 11 - - - - - - 19 - - - - - 25 20 - - - - -
Here, the longest increasing path contains the elements 8, 10, 11, 19, and 25. Notice that we can move only horizontally or vertically (not diagonally) to neighboring cells.
Approach and Algorithm
We can solve this problem using a depth-first search (DFS) algorithm. The basic idea is to start from each cell in the matrix and explore all possible paths, keeping track of the maximum length encountered.
The algorithm follows these steps:
- Define a helper function to find the longest increasing path from a given cell.
- If the cell is out of bounds or has already been visited, return.
- Mark the cell as visited.
- If the current path length is greater than the maximum length encountered so far, update the maximum length and store the current path.
- Recursively explore the neighboring cells in all four directions (up, down, left, right), but only if the neighboring cell's value is greater than the current cell's value.
- Mark the cell as unvisited to allow it to be included in other paths.
- Repeat the above steps for all cells in the matrix.
The algorithm keeps track of the longest path found and stores it in a separate matrix. Finally, it outputs the longest increasing path from the given starting position.
Program Solution
// C program
// Find longest increasing path in a matrix
#include <stdio.h>
#define ROW 4
#define COL 7
//Print grid elements
void printData(int grid[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
printf(" %d\t", grid[i][j]);
}
printf("\n");
}
printf("\n");
}
// Copy visitor element to output collection
void copyResult(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
// Assign element
if (visitor[i][j] == 1)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = visitor[i][j];
}
}
}
}
// Find increasing path
// r and c is Source point
void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int *length, int counter)
{
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
//When not valid position
return;
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return;
}
//Active visiting node
visitor[r][c] = 1;
if ( *length < counter)
{
// When get new increasing path
*length = counter;
copyResult(collection, visitor, output);
}
// Test element in 4 direction
if (r + 1 < ROW && collection[r + 1][c] > collection[r][c])
{
findPath(collection, visitor, output, r + 1, c, length, counter + 1);
}
if (c + 1 < COL && collection[r][c + 1] > collection[r][c])
{
findPath(collection, visitor, output, r, c + 1, length, counter + 1);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
findPath(collection, visitor, output, r - 1, c, length, counter + 1);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
findPath(collection, visitor, output, r, c - 1, length, counter + 1);
}
// Deactivate visited node status
visitor[r][c] = 0;
}
// Handles the request to find longest increasing path
// r and c is Source point
void increasingPath(int collection[ROW][COL], int r, int c)
{
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
// r and c Source point
return;
}
//Create resultant grid
int output[ROW][COL];
int visitor[ROW][COL];
int i = 0;
int j = 0;
int length = 0;
//Set initial values
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
output[i][j] = 0;
visitor[i][j] = 0;
}
}
findPath(collection, visitor, output, r, c, & length, 0);
printf("\n Source point (%d,%d) ", r, c);
if (length != 0)
{
//When result are exist
// Display solution
printf("\n Longest Increasing Path \n");
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
if (output[i][j] == 0)
{
printf(" - \t");
}
else
{
printf(" %d\t", output[i][j]);
}
}
printf("\n");
}
}
else
{
//When no solution possible
printf("\n No Increasing Path \n");
}
}
int main()
{
int collection[ROW][COL] =
{
{8, 0, 1, 2, 7, 8, 10},
{10, 11, 3, 1, 4, 6, 7},
{21, 19,18, 5, 14, 9, 10},
{25, 20,17, 16,13, 12, 11}
};
// Print input problem
printf("\n Input Matrix \n");
printData(collection);
// Test Cases
increasingPath(collection, 0, 0);
increasingPath(collection, 1, 3);
increasingPath(collection, 1, 5);
increasingPath(collection, 0, 2);
increasingPath(collection, 0, 4);
increasingPath(collection, 0, 6);
return 0;
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path/*
Java Program for
Find longest increasing path in a matrix
*/
class Path
{
public int length;
public Path()
{
this.length = -1;
}
//Print grid elements
public void printData(int[][] grid, int row, int col)
{
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
System.out.print(" " + grid[i][j] + "\t");
}
System.out.print("\n");
}
System.out.print("\n");
}
// Copy visitor element to output collection
public void copyResult(int[][] collection, boolean[][] visitor, int[][] output, int row, int col)
{
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
if (visitor[i][j] == true)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = 0;
}
}
}
}
// Find increasing path
// r and c is Source point
public void findPath(int[][] collection, boolean[][] visitor,
int[][] output, int r, int c, int counter, int row,int col)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return;
}
if (visitor[r][c] == true)
{
//When the element has been already been visited
return;
}
//Active visiting node
visitor[r][c] = true;
if (this.length < counter)
{
// When get new increasing path
this.length = counter;
copyResult(collection, visitor, output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection[r + 1][c] > collection[r][c])
{
findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection[r][c + 1] > collection[r][c])
{
findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor[r][c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
public void increasingPath(int[][] collection, int r, int c, int row, int col)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
// r and c Source point
return;
}
//Create resultant grid
int[][] output = new int[row][col];
boolean[][] visitor = new boolean[row][col];
int i = 0;
int j = 0;
this.length = 0;
//Set initial values
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
output[i][j] = 0;
visitor[i][j] =false;
}
}
findPath(collection, visitor, output, r, c, 0, row,col);
System.out.print("\n Source point (" + r + "," + c + ") ");
if (length != 0)
{
//When result are exist
// Display solution
System.out.print("\n Longest Increasing Path \n");
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
if (output[i][j] == 0)
{
System.out.print(" - \t");
}
else
{
System.out.print(" " + output[i][j] + "\t");
}
}
System.out.print("\n");
}
}
else
{
//When no solution possible
System.out.print("\n No Increasing Path \n");
}
}
public static void main(String[] args)
{
Path task = new Path();
int [][]collection =
{
{8, 0, 1, 2, 7, 8, 10},
{10, 11, 3, 1, 4, 6, 7},
{21, 19,18, 5, 14, 9, 10},
{25, 20,17, 16,13, 12, 11}
};
// Get size
int row = collection.length;
int col = collection[0].length;
// Print input problem
System.out.print("\n Input Matrix \n");
task.printData(collection,row,col);
// Test Cases
task.increasingPath(collection, 0, 0,row,col);
task.increasingPath(collection, 1, 3,row,col);
task.increasingPath(collection, 1, 5,row,col);
task.increasingPath(collection, 0, 2,row,col);
task.increasingPath(collection, 0, 4,row,col);
task.increasingPath(collection, 0, 6,row,col);
}
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path// Include header file
#include <iostream>
#define ROW 4
#define COL 7
using namespace std;
/*
C++ Program for
Find longest increasing path in a matrix
*/
class Path
{
public: int length;
Path()
{
this->length = -1;
}
//Print grid elements
void printData(int grid[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
cout << " " << grid[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
}
// Copy visitor element to output collection
void copyResult(int collection[ROW][COL], bool visitor[ROW][COL], int output[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
// Assign element
if (visitor[i][j] == true)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = 0;
}
}
}
}
// Find increasing path
// r and c is Source point
void findPath(int collection[ROW][COL], bool visitor[ROW][COL], int output[ROW][COL],
int r, int c, int counter)
{
//When not valid position
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
return;
}
//When the element has been already been visited
if (visitor[r][c] == true)
{
return;
}
//Active visiting node
visitor[r][c] = true;
if (this->length < counter)
{
// When get new increasing path
this->length = counter;
this->copyResult(collection, visitor, output);
}
// Test element in 4 direction
if (r + 1 < ROW && collection[r + 1][c] > collection[r][c])
{
this->findPath(collection, visitor, output, r + 1, c, counter + 1);
}
if (c + 1 < COL && collection[r][c + 1] > collection[r][c])
{
this->findPath(collection, visitor, output, r, c + 1, counter + 1);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
this->findPath(collection, visitor, output, r - 1, c, counter + 1);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
this->findPath(collection, visitor, output, r, c - 1, counter + 1);
}
// Deactivate visited node status
visitor[r][c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
void increasingPath(int collection[ROW][COL], int r, int c)
{
// r and c Source point
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
return;
}
//Create resultant grid
int output[ROW][COL];
bool visitor[ROW][COL];
int i = 0;
int j = 0;
this->length = 0;
//Set initial values
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
output[i][j] = 0;
visitor[i][j] = false;
}
}
this->findPath(collection, visitor, output, r, c, 0);
cout << "\n Source point (" << r << "," << c << ") ";
if (this->length != 0)
{
//When result are exist
// Display solution
cout << "\n Longest Increasing Path \n";
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
if (output[i][j] == 0)
{
cout << " - \t";
}
else
{
cout << " " << output[i][j] << "\t";
}
}
cout << "\n";
}
}
else
{
//When no solution possible
cout << "\n No Increasing Path \n";
}
}
};
int main()
{
Path task = Path();
int collection[ROW][COL] =
{
{8, 0, 1, 2, 7, 8, 10},
{10, 11, 3, 1, 4, 6, 7},
{21, 19,18, 5, 14, 9, 10},
{25, 20,17, 16,13, 12, 11}
};
// Print input problem
cout << "\n Input Matrix \n";
task.printData(collection);
// Test Cases
task.increasingPath(collection, 0, 0);
task.increasingPath(collection, 1, 3);
task.increasingPath(collection, 1, 5);
task.increasingPath(collection, 0, 2);
task.increasingPath(collection, 0, 4);
task.increasingPath(collection, 0, 6);
return 0;
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path// Include namespace system
using System;
/*
C# Program for
Find longest increasing path in a matrix
*/
public class Path
{
public int length;
public Path()
{
this.length = -1;
}
//Print grid elements
public void printData(int[,] grid, int row, int col)
{
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
Console.Write(" " + grid[i,j] + "\t");
}
Console.Write("\n");
}
Console.Write("\n");
}
// Copy visitor element to output collection
public void copyResult(int[,] collection, Boolean[,] visitor, int[,] output, int row, int col)
{
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
if (visitor[i,j] == true)
{
output[i,j] = collection[i,j];
}
else
{
output[i,j] = 0;
}
}
}
}
// Find increasing path
// r and c is Source point
public void findPath(int[,] collection, Boolean[,] visitor, int[,] output, int r, int c, int counter, int row, int col)
{
//When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//When the element has been already been visited
if (visitor[r,c] == true)
{
return;
}
//Active visiting node
visitor[r,c] = true;
if (this.length < counter)
{
// When get new increasing path
this.length = counter;
copyResult(collection, visitor, output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection[r + 1,c] > collection[r,c])
{
findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection[r,c + 1] > collection[r,c])
{
findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection[r - 1,c] > collection[r,c])
{
findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection[r,c - 1] > collection[r,c])
{
findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor[r,c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
public void increasingPath(int[,] collection, int r, int c, int row, int col)
{
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//Create resultant grid
int[,] output = new int[row,col];
Boolean[,] visitor = new Boolean[row,col];
int i = 0;
int j = 0;
this.length = 0;
//Set initial values
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
output[i,j] = 0;
visitor[i,j] = false;
}
}
findPath(collection, visitor, output, r, c, 0, row, col);
Console.Write("\n Source point (" + r + "," + c + ") ");
if (length != 0)
{
//When result are exist
// Display solution
Console.Write("\n Longest Increasing Path \n");
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
if (output[i,j] == 0)
{
Console.Write(" - \t");
}
else
{
Console.Write(" " + output[i,j] + "\t");
}
}
Console.Write("\n");
}
}
else
{
//When no solution possible
Console.Write("\n No Increasing Path \n");
}
}
public static void Main(String[] args)
{
Path task = new Path();
int[,] collection = {
{
8 , 0 , 1 , 2 , 7 , 8 , 10
} , {
10 , 11 , 3 , 1 , 4 , 6 , 7
} , {
21 , 19 , 18 , 5 , 14 , 9 , 10
} , {
25 , 20 , 17 , 16 , 13 , 12 , 11
}
};
// Get size
int row = collection.GetLength(0);
int col = collection.GetLength(1);
// Print input problem
Console.Write("\n Input Matrix \n");
task.printData(collection, row, col);
// Test Cases
task.increasingPath(collection, 0, 0, row, col);
task.increasingPath(collection, 1, 3, row, col);
task.increasingPath(collection, 1, 5, row, col);
task.increasingPath(collection, 0, 2, row, col);
task.increasingPath(collection, 0, 4, row, col);
task.increasingPath(collection, 0, 6, row, col);
}
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path<?php
/*
Php Program for
Find longest increasing path in a matrix
*/
class Path
{
public $length;
function __construct()
{
$this->length = -1;
}
//Print grid elements
public function printData( & $grid, $row, $col)
{
$i = 0;
$j = 0;
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
echo " ". $grid[$i][$j] ."\t";
}
echo "\n";
}
echo "\n";
}
// Copy visitor element to output collection
public function copyResult( & $collection, & $visitor, & $output, $row, $col)
{
$i = 0;
$j = 0;
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
// Assign element
if ($visitor[$i][$j] == true)
{
$output[$i][$j] = $collection[$i][$j];
}
else
{
$output[$i][$j] = 0;
}
}
}
}
// Find increasing path
// r and c is Source point
public function findPath( & $collection, & $visitor, & $output, $r, $c, $counter, $row, $col)
{
//When not valid position
if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
{
return;
}
//When the element has been already been visited
if ($visitor[$r][$c] == true)
{
return;
}
//Active visiting node
$visitor[$r][$c] = true;
if ($this->length < $counter)
{
// When get new increasing path
$this->length = $counter;
$this->copyResult($collection, $visitor, $output, $row, $col);
}
// Test element in 4 direction
if ($r + 1 < $row && $collection[$r + 1][$c] > $collection[$r][$c])
{
$this->findPath($collection, $visitor, $output, $r + 1, $c, $counter + 1, $row, $col);
}
if ($c + 1 < $col && $collection[$r][$c + 1] > $collection[$r][$c])
{
$this->findPath($collection, $visitor, $output, $r, $c + 1, $counter + 1, $row, $col);
}
if ($r - 1 >= 0 && $collection[$r - 1][$c] > $collection[$r][$c])
{
$this->findPath($collection, $visitor, $output, $r - 1, $c, $counter + 1, $row, $col);
}
if ($c - 1 >= 0 && $collection[$r][$c - 1] > $collection[$r][$c])
{
$this->findPath($collection, $visitor, $output, $r, $c - 1, $counter + 1, $row, $col);
}
// Deactivate visited node status
$visitor[$r][$c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
public function increasingPath( & $collection, $r, $c, $row, $col)
{
// r and c Source point
if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
{
return;
}
$this->length = 0;
//Create resultant grid
$output = array_fill(0, $row, array_fill(0, $col, 0));
$visitor = array_fill(0, $row, array_fill(0, $col, false));
$i = 0;
$j = 0;
$this->findPath($collection, $visitor, $output, $r, $c, 0, $row, $col);
echo "\n Source point (". $r .",". $c .") ";
if ($this->length != 0)
{
//When result are exist
// Display solution
echo "\n Longest Increasing Path \n";
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
if ($output[$i][$j] == 0)
{
echo " - \t";
}
else
{
echo " ". $output[$i][$j] ."\t";
}
}
echo "\n";
}
}
else
{
//When no solution possible
echo "\n No Increasing Path \n";
}
}
}
function main()
{
$task = new Path();
$collection = array(
array(8, 0, 1, 2, 7, 8, 10),
array(10, 11, 3, 1, 4, 6, 7),
array(21, 19, 18, 5, 14, 9, 10),
array(25, 20, 17, 16, 13, 12, 11));
// Get size
$row = count($collection);
$col = count($collection[0]);
// Print input problem
echo "\n Input Matrix \n";
$task->printData($collection, $row, $col);
// Test Cases
$task->increasingPath($collection, 0, 0, $row, $col);
$task->increasingPath($collection, 1, 3, $row, $col);
$task->increasingPath($collection, 1, 5, $row, $col);
$task->increasingPath($collection, 0, 2, $row, $col);
$task->increasingPath($collection, 0, 4, $row, $col);
$task->increasingPath($collection, 0, 6, $row, $col);
}
main();Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path/*
Node Js Program for
Find longest increasing path in a matrix
*/
class Path
{
constructor()
{
this.length = -1;
}
//Print grid elements
printData(grid, row, col)
{
var i = 0;
var j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
process.stdout.write(" " + grid[i][j] + "\t");
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Copy visitor element to output collection
copyResult(collection, visitor, output, row, col)
{
var i = 0;
var j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
if (visitor[i][j] == true)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = 0;
}
}
}
}
// Find increasing path
// r and c is Source point
findPath(collection, visitor, output, r, c, counter, row, col)
{
//When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//When the element has been already been visited
if (visitor[r][c] == true)
{
return;
}
//Active visiting node
visitor[r][c] = true;
if (this.length < counter)
{
// When get new increasing path
this.length = counter;
this.copyResult(collection, visitor, output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection[r + 1][c] > collection[r][c])
{
this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection[r][c + 1] > collection[r][c])
{
this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor[r][c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
increasingPath(collection, r, c, row, col)
{
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
this.length = 0;
//Create resultant grid
var output = Array(row).fill(0).map(() => new Array(col).fill(0));
var visitor = Array(row).fill(false).map(() => new Array(col).fill(false));
var i = 0;
var j = 0;
this.findPath(collection, visitor, output, r, c, 0, row, col);
process.stdout.write("\n Source point (" + r + "," + c + ") ");
if (this.length != 0)
{
//When result are exist
// Display solution
process.stdout.write("\n Longest Increasing Path \n");
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
if (output[i][j] == 0)
{
process.stdout.write(" - \t");
}
else
{
process.stdout.write(" " + output[i][j] + "\t");
}
}
process.stdout.write("\n");
}
}
else
{
//When no solution possible
process.stdout.write("\n No Increasing Path \n");
}
}
}
function main()
{
var task = new Path();
var collection = [
[8, 0, 1, 2, 7, 8, 10] ,
[10, 11, 3, 1, 4, 6, 7] ,
[21, 19, 18, 5, 14, 9, 10] ,
[25, 20, 17, 16, 13, 12, 11]
];
// Get size
var row = collection.length;
var col = collection[0].length;
// Print input problem
process.stdout.write("\n Input Matrix \n");
task.printData(collection, row, col);
// Test Cases
task.increasingPath(collection, 0, 0, row, col);
task.increasingPath(collection, 1, 3, row, col);
task.increasingPath(collection, 1, 5, row, col);
task.increasingPath(collection, 0, 2, row, col);
task.increasingPath(collection, 0, 4, row, col);
task.increasingPath(collection, 0, 6, row, col);
}
main();Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path# Python 3 Program for
# Find longest increasing path in a matrix
class Path :
def __init__(self) :
self.length = -1
# Print grid elements
def printData(self, grid, row, col) :
i = 0
j = 0
while (i < row) :
j = 0
while (j < col) :
print("", grid[i][j] , end = "\t")
j += 1
print(end = "\n")
i += 1
print(end = "\n")
# Copy visitor element to output collection
def copyResult(self, collection, visitor, output, row, col) :
i = 0
j = 0
while (i < row) :
j = 0
while (j < col) :
# Assign element
if (visitor[i][j] == True) :
output[i][j] = collection[i][j]
else :
output[i][j] = 0
j += 1
i += 1
# Find increasing path
# r and c is Source point
def findPath(self, collection, visitor, output, r, c, counter, row, col) :
# When not valid position
if (r < 0 or r >= row or c < 0 or c >= col) :
return
# When the element has been already been visited
if (visitor[r][c] == True) :
return
# Active visiting node
visitor[r][c] = True
if (self.length < counter) :
# When get new increasing path
self.length = counter
self.copyResult(collection, visitor, output, row, col)
# Test element in 4 direction
if (r + 1 < row and collection[r + 1][c] > collection[r][c]) :
self.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col)
if (c + 1 < col and collection[r][c + 1] > collection[r][c]) :
self.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col)
if (r - 1 >= 0 and collection[r - 1][c] > collection[r][c]) :
self.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col)
if (c - 1 >= 0 and collection[r][c - 1] > collection[r][c]) :
self.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col)
# Deactivate visited node status
visitor[r][c] = False
# Handles the request to find longest increasing path
# r and c is Source point
def increasingPath(self, collection, r, c, row, col) :
# r and c Source point
if (r < 0 or r >= row or c < 0 or c >= col) :
return
self.length = 0
# Create resultant grid
output = [[0] * (col) for _ in range(row) ]
visitor = [[False] * (col) for _ in range(row) ]
self.findPath(collection, visitor, output, r, c, 0, row, col)
print("\n Source point (", r ,",", c ,") ", end = "")
if (self.length != 0) :
# When result are exist
i = 0
j = 0
# Display solution
print("\n Longest Increasing Path ")
while (i < row) :
j = 0
while (j < col) :
if (output[i][j] == 0) :
print(end = "-\t")
else :
print(output[i][j], end = "\t")
j += 1
print(end = "\n")
i += 1
else :
# When no solution possible
print("\n No Increasing Path ")
def main() :
task = Path()
collection = [
[8, 0, 1, 2, 7, 8, 10] ,
[10, 11, 3, 1, 4, 6, 7] ,
[21, 19, 18, 5, 14, 9, 10] ,
[25, 20, 17, 16, 13, 12, 11]
]
# Get size
row = len(collection)
col = len(collection[0])
# Print input problem
print("\n Input Matrix ")
task.printData(collection, row, col)
# Test Cases
task.increasingPath(collection, 0, 0, row, col)
task.increasingPath(collection, 1, 3, row, col)
task.increasingPath(collection, 1, 5, row, col)
task.increasingPath(collection, 0, 2, row, col)
task.increasingPath(collection, 0, 4, row, col)
task.increasingPath(collection, 0, 6, row, col)
if __name__ == "__main__": main()Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point ( 0 , 0 )
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point ( 1 , 3 )
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point ( 1 , 5 )
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point ( 0 , 2 )
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point ( 0 , 4 )
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point ( 0 , 6 )
No Increasing Path# Ruby Program for
# Find longest increasing path in a matrix
class Path
# Define the accessor and reader of class Path
attr_reader :length
attr_accessor :length
def initialize()
self.length = -1
end
# Print grid elements
def printData(grid, row, col)
i = 0
j = 0
while (i < row)
j = 0
while (j < col)
print(" ", grid[i][j] ,"\t")
j += 1
end
print("\n")
i += 1
end
print("\n")
end
# Copy visitor element to output collection
def copyResult(collection, visitor, output, row, col)
i = 0
j = 0
while (i < row)
j = 0
while (j < col)
# Assign element
if (visitor[i][j] == true)
output[i][j] = collection[i][j]
else
output[i][j] = 0
end
j += 1
end
i += 1
end
end
# Find increasing path
# r and c is Source point
def findPath(collection, visitor, output, r, c, counter, row, col)
# When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
return
end
# When the element has been already been visited
if (visitor[r][c] == true)
return
end
# Active visiting node
visitor[r][c] = true
if (self.length < counter)
# When get new increasing path
self.length = counter
self.copyResult(collection, visitor, output, row, col)
end
# Test element in 4 direction
if (r + 1 < row && collection[r + 1][c] > collection[r][c])
self.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col)
end
if (c + 1 < col && collection[r][c + 1] > collection[r][c])
self.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col)
end
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
self.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col)
end
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
self.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col)
end
# Deactivate visited node status
visitor[r][c] = false
end
# Handles the request to find longest increasing path
# r and c is Source point
def increasingPath(collection, r, c, row, col)
# r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
return
end
self.length = 0
# Create resultant grid
output = Array.new(row) {Array.new(col) {0}}
visitor = Array.new(row) {Array.new(col) {false}}
self.findPath(collection, visitor, output, r, c, 0, row, col)
print("\n Source point (", r ,",", c ,") ")
if (self.length != 0)
# When result are exist
i = 0
j = 0
# Display solution
print("\n Longest Increasing Path \n")
while (i < row)
j = 0
while (j < col)
if (output[i][j] == 0)
print(" - \t")
else
print(" ", output[i][j] ,"\t")
end
j += 1
end
print("\n")
i += 1
end
else
# When no solution possible
print("\n No Increasing Path \n")
end
end
end
def main()
task = Path.new()
collection = [
[8, 0, 1, 2, 7, 8, 10] , [10, 11, 3, 1, 4, 6, 7] , [21, 19, 18, 5, 14, 9, 10] , [25, 20, 17, 16, 13, 12, 11]
]
# Get size
row = collection.length
col = collection[0].length
# Print input problem
print("\n Input Matrix \n")
task.printData(collection, row, col)
# Test Cases
task.increasingPath(collection, 0, 0, row, col)
task.increasingPath(collection, 1, 3, row, col)
task.increasingPath(collection, 1, 5, row, col)
task.increasingPath(collection, 0, 2, row, col)
task.increasingPath(collection, 0, 4, row, col)
task.increasingPath(collection, 0, 6, row, col)
end
main()Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path
/*
Scala Program for
Find longest increasing path in a matrix
*/
class Path(var length: Int)
{
def this()
{
this(-1);
}
//Print grid elements
def printData(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + grid(i)(j) + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Copy visitor element to output collection
def copyResult(collection: Array[Array[Int]], visitor: Array[Array[Boolean]], output: Array[Array[Int]], row: Int, col: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
if (visitor(i)(j) == true)
{
output(i)(j) = collection(i)(j);
}
else
{
output(i)(j) = 0;
}
j += 1;
}
i += 1;
}
}
// Find increasing path
// r and c is Source point
def findPath(collection: Array[Array[Int]], visitor: Array[Array[Boolean]], output: Array[Array[Int]], r: Int, c: Int, counter: Int, row: Int, col: Int): Unit = {
//When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//When the element has been already been visited
if (visitor(r)(c) == true)
{
return;
}
//Active visiting node
visitor(r)(c) = true;
if (this.length < counter)
{
// When get new increasing path
this.length = counter;
this.copyResult(collection, visitor, output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection(r + 1)(c) > collection(r)(c))
{
this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection(r)(c + 1) > collection(r)(c))
{
this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection(r - 1)(c) > collection(r)(c))
{
this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection(r)(c - 1) > collection(r)(c))
{
this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor(r)(c) = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
def increasingPath(collection: Array[Array[Int]], r: Int, c: Int, row: Int, col: Int): Unit = {
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
this.length = 0;
//Create resultant grid
var output: Array[Array[Int]] = Array.fill[Int](row, col)(0);
var visitor: Array[Array[Boolean]] = Array.fill[Boolean](row, col)(false);
this.findPath(collection, visitor, output, r, c, 0, row, col);
print("\n Source point (" + r + "," + c + ") ");
if (this.length != 0)
{
//When result are exist
var i: Int = 0;
var j: Int = 0;
// Display solution
print("\n Longest Increasing Path \n");
while (i < row)
{
j = 0;
while (j < col)
{
if (output(i)(j) == 0)
{
print(" - \t");
}
else
{
print(" " + output(i)(j) + "\t");
}
j += 1;
}
print("\n");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Increasing Path \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Path = new Path();
var collection: Array[Array[Int]] = Array(
Array(8, 0, 1, 2, 7, 8, 10),
Array(10, 11, 3, 1, 4, 6, 7),
Array(21, 19, 18, 5, 14, 9, 10),
Array(25, 20, 17, 16, 13, 12, 11)
);
// Get size
var row: Int = collection.length;
var col: Int = collection(0).length;
// Print input problem
print("\n Input Matrix \n");
task.printData(collection, row, col);
// Test Cases
task.increasingPath(collection, 0, 0, row, col);
task.increasingPath(collection, 1, 3, row, col);
task.increasingPath(collection, 1, 5, row, col);
task.increasingPath(collection, 0, 2, row, col);
task.increasingPath(collection, 0, 4, row, col);
task.increasingPath(collection, 0, 6, row, col);
}
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing Path/*
Swift 4 Program for
Find longest increasing path in a matrix
*/
class Path
{
var length: Int;
init()
{
self.length = -1;
}
//Print grid elements
func printData(_ grid: [[Int]], _ row: Int, _ col: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print("", grid[i][j] , terminator: "\t");
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
// Copy visitor element to output collection
func copyResult(_ collection: [[Int]], _ visitor: [[Bool]], _ output: inout[[Int]], _ row: Int, _ col: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
if (visitor[i][j] == true)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = 0;
}
j += 1;
}
i += 1;
}
}
// Find increasing path
// r and c is Source point
func findPath(_ collection: [[Int]], _ visitor: inout[[Bool]], _ output: inout[[Int]],
_ r: Int, _ c: Int, _ counter: Int, _ row: Int, _ col: Int)
{
//When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//When the element has been already been visited
if (visitor[r][c] == true)
{
return;
}
//Active visiting node
visitor[r][c] = true;
if (self.length < counter)
{
// When get new increasing path
self.length = counter;
self.copyResult(collection, visitor, &output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection[r + 1][c] > collection[r][c])
{
self.findPath(collection, &visitor, &output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection[r][c + 1] > collection[r][c])
{
self.findPath(collection, &visitor, &output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
self.findPath(collection, &visitor, &output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
self.findPath(collection, &visitor, &output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor[r][c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
func increasingPath(_ collection: [[Int]], _ r: Int, _ c: Int, _ row: Int, _ col: Int)
{
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
self.length = 0;
//Create resultant grid
var output: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
var visitor: [[Bool]] = Array(repeating: Array(repeating: false, count: col), count: row);
self.findPath(collection, &visitor, &output, r, c, 0, row, col);
print("\n Source point (", r ,",", c ,") ", terminator: "");
if (self.length != 0)
{
//When result are exist
var i: Int = 0;
var j: Int = 0;
// Display solution
print("\n Longest Increasing Path ");
while (i < row)
{
j = 0;
while (j < col)
{
if (output[i][j] == 0)
{
print(terminator: "-\t");
}
else
{
print("", output[i][j],terminator: "\t");
}
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Increasing Path ");
}
}
}
func main()
{
let task: Path = Path();
let collection: [[Int]] = [
[8, 0, 1, 2, 7, 8, 10] ,
[10, 11, 3, 1, 4, 6, 7] ,
[21, 19, 18, 5, 14, 9, 10] ,
[25, 20, 17, 16, 13, 12, 11]
];
// Get size
let row: Int = collection.count;
let col: Int = collection[0].count;
// Print input problem
print("\n Input Matrix ");
task.printData(collection, row, col);
// Test Cases
task.increasingPath(collection, 0, 0, row, col);
task.increasingPath(collection, 1, 3, row, col);
task.increasingPath(collection, 1, 5, row, col);
task.increasingPath(collection, 0, 2, row, col);
task.increasingPath(collection, 0, 4, row, col);
task.increasingPath(collection, 0, 6, row, col);
}
main();Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point ( 0 , 0 )
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point ( 1 , 3 )
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point ( 1 , 5 )
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point ( 0 , 2 )
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point ( 0 , 4 )
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point ( 0 , 6 )
No Increasing Path/*
Kotlin Program for
Find longest increasing path in a matrix
*/
class Path
{
var length: Int;
constructor()
{
this.length = -1;
}
//Print grid elements
fun printData(grid: Array<Array<Int>> , row: Int, col: Int): Unit
{
var i: Int = 0;
var j: Int ;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + grid[i][j] + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Copy visitor element to output collection
fun copyResult(collection: Array <Array<Int>> , visitor: Array <Array<Boolean>> ,
output: Array <Array<Int>> , row: Int, col: Int): Unit
{
var i: Int = 0;
var j: Int ;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
if (visitor[i][j] == true)
{
output[i][j] = collection[i][j];
}
else
{
output[i][j] = 0;
}
j += 1;
}
i += 1;
}
}
// Find increasing path
// r and c is Source point
fun findPath(collection: Array <Array<Int>> , visitor: Array<Array<Boolean>> ,
output: Array <Array<Int>> , r: Int, c: Int, counter: Int, row: Int, col: Int): Unit
{
//When not valid position
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
//When the element has been already been visited
if (visitor[r][c] == true)
{
return;
}
//Active visiting node
visitor[r][c] = true;
if (this.length < counter)
{
// When get new increasing path
this.length = counter;
this.copyResult(collection, visitor, output, row, col);
}
// Test element in 4 direction
if (r + 1 < row && collection[r + 1][c] > collection[r][c])
{
this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
}
if (c + 1 < col && collection[r][c + 1] > collection[r][c])
{
this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
}
if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
{
this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
}
if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
{
this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
}
// Deactivate visited node status
visitor[r][c] = false;
}
// Handles the request to find longest increasing path
// r and c is Source point
fun increasingPath(collection: Array <Array<Int>> , r: Int, c: Int, row: Int, col: Int): Unit
{
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
this.length = 0;
//Create resultant grid
var output: Array < Array < Int >> = Array(row)
{
Array(col)
{
0
}
};
var visitor: Array < Array < Boolean >> = Array(row)
{
Array(col)
{
false
}
};
this.findPath(collection, visitor, output, r, c, 0, row, col);
print("\n Source point (" + r + "," + c + ") ");
if (this.length != 0)
{
//When result are exist
var i: Int = 0;
var j: Int ;
// Display solution
print("\n Longest Increasing Path \n");
while (i < row)
{
j = 0;
while (j < col)
{
if (output[i][j] == 0)
{
print(" - \t");
}
else
{
print(" " + output[i][j] + "\t");
}
j += 1;
}
print("\n");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Increasing Path \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Path = Path();
var collection: Array<Array<Int>> = arrayOf(
arrayOf(8, 0, 1, 2, 7, 8, 10),
arrayOf(10, 11, 3, 1, 4, 6, 7),
arrayOf(21, 19, 18, 5, 14, 9, 10),
arrayOf(25, 20, 17, 16, 13, 12, 11)
);
// Get size
var row: Int = collection.count();
var col: Int = collection[0].count();
// Print input problem
print("\n Input Matrix \n");
task.printData(collection, row, col);
// Test Cases
task.increasingPath(collection, 0, 0, row, col);
task.increasingPath(collection, 1, 3, row, col);
task.increasingPath(collection, 1, 5, row, col);
task.increasingPath(collection, 0, 2, row, col);
task.increasingPath(collection, 0, 4, row, col);
task.increasingPath(collection, 0, 6, row, col);
}Output
Input Matrix
8 0 1 2 7 8 10
10 11 3 1 4 6 7
21 19 18 5 14 9 10
25 20 17 16 13 12 11
Source point (0,0)
Longest Increasing Path
8 - - - - - -
10 11 - - - - -
- 19 - - - - -
25 20 - - - - -
Source point (1,3)
Longest Increasing Path
- - - - - - -
- - - 1 4 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (1,5)
Longest Increasing Path
- - - - - - -
- - - - - 6 -
- 19 18 - - 9 10
25 20 17 16 13 12 11
Source point (0,2)
Longest Increasing Path
- - 1 - - - -
- - 3 - - - -
- 19 18 - - - -
25 20 - - - - -
Source point (0,4)
Longest Increasing Path
- - - - 7 8 10
- - - - - - -
- - - - - - -
- - - - - - -
Source point (0,6)
No Increasing PathImplementation and Output
Let's implement the above algorithm in C and see the output for the given matrix:
// C program code (Refer to the original code provided)
The output for the given matrix and starting positions is:
Source point (0, 0) Longest Increasing Path 8 - - - - - - 10 11 - - - - - - 19 - - - - - 25 20 - - - - - Source point (1, 3) Longest Increasing Path - - - - - - - - - - 1 4 6 - - 19 18 - - 9 10 25 20 17 16 13 12 11 Source point (1, 5) Longest Increasing Path - - - - - - - - - - - - 6 - - 19 18 - - 9 10 25 20 17 16 13 12 11 Source point (0, 2) Longest Increasing Path - - 1 - - - - - - 3 - - - - - 19 18 - - - - 25 20 - - - - - Source point (0, 4) Longest Increasing Path - - - - 7 8 10 - - - - - - - - - - - - - - - - - - - - - Source point (0, 6) No Increasing Path
The output shows the longest increasing paths for various starting positions in the given matrix. For the starting positions that have a valid increasing path, the elements of the path are displayed. For the starting position (0, 6), there is no increasing path.
Time Complexity
The time complexity of the algorithm is determined by the number of cells in the matrix, which is ROW x COL. Since we perform a depth-first search from each cell, the worst-case time complexity is O(ROW x COL x (ROW x COL)).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment