Coding

Minimum Falling Path Sum

Asked at

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a 2d array called **matrix **consisting of **integer **values. Return the **minimum **path sum that can be obtained by **starting **at **any **cell in the **first **row and **ending **at **any **cell in the **last **row.

Movement is allowed only to the bottom, bottom-right, or **bottom-left **cell of the current cell.

Input: matrix = [[1, 2, 10, 4], [100, 3, 2, 1], [1, 1, 20, 2], [1, 2, 2, 1]] Output: 6 Explanation: One optimal route can be:- Start at 1st cell of 1st row -> bottom-right -> bottom -> bottom-left.

Input: matrix = [[1, 4, 3, 1], [2, 3, -1, -1], [1, 1, -1, 8]] Output: -1 Explanation: One optimal route can be:- Start at 4th cell of 1st row -> bottom-left -> bottom.

Input: matrix = [[4, 3, 4], [4, 5, 1], [4, 6, 2], [4, 1, 4]]

m == number of rows in matrix
n == number of columns in matrix
1 <= n, m <= 100
-1000 <= matrix[i][j] <= 1000
The answer will not exceed 109

cpp

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {

    }
};

java

class Solution {
    public int minFallingPathSum(int[][] matrix) {

    }
}

python

class Solution:
    def minFallingPathSum(self, matrix):

javascript

class Solution {
    minFallingPathSum(matrix) {

    }
}

csharp

public class Solution {
    public int MinFallingPathSum(int[][] matrix) {
        
    }
}

func minFallingPathSum(matrix [][]int) int {

}

Stuck? Show a way to structure it+

01Let dp[c] represent the best sum ending at column c in the prior row.
02For each cell, take its value plus the minimum of up-left, up, and up-right.
03Treat unavailable diagonal parents as infinity.
04Return the minimum value in the final row.

Reference answer

A falling path reaches (r,c) from (r-1,c-1), (r-1,c), or (r-1,c+1). Initialize the first DP row from the grid. For each subsequent row, compute a fresh array where next[c] = grid[r][c] + min(prev[c-1], prev[c], prev[c+1]), ignoring out-of-range parents. The minimum in the final row is the answer because a path may end in any column. This is O(R*C) time and O(C) extra space. Do not update the same row in place without preserving old neighbor values, and use infinity rather than wrapping indices at the edges.

Then expect these follow-ups

How would you return the path itself?
Tests: parent pointers
What changes when moves are only down and down-right?
Tests: recurrence design

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question