|
|
|
Interview Question: Minimum path sum in a matrix
by
Kamal Rawat
on
Dec 15, 2011
Given a Matrix of positive integers, you have to travel from one cell to another such that the sum of elements in path is minimum.
|
|
|
|
Comments: 0 Views: 1194
|
|
|
|
MCN Professionals | Interview Question of the day
To receive one interview question in your mailbox daily, please subscribe to "A Question A Day" at MCN Professionals home page.-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Given a Matrix of positive integers and 2 cells A & B. You have to reach from A to B, You can travel in forward, downward and diagonally. For example: If the given Matrix is as below:
1 2 3
4 8 2
1 5 3
and you want to move from (0,0) to (2,2). Then you have to travel the following elements:
1 2 3
4 8 2
1 5 3
Path: 1->2->2->3
Solution:
It is easy to visualize it recursively. If we start from the destination point and move backward. Then
Minimum Path to reach a point = Current Cell value + Minimum of paths from (top, left & top-left diagonal)
/** Print the min sum path in a matrix. if the matrix is
* { {1, 2, 3},
* {4, 8, 2},
* {1, 5, 3} }
*then path from (0,0) to (2,2) will be via 1->2->2->3
*
* (m,n) is the last cell where we want to reach.
*/
int printMinPath(int arr[R][C], int m, int n)
{
if(m<0 || n<0)
return POSOTIVE_INFINITY;
if(n==0 && m==0)
return arr[m][n]; // since array has only positive numbers
else
{
int a = printMinPath(arr, m-1, n);
int b = printMinPath(arr, m, n-1);
int c = printMinPath(arr, m-1, n-1);
return getMinimum(a, b, c) + arr[m][n];
}
}
Function getMinimum(int, int, int); is a simple function which accepts 3 int values and return the minimum of them.
-----------------------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...
|
|
|
|
|