Question

A Hackerrank Challenge:

Given an NxN matrix, slice it and find the minimum slice weight.

A slice consists of all the elements that are below, below right, or below left of the element above it. The Min Slice Weight is the minimum sum of all elements in the slice.

Example: given input

1 2 3

4 5 6

7 8 9

The slices would be 1 4 7 1; 1 4 8; 1 5 7; 1 5 8; 1 5 9; 2 4 7; 2 4 8; 2 5 8; 2 5 9;2 6 8; 2 6 9 ....etc.

KEEP IN MIND THAT THE MATRIX IS NOT 3 X 3, BUT N X N.

The minimum slice would be 1 4 7 in this case because 1+4+7 is the minimum of all the sums;

Write a function public int FindMinSlice (List<List> Matrix) that returns the min slice weight.

Answer 1

public int FindMinSlice (List> Matrix)
{
int rows=Matrix.size(); // number of rows in the matrix
if(rows==0)
return 0;
int columns=Matrix.get(0).size(); // number of columns in the matrix
if(columns==0)
return 0;
int sliceSum[]=new int[columns]; // maintains the current minimum slice sum starting form column j, we build this array bottom up
for(int i=0;i sliceSum[i]=Matrix.get(rows-1).get(i); // fill the sliceSum array with the values in the last row
for(int i=rows-2;i>=0;i--) // iterate through the rows upward starting from the second-last row
{
for(int j=columns-1;j>=0;j--) { // iterate through the columns leftward starting from the last column
// sliceSum[j] = Matrix[i][j]+ min(sliceSum[j-1], sliceSum[j], sliceSum[j+1]) if the required indices exists in sliceSum
if(j==columns-1)
sliceSum[j]=Math.min(sliceSum[j-1],sliceSum[j])+Matrix.get(i).get(j);
else if(j==0)
sliceSum[j]=Math.min(sliceSum[j],sliceSum[j+1])+Matrix.get(i).get(j);
else
sliceSum[j]=Math.min(sliceSum[j-1],Math.min(sliceSum[j],sliceSum[j+1]))+Matrix.get(i).get(j);
}
}
int minSliceSum=sliceSum[0]; // current minimum sliceSum
for(int i=1;i minSliceSum=Math.min(minSliceSum,sliceSum[i]); // update the minimum sliceSum if required
return minSliceSum;
}