Jobs

Interviews

Discussions

Minimum Falling Path Sum II

Hard

Asked by:

More companies

17 views

Topics:

ArraysDynamic Programming

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2:

Input: grid = [[7]]
Output: 7

Constraints:

n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

Try coding it in LeetCode

Minimum Falling Path Sum II

Hard

Asked by:

17 views

Topics:

ArraysDynamic Programming

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2:

Input: grid = [[7]]
Output: 7

Constraints:

n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the matrix `arr` (number of rows/columns)?
Can the integers in the matrix be negative, zero, or only positive?
If there are multiple falling paths with the same minimum sum, is any one of them acceptable?
Is the input matrix guaranteed to be square, or should I handle the case where the number of rows and columns are different?
Is an empty matrix or a matrix with zero rows/columns a possible input, and if so, what should I return?

Brute Force Solution

Approach

The problem asks us to find the path with the smallest sum from top to bottom in a grid, with a catch: you can't pick adjacent columns in consecutive rows. The brute force approach is simple: try every single possible path from the top row to the bottom row.

Here's how the algorithm would work step-by-step:

Start at the top row and consider each number in that row as a potential starting point for a path.
For each number in the top row, explore all possible next numbers in the row below, making sure you don't pick a number in the same column as the number you just picked above it.
Continue this process for each subsequent row, always avoiding the column you used in the previous row.
Once you reach the bottom row, you've completed one possible path. Calculate the sum of all the numbers in that path.
Repeat this whole process, starting with a different number in the top row, and generating all other possible paths from top to bottom.
Keep track of the sum of each path you find.
After exploring every single possible path, compare the sums of all the paths, and pick the path with the smallest sum. That's your answer.

Code Implementation

def minimum_falling_path_sum_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    minimum_path_sum = float('inf')

    def calculate_path_sum(row, column, current_path_sum):
        nonlocal minimum_path_sum

        current_path_sum += matrix[row][column]

        # If we've reached the bottom row, update min
        if row == number_of_rows - 1:

            minimum_path_sum = min(minimum_path_sum, current_path_sum)
            return

        # Explore all possible next steps in next row
        for next_column in range(number_of_columns):
            # Ensure that we are not using adjacent columns
            if next_column != column:

                calculate_path_sum(row + 1, next_column, current_path_sum)

    # Iterate through first row as starting point
    for start_column in range(number_of_columns):
        calculate_path_sum(0, start_column, 0)

    return minimum_path_sum

Big(O) Analysis

Time Complexity

O(n^n) – The algorithm explores all possible paths from the top row to the bottom row of the grid. In each row, we have n choices. Since there are n rows, the total number of possible paths is n * (n-1) * (n-1) * ... * (n-1) which is approximately n * (n-1)^(n-1), where we decrement to remove the column picked in the prior row, however in the worst case this number is still close to n options for each row. Since there are n rows, this results in roughly n^n possible paths, which means the time complexity grows exponentially. Each path requires O(n) time to sum its elements; however, given the exponential number of paths, the dominant factor is the path enumeration giving O(n^n) overall.

Space Complexity

O(N) – The brute force approach explores all possible paths recursively. In the worst-case scenario, the recursion depth can reach N, where N is the number of rows in the grid. Each recursive call adds a stack frame to the call stack, requiring additional memory. Therefore, the space complexity is proportional to the maximum recursion depth, resulting in O(N) space due to the call stack.

Optimal Solution

Approach

The best way to find the smallest path sum is to build up the solution row by row, always remembering the best options we've seen so far. Instead of recalculating everything for each path, we update our best-known sums using information from the previous row.

Here's how the algorithm would work step-by-step:

Start with the top row of numbers. These are our starting path sums.
Move to the next row. For each number in this row, consider all possible paths from the previous row to reach it, but don't use the number directly above it.
To do this, find the smallest path sum from the previous row, excluding the column directly above the current number.
Add this smallest path sum to the current number. This is the new smallest path sum to reach this point.
Repeat this process for every number in the current row, updating the smallest path sums.
Continue this process for each row until you reach the last row.
The smallest number in the last row is the overall minimum falling path sum.

Code Implementation

def min_falling_path_sum_ii(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp_table = [row[:] for row in grid]

    for row_index in range(1, rows):
        for col_index in range(cols):
            minimum_path_sum = float('inf')
            
            # Find the minimum sum from the previous row, excluding the current column
            for previous_col_index in range(cols):
                if previous_col_index != col_index:
                    minimum_path_sum = min(minimum_path_sum, dp_table[row_index - 1][previous_col_index])

            dp_table[row_index][col_index] = grid[row_index][col_index] + minimum_path_sum

    #The minimum value in the last row represents the min path sum
    return min(dp_table[rows - 1])

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n rows in the input matrix. For each element in a row, it searches for the minimum value in the previous row, excluding the element directly above it. Finding this minimum requires examining up to n-1 elements in the previous row. Therefore, for each of the n rows, we perform approximately n operations for each of the n elements, which gives us roughly n * n operations. This results in a time complexity of O(n²).

Space Complexity

O(N) – The algorithm uses the input array to store the intermediate minimum falling path sums, modifying it in place. This means the auxiliary space used is proportional to the size of one row of the input array, which is N, where N is the number of columns (and thus elements) in each row. Although the input array itself is modified, the extra memory required is for finding and storing the minimum and second minimum from the previous row, but because the original input matrix is mutated, this temporary storage for the previous row is what determines the auxiliary space. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty, as there is no path.
Single row input array	Return the minimum element in the single row, as that's the only possible path.
Input array with only two rows	Handle by iterating through all possible paths that avoid the same column in consecutive rows and finding the minimum sum.
Large input array (e.g., 200x200) to test performance	Dynamic programming approach should be used to ensure efficient computation within reasonable time complexity, avoiding recursion which can lead to stack overflow.
Input array with all identical values	The solution should correctly find the minimum path, considering the constraint of not using the same column in consecutive rows, by selecting the next smallest even if same number.
Input array with negative numbers	The algorithm should correctly handle negative numbers, as they can contribute to minimizing the falling path sum.
Input array with very large positive numbers, potentially causing integer overflow during summation	Use a larger data type (e.g., long) to store the intermediate sums to prevent integer overflow.
Integer.MIN_VALUE in the input array	Handle this value by initializing minimum sums to large positive values initially, but also verify that using Integer.MAX_VALUE won't cause overflow problems when compared to Integer.MIN_VALUE during minimization calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the matrix `arr` (number of rows/columns)?
Can the integers in the matrix be negative, zero, or only positive?
If there are multiple falling paths with the same minimum sum, is any one of them acceptable?
Is the input matrix guaranteed to be square, or should I handle the case where the number of rows and columns are different?
Is an empty matrix or a matrix with zero rows/columns a possible input, and if so, what should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top row and consider each number in that row as a potential starting point for a path.
For each number in the top row, explore all possible next numbers in the row below, making sure you don't pick a number in the same column as the number you just picked above it.
Continue this process for each subsequent row, always avoiding the column you used in the previous row.
Once you reach the bottom row, you've completed one possible path. Calculate the sum of all the numbers in that path.
Repeat this whole process, starting with a different number in the top row, and generating all other possible paths from top to bottom.
Keep track of the sum of each path you find.
After exploring every single possible path, compare the sums of all the paths, and pick the path with the smallest sum. That's your answer.

Code Implementation

def minimum_falling_path_sum_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    minimum_path_sum = float('inf')

    def calculate_path_sum(row, column, current_path_sum):
        nonlocal minimum_path_sum

        current_path_sum += matrix[row][column]

        # If we've reached the bottom row, update min
        if row == number_of_rows - 1:

            minimum_path_sum = min(minimum_path_sum, current_path_sum)
            return

        # Explore all possible next steps in next row
        for next_column in range(number_of_columns):
            # Ensure that we are not using adjacent columns
            if next_column != column:

                calculate_path_sum(row + 1, next_column, current_path_sum)

    # Iterate through first row as starting point
    for start_column in range(number_of_columns):
        calculate_path_sum(0, start_column, 0)

    return minimum_path_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the top row of numbers. These are our starting path sums.
Move to the next row. For each number in this row, consider all possible paths from the previous row to reach it, but don't use the number directly above it.
To do this, find the smallest path sum from the previous row, excluding the column directly above the current number.
Add this smallest path sum to the current number. This is the new smallest path sum to reach this point.
Repeat this process for every number in the current row, updating the smallest path sums.
Continue this process for each row until you reach the last row.
The smallest number in the last row is the overall minimum falling path sum.

Code Implementation

def min_falling_path_sum_ii(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp_table = [row[:] for row in grid]

    for row_index in range(1, rows):
        for col_index in range(cols):
            minimum_path_sum = float('inf')
            
            # Find the minimum sum from the previous row, excluding the current column
            for previous_col_index in range(cols):
                if previous_col_index != col_index:
                    minimum_path_sum = min(minimum_path_sum, dp_table[row_index - 1][previous_col_index])

            dp_table[row_index][col_index] = grid[row_index][col_index] + minimum_path_sum

    #The minimum value in the last row represents the min path sum
    return min(dp_table[rows - 1])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty, as there is no path.
Single row input array	Return the minimum element in the single row, as that's the only possible path.
Input array with only two rows	Handle by iterating through all possible paths that avoid the same column in consecutive rows and finding the minimum sum.
Large input array (e.g., 200x200) to test performance	Dynamic programming approach should be used to ensure efficient computation within reasonable time complexity, avoiding recursion which can lead to stack overflow.
Input array with all identical values	The solution should correctly find the minimum path, considering the constraint of not using the same column in consecutive rows, by selecting the next smallest even if same number.
Input array with negative numbers	The algorithm should correctly handle negative numbers, as they can contribute to minimizing the falling path sum.
Input array with very large positive numbers, potentially causing integer overflow during summation	Use a larger data type (e.g., long) to store the intermediate sums to prevent integer overflow.
Integer.MIN_VALUE in the input array	Handle this value by initializing minimum sums to large positive values initially, but also verify that using Integer.MAX_VALUE won't cause overflow problems when compared to Integer.MIN_VALUE during minimization calculations.