Last Updated: 19 Nov, 2020

Minimum Falling Path Sum

Moderate

Asked in companies

Solve now

Problem statement

You have been given a square array 'VEC' of integers of size 'N' rows and 'N' columns. Your task is to find the minimum sum of a falling path through the square array. The number of rows and columns in the given array will be the same.

A falling path starts at any element in the first row and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.

Example:

VEC[][]= {{5, 10}, {25, 15}}

alt text

All the rectangles denote the possible falling paths. The rectangle with red filler is the minimum falling path with the minimum falling path sum of 20 (5+15).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test contains an integer ‘N’ denoting the number of rows and columns.

The next ‘N’ lines of each test case contain ‘N’ space-separated integers denoting the elements of the square array.

Output format:

For each test case, print a single integer the minimum sum of a falling path through the square array.

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything; it has already been taken care of. Just return the minimum sum calculated.

Constraints:

1 <= T <= 50
1 <= N <= 100
-10^7 <= VEC[i][j] <=10^7

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of rows and columns in the array, and ‘VEC[i][j]’ denotes the range of elements in the 2 Dimensional array.

Time limit: 1 second

Solve now

Approaches

01 Approach

Since the difference between the previous ‘ROW’ ‘COLUMN’ number and the current ‘ROW’ ’COLUMN’ number should be at most one, the possible next step from point A[‘ROW’ ][‘COLUMN’] will be A[‘ROW’ +1][‘COLUMN’-1], A[‘ROW’+1][‘COLUMN’] and A[‘ROW’+1][‘COLUMN’+1]. So, the idea is to traverse these possible paths and keep storing the minimum result for each ‘COLUMN’. Finally, return the minimum of all the values of each ‘COLUMN’.

Run a loop where ‘‘ROW’’ ranges from ‘N-2’ to 0 and another nested loop where ‘COLUMN’’ ranges from 0 to ‘N-1’.
We maintain a variable ‘MINFALL’ which is initialized to ‘VEC[‘ROW’+1][‘COLUMN’].
If ‘COLUMN’’ is greater than or equal to 0, compare the value of variable ‘MINFALL’ with ‘VEC[‘ROW’+1][‘COLUMN’-1]’ and store the minimum of the two in variable ‘MINFALL’.
If ‘COLUMN’+1’ is less than ‘N’, compare the value of variable ‘MINFALL’ with ‘VEC[‘ROW’+1][‘COLUMN’+1]’ and store the minimum of the two in variable ‘MINFALL’.
Through steps 2, 3 & 4, we will get the minimum path from the end ‘ROW’ to the point ‘VEC[‘ROW’][‘COLUMN’]’ and will add this minimum value to ‘VEC[‘ROW’][‘COLUMN’]’.
We will use these values for finding the minimum falling path for upper ‘ROW’s.
Finally, we will compare and find the minimum values among ‘VEC[0][I]’ where ‘I’ ranges from 0 to ‘N-1’ and return the smallest value.

Solve now