Minimum Falling Path Sum Interview Question for Meta

import sys


def minFallingPathSum(matrix):
    n = len(matrix)

    # Create a DP table to store the minimum falling path sum for each cell
    dp = [[0] * n for _ in range(n)]

    # Initialize the first row of the DP table with the values from the matrix
    for j in range(n):
        dp[0][j] = matrix[0][j]

    # Iterate over the remaining rows
    for i in range(1, n):
        for j in range(n):
            # Calculate the minimum falling path sum for the current cell
            # by considering the three possible paths from the previous row
            if j == 0:
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i - 1][j + 1])
            elif j == n - 1:
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j])
            else:
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])

    # The minimum falling path sum is the minimum value in the last row of the DP table
    return min(dp[n - 1])


# Example usage
matrix1 = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]
print(minFallingPathSum(matrix1))  # Output: 13

matrix2 = [[-19, 57], [-40, -5]]
print(minFallingPathSum(matrix2))  # Output: -59

matrix3 = [[100, -42, -46, -41], [31, 97, 10, -10], [-58, -51, 82, 89], [51, 81, 69, -51]]
print(minFallingPathSum(matrix3)) # Output: -64


# Brute Force Solution (Recursion - Exceeds time limit for larger inputs)
def minFallingPathSum_brute_force(matrix):
    n = len(matrix)
    min_sum = sys.maxsize

    def find_path(row, col, current_sum):
        nonlocal min_sum

        if row == n:
            min_sum = min(min_sum, current_sum)
            return

        # Move down
        find_path(row + 1, col, current_sum + matrix[row][col])

        # Move diagonally left
        if col > 0:
            find_path(row + 1, col - 1, current_sum + matrix[row][col])

        # Move diagonally right
        if col < n - 1:
            find_path(row + 1, col + 1, current_sum + matrix[row][col])

    for start_col in range(n):
        find_path(0, start_col, 0)

    return min_sum




# Big O analysis for DP solution:
# Time Complexity: O(n^2), where n is the size of the matrix. We iterate through each cell of the matrix once to fill the DP table.
# Space Complexity: O(n^2), where n is the size of the matrix. We use a DP table of the same size as the input matrix to store the minimum falling path sums.

# Big O analysis for Brute Force solution:
# Time Complexity: O(3^n), where n is the number of rows in the matrix. In the worst case, we have three possible paths for each cell (down, diagonally left, and diagonally right), leading to exponential time complexity.
# Space Complexity: O(n), where n is the number of rows in the matrix. This is due to the call stack during recursion.


# Edge Cases:
# 1. Empty matrix: If the input matrix is empty, the function should return 0 (or raise an exception, depending on the requirements).
# 2. Matrix with only one row: In this case, the minimum falling path sum is simply the minimum value in that row.
# 3. Matrix with negative values: The algorithm should correctly handle negative values in the matrix.
# 4. Matrix with large values: The algorithm should handle large integer values to avoid potential overflow issues.

Explanation:

The problem asks for the minimum sum of any falling path through a given n x n matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right.

1. Dynamic Programming (Optimal Solution):

Approach: We use dynamic programming to solve this problem efficiently. We create a DP table dp of the same size as the input matrix, where dp[i][j] stores the minimum falling path sum ending at matrix[i][j]. We initialize the first row of dp with the values from the first row of matrix. Then, for each subsequent row, we calculate dp[i][j] by taking the minimum of the three possible paths from the previous row (i.e., dp[i-1][j-1], dp[i-1][j], and dp[i-1][j+1]) and adding it to matrix[i][j]. Finally, the minimum value in the last row of dp is the minimum falling path sum.
Code: The Python code provided implements this DP approach.

2. Brute Force (Recursive Solution):

Approach: A brute-force approach would involve recursively exploring all possible falling paths from each starting column in the first row. For each cell, we can move to one of three cells in the next row: directly below, diagonally left, or diagonally right. We keep track of the current sum of the path and update the minimum sum when we reach the last row.
Code: The minFallingPathSum_brute_force function provides an example of the brute-force recursive solution. This will result in exceeding time limits for larger input sizes.

Big O Analysis (DP Solution):

Time Complexity: O(n^2), where n is the size of the matrix. We iterate through each cell of the matrix once to fill the DP table.
Space Complexity: O(n^2), where n is the size of the matrix. We use a DP table of the same size as the input matrix to store the minimum falling path sums.

Big O Analysis (Brute Force Solution):

Time Complexity: O(3^n), where n is the number of rows in the matrix. In the worst case, we have three possible paths for each cell (down, diagonally left, and diagonally right), leading to exponential time complexity.
Space Complexity: O(n), where n is the number of rows in the matrix. This is due to the call stack during recursion.

Edge Cases:

Empty matrix: If the input matrix is empty, the function should return 0 (or raise an exception, depending on the requirements).
Matrix with only one row: In this case, the minimum falling path sum is simply the minimum value in that row.
Matrix with negative values: The algorithm should correctly handle negative values in the matrix.
Matrix with large values: The algorithm should handle large integer values to avoid potential overflow issues.