Jobs

Interviews

Discussions

Minimum Path Sum

Medium

Google

1 view

Topics:

ArraysDynamic Programming

You are given a m x n grid filled with non-negative numbers. Your task is to find a path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) such that the sum of all numbers along the path is minimized.

Constraints:

You can only move either down or right at any point in time.
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Explain how you would approach solving this problem and provide the code implementation for your solution. Discuss the time and space complexity of your approach. Also, consider and explain any edge cases.

Minimum Path Sum

Medium

Google

1 view

Topics:

ArraysDynamic Programming

Constraints:

You can only move either down or right at any point in time.
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

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 dimensions of the grid, `m` and `n`? Can they be zero?
Can the values in the `grid` be zero?
Is the `grid` guaranteed to be rectangular (i.e., all rows have the same number of columns)?
Could you provide an example of the input grid and the corresponding minimum path sum?
Are we guaranteed that there is always a path from the top-left to the bottom-right cell, or could there be a case where no path exists?

Brute Force Solution

Approach

The brute force way to find the minimum path sum involves exploring every possible route from the top-left corner to the bottom-right corner of the grid. We will calculate the sum of the numbers along each route and then compare them all. Finally, we'll pick the route with the smallest sum.

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

Start at the top-left corner of the grid.
Consider every possible path you can take to reach the bottom-right corner, only moving down or right.
For each path, add up all the numbers you encounter along that path.
Keep track of the total sum for each different path.
Once you have explored all possible paths and calculated their sums, compare all the sums.
The path with the smallest sum is the minimum path, and that sum is the answer.

Code Implementation

def minimum_path_sum_brute_force(grid):
    if not grid:
        return 0

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    def calculate_path_sum(row_index, column_index, current_path_sum):
        # If we reach the bottom-right, return the path sum
        if row_index == number_of_rows - 1 and column_index == number_of_columns - 1:
            return current_path_sum + grid[row_index][column_index]

        # If we go out of bounds, return infinity so it doesn't affect the min calculation
        if row_index >= number_of_rows or column_index >= number_of_columns:
            return float('inf')

        current_path_sum += grid[row_index][column_index]

        # Explore moving down
        down_path_sum = calculate_path_sum(row_index + 1, column_index, current_path_sum)

        # Explore moving right
        right_path_sum = calculate_path_sum(row_index, column_index + 1, current_path_sum)

        # Because the path must be minimum, pick the minimum path
        return min(down_path_sum, right_path_sum)

    return calculate_path_sum(0, 0, 0)

Big(O) Analysis

Time Complexity

O(2^(m+n)) – The provided brute force solution explores every possible path from the top-left to the bottom-right corner of an m x n grid, moving only down or right. At each step, we have two choices (down or right) until we reach the destination. In a m x n grid, we need to take a total of (m-1) steps down and (n-1) steps right, meaning we have m+n-2 total steps. Since each step has two choices, the total number of possible paths grows exponentially, roughly as 2^(m+n-2). Therefore, the time complexity is O(2^(m+n)).

Space Complexity

O(2^(M+N)) – The brute force approach explores every possible path from the top-left to the bottom-right corner using recursion. Since we can only move down or right, reaching the bottom-right corner (M rows, N columns) requires M+N-2 moves, each with two choices (down or right) except for the last move. The recursion depth can reach up to M+N, but more critically, the number of paths, and thus the recursive calls residing on the stack at a given moment during the exploration, grows exponentially with the number of steps. This leads to a recursion tree whose number of nodes is proportional to 2^(M+N), which dictates the auxiliary space required by the call stack. Therefore, the space complexity is O(2^(M+N)), where M is the number of rows and N is the number of columns in the grid.

Optimal Solution

Approach

The goal is to find the path with the smallest total cost from the top-left to the bottom-right of a grid. The efficient approach builds the solution step-by-step, remembering the best cost to reach each cell and using that information to make smart decisions.

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

Imagine starting at the top-left corner of the grid.
The cost to get to the starting cell is just the value of that cell itself.
Now, for each cell, figure out the cheapest way to reach it. This is done by adding the current cell's value to the smaller of the costs to reach it from either the cell directly above or the cell directly to the left.
In other words, the best path to a cell must come from either above or the left. Choose the lower-cost path.
Repeat this process for every cell in the grid, moving from left to right and top to bottom.
When you reach the bottom-right corner, the value stored there is the minimum cost to reach it from the top-left.
Essentially, you're building up the best possible path cost to each cell as you go, ensuring the final result is the absolute minimum.

Code Implementation

def minimum_path_sum(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    #Initialize first cell's path sum
    grid[0][0] = grid[0][0]

    # Initialize first column
    for row_index in range(1, number_of_rows):
        grid[row_index][0] += grid[row_index-1][0]

    # Initialize first row
    for column_index in range(1, number_of_columns):
        grid[0][column_index] += grid[0][column_index-1]

    # Iterate over grid to calc min path sum
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            # Choose the min path from top or left
            grid[row_index][column_index] += min(grid[row_index-1][column_index], \
                                               grid[row_index][column_index-1])

    # Result stores min path sum from top-left to bottom-right
    return grid[number_of_rows-1][number_of_columns-1]

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell in the grid to calculate the minimum path sum. The grid has 'm' rows and 'n' columns. The algorithm visits each cell exactly once, performing a constant amount of work (addition and comparison) at each cell to determine the minimum path sum to that cell. Therefore, the time complexity is proportional to the number of cells in the grid, resulting in a time complexity of O(m*n).

Space Complexity

O(1) – The algorithm modifies the input grid in place to store the minimum path sums. While modifying the input is a space consideration, it doesn't use auxiliary space. No additional data structures like lists, maps, or sets are created. Therefore, the space complexity is constant, independent of the grid's dimensions.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or empty, indicating no path exists or the cost is zero.
Grid with only one cell (1x1 grid)	Return the value of the single cell, as that is the only possible path.
Grid with one row or one column	Iterate through the single row or column and sum the values to get the minimum path sum.
Large grid dimensions (m and n are very large)	Dynamic programming avoids redundant calculations, providing an efficient solution.
Grid with large integer values that could lead to integer overflow	Use a data type that can accommodate larger numbers, such as long or double, to prevent overflow.
Grid with all cells having a value of 0	The algorithm will correctly find the path with the sum of 0, indicating a path with no cost.
Grid containing extremely large numbers, approaching the maximum integer value	Handle potential overflow by using appropriate data types like long, or consider using modular arithmetic if applicable based on the requirements.
Invalid input: grid contains negative numbers (problem states non-negative)	Either throw an exception or handle the negative numbers, by for example taking the absolute value (after clarifying this with the interviewer).

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 dimensions of the grid, `m` and `n`? Can they be zero?
Can the values in the `grid` be zero?
Is the `grid` guaranteed to be rectangular (i.e., all rows have the same number of columns)?
Could you provide an example of the input grid and the corresponding minimum path sum?
Are we guaranteed that there is always a path from the top-left to the bottom-right cell, or could there be a case where no path exists?

Brute Force Solution

Approach

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

Start at the top-left corner of the grid.
Consider every possible path you can take to reach the bottom-right corner, only moving down or right.
For each path, add up all the numbers you encounter along that path.
Keep track of the total sum for each different path.
Once you have explored all possible paths and calculated their sums, compare all the sums.
The path with the smallest sum is the minimum path, and that sum is the answer.

Code Implementation

def minimum_path_sum_brute_force(grid):
    if not grid:
        return 0

    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    def calculate_path_sum(row_index, column_index, current_path_sum):
        # If we reach the bottom-right, return the path sum
        if row_index == number_of_rows - 1 and column_index == number_of_columns - 1:
            return current_path_sum + grid[row_index][column_index]

        # If we go out of bounds, return infinity so it doesn't affect the min calculation
        if row_index >= number_of_rows or column_index >= number_of_columns:
            return float('inf')

        current_path_sum += grid[row_index][column_index]

        # Explore moving down
        down_path_sum = calculate_path_sum(row_index + 1, column_index, current_path_sum)

        # Explore moving right
        right_path_sum = calculate_path_sum(row_index, column_index + 1, current_path_sum)

        # Because the path must be minimum, pick the minimum path
        return min(down_path_sum, right_path_sum)

    return calculate_path_sum(0, 0, 0)

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-left corner of the grid.
The cost to get to the starting cell is just the value of that cell itself.
Now, for each cell, figure out the cheapest way to reach it. This is done by adding the current cell's value to the smaller of the costs to reach it from either the cell directly above or the cell directly to the left.
In other words, the best path to a cell must come from either above or the left. Choose the lower-cost path.
Repeat this process for every cell in the grid, moving from left to right and top to bottom.
When you reach the bottom-right corner, the value stored there is the minimum cost to reach it from the top-left.
Essentially, you're building up the best possible path cost to each cell as you go, ensuring the final result is the absolute minimum.

Code Implementation

def minimum_path_sum(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    #Initialize first cell's path sum
    grid[0][0] = grid[0][0]

    # Initialize first column
    for row_index in range(1, number_of_rows):
        grid[row_index][0] += grid[row_index-1][0]

    # Initialize first row
    for column_index in range(1, number_of_columns):
        grid[0][column_index] += grid[0][column_index-1]

    # Iterate over grid to calc min path sum
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            # Choose the min path from top or left
            grid[row_index][column_index] += min(grid[row_index-1][column_index], \
                                               grid[row_index][column_index-1])

    # Result stores min path sum from top-left to bottom-right
    return grid[number_of_rows-1][number_of_columns-1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or empty, indicating no path exists or the cost is zero.
Grid with only one cell (1x1 grid)	Return the value of the single cell, as that is the only possible path.
Grid with one row or one column	Iterate through the single row or column and sum the values to get the minimum path sum.
Large grid dimensions (m and n are very large)	Dynamic programming avoids redundant calculations, providing an efficient solution.
Grid with large integer values that could lead to integer overflow	Use a data type that can accommodate larger numbers, such as long or double, to prevent overflow.
Grid with all cells having a value of 0	The algorithm will correctly find the path with the sum of 0, indicating a path with no cost.
Grid containing extremely large numbers, approaching the maximum integer value	Handle potential overflow by using appropriate data types like long, or consider using modular arithmetic if applicable based on the requirements.
Invalid input: grid contains negative numbers (problem states non-negative)	Either throw an exception or handle the negative numbers, by for example taking the absolute value (after clarifying this with the interviewer).