What is the time complexity of Minimum Path Sum?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Minimum Path Sum?

This problem uses Array, Dynamic Programming, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Minimum Path Sum?

Insight 1: Dynamic programming can be used because the optimal path to a cell (i, j) depends only on the optimal paths to its immediate neighbors (i-1, j) and (i, j-1). Insight 2: The minimum path sum to cell (i, j) can be calculated as grid[i][j] + min(pathSum(i-1, j), pathSum(i, j-1)).

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimum Path Sum - LeetCode 64 Solution

Q: How to solve Minimum Path Sum?

The solution uses dynamic programming to calculate the minimum path sum to each cell in the grid. The approach leverages the grid itself to store the intermediate results. First, the first row and first column are initialized based on the path from the top-left corner. Then, for each remaining cell, the minimum path sum is calculated by adding the current cell's value to the minimum of the path sums from the cell above and the cell to the left. Finally, the value in the bottom-right cell represents the overall minimum path sum.

Q: Which companies ask LeetCode 64. Minimum Path Sum in interviews?

This problem is frequently asked at Amazon, Apple, Bloomberg, Dream11, General Motors and 10 more companies.

Minimum Path Sum - Complete Solution Guide

Minimum Path Sum is LeetCode problem 64, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example 1: Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum. Example 2: Input: grid = [[1,2,3],[4,5,6]] Output: 12 Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][

Detailed Explanation

The problem requires finding the minimum path sum from the top-left corner to the bottom-right corner of a given m x n grid filled with non-negative numbers. The allowed moves are only down or right at any point in time. The objective is to find the path that results in the smallest sum of numbers along the path.

Solution Approach

The solution uses dynamic programming to calculate the minimum path sum to each cell in the grid. The approach leverages the grid itself to store the intermediate results. First, the first row and first column are initialized based on the path from the top-left corner. Then, for each remaining cell, the minimum path sum is calculated by adding the current cell's value to the minimum of the path sums from the cell above and the cell to the left. Finally, the value in the bottom-right cell represents the overall minimum path sum.

Step-by-Step Algorithm

Step 1: Initialize the first cell (top-left) as the starting point.
Step 2: Iterate through the first row (excluding the first cell), and update each cell with the sum of itself and the cell to its left. This calculates the minimum path from the top-left to each cell in the first row.
Step 3: Iterate through the first column (excluding the first cell), and update each cell with the sum of itself and the cell above it. This calculates the minimum path from the top-left to each cell in the first column.
Step 4: Iterate through the rest of the grid (from index [1][1] to the bottom-right), and update each cell with the sum of itself and the minimum of the cell above and the cell to its left. grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]).
Step 5: The value at grid[m-1][n-1] now contains the minimum path sum from the top-left to the bottom-right corner. Return this value.

Key Insights

Insight 1: Dynamic programming can be used because the optimal path to a cell (i, j) depends only on the optimal paths to its immediate neighbors (i-1, j) and (i, j-1).
Insight 2: The minimum path sum to cell (i, j) can be calculated as grid[i][j] + min(pathSum(i-1, j), pathSum(i, j-1)).
Insight 3: Instead of creating a separate DP table, the input grid itself can be used to store the minimum path sums to each cell, reducing space complexity.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming, Matrix.

Companies

Asked at: Amazon, Apple, Bloomberg, Dream11, General Motors, Goldman Sachs, Google, Meta, Microsoft, Palo Alto Networks, Salesforce, TikTok, Uber, Yahoo, eBay.

Minimum Path Sum | LeetCode 64

Medium

Array Dynamic Programming Matrix

Time: O(m*n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Update the first row
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j-1];
        }

        // Update the first column
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i-1][0];
        }

        // Update the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }

        return grid[m-1][n-1];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 64: Minimum Path Sum - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Matrix

Companies

AmazonAppleBloombergDream11General MotorsGoldman SachsGoogleMeta

Stats

Difficulty:Medium

Languages:4

Companies:15

Problem #:64

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize the first cell (top-left) as the starting point.
2
Step 2: Iterate through the first row (excluding the first cell), and update each cell with the sum of itself and the cell to its left. This calculates the minimum path from the top-left to each cell in the first row.
3
Step 3: Iterate through the first column (excluding the first cell), and update each cell with the sum of itself and the cell above it. This calculates the minimum path from the top-left to each cell in the first column.
4
Step 4: Iterate through the rest of the grid (from index [1][1] to the bottom-right), and update each cell with the sum of itself and the minimum of the cell above and the cell to its left. grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]).
5
Step 5: The value at grid[m-1][n-1] now contains the minimum path sum from the top-left to the bottom-right corner. Return this value.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(m*n) because of the nested loops that visit each cell in the m x n grid. The space complexity is O(1) since we modify the input matrix in place, and do not use any extra data structures whose size depends on the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a separate DP table

An alternative approach involves creating a separate 2D array (DP table) of the same size as the input grid. The DP table stores the minimum path sum to each cell. The calculation logic remains the same, but instead of modifying the input grid, the DP table is updated. The value at dp[m-1][n-1] contains the result.

Time: O(m*n)Space: O(m*n)

Trade-offs: This approach avoids modifying the input grid but requires additional space proportional to the grid's size. Use this if modifying the original grid is not allowed or desirable. The main solution is preferred when in-place modification is allowed due to better space complexity.

Recursion with Memoization

A recursive solution can be formulated, but it will result in exponential time complexity without memoization. Memoization stores the computed minimum path sums for already visited cells, avoiding redundant calculations. This approach has a similar structure to the dynamic programming solution but is implemented using recursion.

Time: O(m*n)Space: O(m*n) due to the memoization table and the recursion call stack.

Trade-offs: While it can be more intuitive for some, the iterative DP approach is often preferred due to the overhead of function calls in recursion. Also, recursion depth could potentially lead to a stack overflow error in some cases.

✨

Key Insights

1Insight 1: Dynamic programming can be used because the optimal path to a cell (i, j) depends only on the optimal paths to its immediate neighbors (i-1, j) and (i, j-1).
2Insight 2: The minimum path sum to cell (i, j) can be calculated as grid[i][j] + min(pathSum(i-1, j), pathSum(i, j-1)).
3Insight 3: Instead of creating a separate DP table, the input grid itself can be used to store the minimum path sums to each cell, reducing space complexity.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Empty grid (m=0 or n=0). While the constraints state that m, n >= 1, a robust solution should ideally check for these edge cases. The code, as is, would throw an error when attempting to access grid[0].length. A check for `if not grid or not grid[0]: return 0` would handle this.
Edge case 2: Single cell grid (m=1, n=1). The code correctly handles this, as no iterations occur and the initial value of grid[0][0] is returned.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not initializing the first row and first column correctly. The minimum path sum to any cell in the first row (or first column) depends only on the cells to its left (or above). Forgetting to account for this initialization leads to incorrect results.

✗Common mistake 2: Forgetting to add the current cell's value (`grid[i][j]`) when calculating the minimum path sum. The path sum must include the value of all cells along the path.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Route planning. Consider a map represented as a grid, where each cell has an associated cost (e.g., travel time or fuel consumption). The algorithm can find the cheapest/fastest route from one location to another.

🏦Real-world scenario 2: Image processing. Finding the minimum energy path in an image can be useful for tasks like seam carving (resizing images by removing low-energy paths) or object detection.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Minimum Path Sum"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?