Jobs

Interviews

Discussions

Minimum Falling Path Sum

Medium

Uber

0 views

Topics:

ArraysDynamic Programming

Given an n x n array of integers matrix, return the minimum sum of any falling path through 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. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

For example, consider the following matrix:

matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]

In this case, the minimum falling path sum is 13. One such path is 2 -> 5 -> 6.

Now, consider the following matrix:

matrix = [[-19, 57], [-40, -5]]

In this case, the minimum falling path sum is -59 (i.e., -19 + -40).

Can you implement a function to find the minimum falling path sum of a given matrix? Discuss the time and space complexity of your solution. What are some edge cases to consider, and how does your implementation handle them?

Minimum Falling Path Sum

Medium

Uber

0 views

Topics:

ArraysDynamic Programming

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

For example, consider the following matrix:

matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]

In this case, the minimum falling path sum is 13. One such path is 2 -> 5 -> 6.

Now, consider the following matrix:

matrix = [[-19, 57], [-40, -5]]

In this case, the minimum falling path sum is -59 (i.e., -19 + -40).

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 is the range of values within the matrix, and can they be negative?
Can the input matrix be empty, or have dimensions of zero?
Is the input matrix guaranteed to be square (N x N), or can it be rectangular (N x M)?
If there are multiple minimum falling paths, is any one of them acceptable, or is there a specific path that should be returned (e.g., lexicographically smallest)?
What data type should I return representing the minimum falling path sum?

Brute Force Solution

Approach

The goal is to find the smallest sum of numbers you can get by moving down a grid, picking one number from each row. We'll explore every possible path to find the one with the minimum sum.

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

Start at the top row and pick a number.
From that number, consider all three possible numbers in the row below (the one directly below, and the ones diagonally left and right).
For each of those three numbers, repeat the process: look at the three numbers in the row below them.
Continue this process until you reach the bottom row for every possible path you started at the top with.
Each time you reach the bottom, add up all the numbers you picked along that particular path.
Compare all the sums from every possible path and choose the smallest one. That's the minimum falling path sum.

Code Implementation

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

    def find_path_sum(row, column):
        # Base case: Reached the bottom row, return the value.
        if row == number_of_rows - 1:
            return matrix[row][column]

        minimum_path_sum = float('inf')

        # Explore all possible next steps.
        for column_offset in [-1, 0, 1]:
            next_column = column + column_offset

            # Make sure the next column is within bounds.
            if 0 <= next_column < number_of_columns:

                path_sum =
                    matrix[row][column] + find_path_sum(row + 1, next_column)

                minimum_path_sum = min(minimum_path_sum, path_sum)

        return minimum_path_sum

    minimum_falling_path = float('inf')

    # Iterate through the starting columns of the top row
    for start_column in range(number_of_columns):

        # Explore all possible paths from each starting column.
        current_path_sum = find_path_sum(0, start_column)
        minimum_falling_path = min(minimum_falling_path,
                                     current_path_sum)

    return minimum_falling_path

Big(O) Analysis

Time Complexity

O(3^n) – The described approach explores all possible paths from the top row to the bottom row. At each cell, we have three possible downward moves: diagonally left, directly below, and diagonally right. Since we repeat this decision for each row, and there are 'n' rows in the grid, each starting position yields potentially 3^(n-1) or roughly 3^n paths. Therefore, the algorithm essentially explores a tree of possibilities where each node has up to three children for n levels. Thus, the time complexity grows exponentially with the number of rows.

Space Complexity

O(N) – The description suggests exploring every possible path using a recursive approach or dynamic programming. A recursive approach, without memoization, would lead to a recursion depth proportional to the number of rows in the grid, which is N. This results in a call stack that consumes O(N) space. Alternatively, dynamic programming often involves storing intermediate results in a table of the same dimensions as the input grid, resulting in O(N) auxiliary space, where N is the number of cells in the grid. Since the grid is likely N x N, this would mean O(N^2). Because the question states each row contains a single number, we know that it is an N x N matrix, therefore we simplify to O(N^2). Because the plain English specifically explores every path, a dynamic programming algorithm must create an auxiliary data structure to keep track of each path.

Optimal Solution

Approach

The goal is to find the path from top to bottom with the smallest sum by making intelligent choices at each step. Instead of trying every single path, we'll build the solution row by row, keeping track of the smallest possible sum to reach each cell. By the end we will have the answer at the bottom.

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

Imagine starting at the top row of numbers.
For each number in the second row, determine the smallest path from the top that reaches it. This means adding it to the smallest of the three numbers directly above it (left, center, and right, if they exist).
Repeat this process for each subsequent row. At each number in a row, add it to the smallest sum from the cells directly above it.
Continue until you reach the bottom row. The smallest number in the bottom row is the smallest falling path sum.

Code Implementation

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

    # Iterate through the matrix starting from the second row
    for row_index in range(1, number_of_rows):
        for column_index in range(number_of_columns):
            # Find the minimum of the possible paths from the previous row
            minimum_previous_path = matrix[row_index - 1][column_index]

            if column_index > 0:
                minimum_previous_path = min(minimum_previous_path, matrix[row_index - 1][column_index - 1])

            if column_index < number_of_columns - 1:
                minimum_previous_path = min(minimum_previous_path, matrix[row_index - 1][column_index + 1])

            # Update the current cell with the minimum path sum
            matrix[row_index][column_index] += minimum_previous_path

    # The minimum value in the last row is the result
    minimum_falling_sum = matrix[number_of_rows - 1][0]
    for column_index in range(1, number_of_columns):
        minimum_falling_sum = min(minimum_falling_sum, matrix[number_of_rows - 1][column_index])

    return minimum_falling_sum

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each cell of the input matrix. The input matrix is of size n x m, where n represents the number of rows and m represents the number of columns. For each cell, it performs a constant time operation to find the minimum of up to three adjacent cells in the previous row. Therefore, the overall time complexity is proportional to the number of cells in the matrix, which is n*m. Thus, the total operations approximate n * m, which simplifies to O(n*m).

Space Complexity

O(N) – The algorithm modifies the input matrix in-place and keeps track of the minimum path sum row by row. We need to consider if the in-place modification affects the space complexity. Typically, in-place modifications are considered part of the input and don't contribute to auxiliary space complexity. However, the plain English explanation describes building the solution row by row, implicitly suggesting the use of extra space to store intermediate results if not done in place. The described accumulation of smallest path sums at each cell requires retaining information about previously computed row sums for subsequent calculations. The bottom row's minimum is the result. Since we are calculating the sums row by row, we need at most the size of one row, or N, where N is the number of columns (and rows because it's a square matrix). Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 or throw an exception, depending on requirements, to handle invalid input.
1x1 matrix	The minimum falling path sum is simply the value of the single element in the matrix.
Matrix with only one row	The minimum falling path sum is the minimum value in that row.
Matrix with very large dimensions (scalability)	Dynamic programming approach should scale reasonably well, but space complexity should be considered for extremely large inputs; consider in-place optimization.
Matrix containing large negative numbers	The algorithm should correctly handle negative numbers and find the minimum path even with very low values.
Matrix containing large positive numbers, potential integer overflow in the sum	Use a data type with a larger range (e.g., long) to store the path sums to prevent overflow.
Matrix with all elements having the same value	The minimum falling path sum will be the sum of that value repeated N times (where N is the number of rows).
Matrix with a skewed distribution of values (e.g., mostly very large positive numbers with a few very small negative numbers)	The algorithm should still correctly identify the path containing the small negative numbers as the minimum path.

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 is the range of values within the matrix, and can they be negative?
Can the input matrix be empty, or have dimensions of zero?
Is the input matrix guaranteed to be square (N x N), or can it be rectangular (N x M)?
If there are multiple minimum falling paths, is any one of them acceptable, or is there a specific path that should be returned (e.g., lexicographically smallest)?
What data type should I return representing the minimum falling path sum?

Brute Force Solution

Approach

The goal is to find the smallest sum of numbers you can get by moving down a grid, picking one number from each row. We'll explore every possible path to find the one with the minimum sum.

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

Start at the top row and pick a number.
From that number, consider all three possible numbers in the row below (the one directly below, and the ones diagonally left and right).
For each of those three numbers, repeat the process: look at the three numbers in the row below them.
Continue this process until you reach the bottom row for every possible path you started at the top with.
Each time you reach the bottom, add up all the numbers you picked along that particular path.
Compare all the sums from every possible path and choose the smallest one. That's the minimum falling path sum.

Code Implementation

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

    def find_path_sum(row, column):
        # Base case: Reached the bottom row, return the value.
        if row == number_of_rows - 1:
            return matrix[row][column]

        minimum_path_sum = float('inf')

        # Explore all possible next steps.
        for column_offset in [-1, 0, 1]:
            next_column = column + column_offset

            # Make sure the next column is within bounds.
            if 0 <= next_column < number_of_columns:

                path_sum =
                    matrix[row][column] + find_path_sum(row + 1, next_column)

                minimum_path_sum = min(minimum_path_sum, path_sum)

        return minimum_path_sum

    minimum_falling_path = float('inf')

    # Iterate through the starting columns of the top row
    for start_column in range(number_of_columns):

        # Explore all possible paths from each starting column.
        current_path_sum = find_path_sum(0, start_column)
        minimum_falling_path = min(minimum_falling_path,
                                     current_path_sum)

    return minimum_falling_path

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine starting at the top row of numbers.
For each number in the second row, determine the smallest path from the top that reaches it. This means adding it to the smallest of the three numbers directly above it (left, center, and right, if they exist).
Repeat this process for each subsequent row. At each number in a row, add it to the smallest sum from the cells directly above it.
Continue until you reach the bottom row. The smallest number in the bottom row is the smallest falling path sum.

Code Implementation

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

    # Iterate through the matrix starting from the second row
    for row_index in range(1, number_of_rows):
        for column_index in range(number_of_columns):
            # Find the minimum of the possible paths from the previous row
            minimum_previous_path = matrix[row_index - 1][column_index]

            if column_index > 0:
                minimum_previous_path = min(minimum_previous_path, matrix[row_index - 1][column_index - 1])

            if column_index < number_of_columns - 1:
                minimum_previous_path = min(minimum_previous_path, matrix[row_index - 1][column_index + 1])

            # Update the current cell with the minimum path sum
            matrix[row_index][column_index] += minimum_previous_path

    # The minimum value in the last row is the result
    minimum_falling_sum = matrix[number_of_rows - 1][0]
    for column_index in range(1, number_of_columns):
        minimum_falling_sum = min(minimum_falling_sum, matrix[number_of_rows - 1][column_index])

    return minimum_falling_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 or throw an exception, depending on requirements, to handle invalid input.
1x1 matrix	The minimum falling path sum is simply the value of the single element in the matrix.
Matrix with only one row	The minimum falling path sum is the minimum value in that row.
Matrix with very large dimensions (scalability)	Dynamic programming approach should scale reasonably well, but space complexity should be considered for extremely large inputs; consider in-place optimization.
Matrix containing large negative numbers	The algorithm should correctly handle negative numbers and find the minimum path even with very low values.
Matrix containing large positive numbers, potential integer overflow in the sum	Use a data type with a larger range (e.g., long) to store the path sums to prevent overflow.
Matrix with all elements having the same value	The minimum falling path sum will be the sum of that value repeated N times (where N is the number of rows).
Matrix with a skewed distribution of values (e.g., mostly very large positive numbers with a few very small negative numbers)	The algorithm should still correctly identify the path containing the small negative numbers as the minimum path.