Problem 64

Abstract / Summary

Find the smallest total by moving only right or down from the top left to bottom right in a grid of numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0064.cpp

class Solution {
public:
    int minPathSum2(vector<vector<int>>& grid) {
        int w = grid.size();
        int h = grid[0].size();

        multimap<int, pair<int, int>> next;
        next.insert({ grid[0][0], { 0, 0 } });

        set<pair<int, int>> done;

        vector<vector<int>> cheapest;
        cheapest.resize(w);
        for (auto& c : cheapest)
            c.resize(h);

        int iteration = 1;
        while (true)
        {
            auto n = next.begin();
            auto cost = n->first;
            auto x = n->second.first;
            auto y = n->second.second;

            cheapest[x][y] = cost;

            if (x == w-1 && y == h-1)
                return cost;

            next.erase(next.begin());
            if (done.count({ x, y }) > 0)
                continue;
            done.insert({ x, y });

            if (x < w-1)
                next.insert({ cost + grid[x+1][y], { x+1, y } });
            if (y < h-1)
                next.insert({ cost + grid[x][y+1], { x, y+1 } });
        }

        return 0;
    }


    int minPathSum(vector<vector<int>>& grid) {
        int h = grid.size();
        int w = grid[0].size();

        vector<vector<int>> cheapest;
        cheapest.resize(h);
        for (auto& c : cheapest)
            c.resize(w);

        cheapest[0][0] = grid[0][0];

        for (int x = 0; x < w; x++)
            for (int y = 0; y < h; y++)
            {
                int lowest = 9999999;
                if (x > 0)
                    lowest          = grid[y][x] + cheapest[y][x-1];
                if (y > 0 && lowest > grid[y][x] + cheapest[y-1][x])
                    lowest          = grid[y][x] + cheapest[y-1][x];

                if (x > 0 || y > 0)
                    cheapest[y][x] = lowest;
            }

        return cheapest[h-1][w-1];
    }
};
71 lines | 1905 bytes | submitted August 7, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 69% (2+ million submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
  • Matrix
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided source defines a class Solution that contains two public member functions, both named minPathSum with different implementations. Each function computes the minimum sum of values along a path from the top-left corner to the bottom-right corner of a 2-dimensional integer grid, moving only rightward or downward. The first implementation, minPathSum2, uses a priority-driven expansion reminiscent of Dijkstra’s algorithm. The second implementation, minPathSum, employs a straightforward dynamic programming table that fills the grid in a row-major order.

minPathSum2 - priority-driven expansion

The function begins by extracting the dimensions of the grid:

int w = grid.size();
int h = grid[0].size();

A multimap named next stores candidate cells together with their accumulated cost. The starting cell is inserted with its own value:

next.insert({ grid[0][0], { 0, 0 } });

A set called done records cells that have already been processed, preventing duplicate work. A 2-D vector cheapest is allocated to hold the final minimal cost for each cell.

The core loop repeatedly extracts the entry with the smallest accumulated cost:

auto n = next.begin();
auto cost = n->first;
auto x = n->second.first;
auto y = n->second.second;

The extracted cost is stored in cheapest[x][y]. If the extracted cell is the destination (w-1, h-1), the function returns the cost immediately, guaranteeing that the first time the destination is reached it is via the cheapest possible route.

The entry is then removed from next. A guard checks whether the cell has already been processed; if so, the loop continues without expanding its neighbors. Otherwise the cell is marked as processed:

if (done.count({ x, y }) > 0)
    continue;
done.insert({ x, y });

Neighbouring cells to the right and down are generated if they lie within the grid bounds, and each is inserted into next with an updated cost:

if (x < w-1)
    next.insert({ cost + grid[x+1][y], { x+1, y } });
if (y < h-1)
    next.insert({ cost + grid[x][y+1], { x, y+1 } });

The loop runs indefinitely until the destination is reached, at which point the function exits.

Edge handling in minPathSum2

The algorithm naturally handles grids of any size, including a single-cell grid. In that case the initial insertion contains the destination, the loop extracts it, stores the cost, detects that it is the bottom-right cell, and returns the value without attempting to generate neighbours. The done set prevents revisiting cells that could be reached via multiple paths, ensuring that each cell’s cheapest cost is recorded exactly once.

minPathSum - dynamic programming table

The second function extracts the grid dimensions in the opposite order, naming the first dimension h (rows) and the second w (columns). It allocates a 2-D vector cheapest sized h × w and seeds the starting cell:

cheapest[0][0] = grid[0][0];

Two nested loops iterate over every column x and row y. For each cell the algorithm computes the cheapest cost to reach it by considering the cell directly above and the cell directly to the left, when those neighbours exist. An initial large sentinel value is used:

int lowest = 9999999;

If a left neighbour exists, the cost through that neighbour is calculated:

if (x > 0)
    lowest = grid[y][x] + cheapest[y][x-1];

If an upper neighbour exists and yields a smaller total, the sentinel is replaced:

if (y > 0 && lowest > grid[y][x] + cheapest[y-1][x])
    lowest = grid[y][x] + cheapest[y-1][x];

For all cells except the origin, the computed lowest value is stored:

if (x > 0 || y > 0)
    cheapest[y][x] = lowest;

After the table is fully populated, the bottom-right entry holds the answer and is returned:

return cheapest[h-1][w-1];

Edge handling in minPathSum

The sentinel 9999999 is sufficiently large to be overridden by any legitimate path sum, even for grids with maximal integer values within typical problem constraints. The conditional checks x > 0 and y > 0 ensure that the algorithm never accesses out-of-bounds indices, correctly handling the first row and first column where only one predecessor exists. For a 1×1 grid the nested loops still execute, but the condition x > 0 || y > 0 prevents overwriting the already seeded origin, and the final return yields the single cell’s value.

Performance optimizations observed

In minPathSum2 the use of a multimap provides an ordered container that always yields the smallest accumulated cost in logarithmic time. By pairing this with a set of processed cells, the algorithm avoids expanding the same cell multiple times, which reduces redundant insertions and keeps the size of the frontier manageable. The early exit when the destination cell is extracted eliminates any further work once the optimal path is found.

The minPathSum implementation benefits from in-place table updates that avoid recomputation. By iterating in a deterministic order (column first, then row), each cell’s dependencies are guaranteed to have been computed already, allowing a single pass without backtracking. The allocation of the cheapest table with a single resize per row avoids repeated reallocation, contributing to cache-friendly memory layout.

Both functions allocate a dedicated 2-D vector for the cheapest costs, which isolates the original grid from modifications and enables direct indexing without additional indirection. The explicit dimension variables (w, h) are stored locally, avoiding repeated calls to size() inside tight loops. This small but consistent practice reduces overhead in the inner computation steps.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a grid filled with colored squares, like a large game board on the floor. Each square has a special number painted on it. The goal is to walk from the top corner to the opposite bottom corner, collecting the numbers as you step on each square. You want to pick the path that adds up to the smallest total, almost like finding the quietest path through a busy playground.

The first way to solve this is like exploring a path by always looking at every option that is close by. It keeps a list of potential steps and always picks the one with the smallest sum discovered so far. It remembers where it has already been so that it does not go in circles. It keeps exploring these steps until it finally lands on the very last square in the corner.

The second way is slightly different. It looks at the board like a notebook. It starts at the top corner and fills in a second, imaginary board. Each spot on this new board keeps track of the smallest possible sum to reach that specific square. To figure out the number for any spot, it looks at the squares right above it and right to the left of it, picks the smaller value, and adds the number from the game board to that tiny amount. By the time it fills in the very last corner, the answer is already sitting right there waiting to be seen.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 5 | μ = 5.00 | σ = 1.66

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python C# Rust JS Java Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
DimitrisJim C
everthis JS
FelixFan1122 C#
fengvyi C++
fpdjsns C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
martianoff Scala
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
XiaotaoGuo C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python, Python
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
DimitrisJim C
everthis JavaScript
FelixFan1122 C#
fengvyi C++
fpdjsns C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
martianoff Scala
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
XiaotaoGuo C++
zfang399 C++
55 links | 38 authors | 10 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Minimum Path Sum | Recursion | Bottom Up | Leetcode 64 | codestorywithMIK'
codestorywithMIK 35 mins
Minimum Path Sum | Recursion | Bottom Up | Leetcode 64 | codestorywithMIK
YouTube video 'LeetCode 30 day Challenge | Day 18 | Minimum Path Sum (C++, Java, Python) | LeetCode 64'
Knowledge Center 18 mins
LeetCode 30 day Challenge | Day 18 | Minimum Path Sum (C++, Java, Python) | LeetCode 64
YouTube video '[Java] Leetcode 64. Minimum Path Sum [DP Min/Max Path to Target #2]'
Eric Programming 19 mins
[Java] Leetcode 64. Minimum Path Sum [DP Min/Max Path to Target #2]
YouTube video 'LeetCode 64 | Minimum Path Sum | Dynamic Programming Algorithm Explained (Java)'
Xavier Elon 9 mins
LeetCode 64 | Minimum Path Sum | Dynamic Programming Algorithm Explained (Java)
YouTube video '64 || Minimum Path Sum || C++ || Leetcode Daily Challenge'
CodeFreaks 13 mins
64 || Minimum Path Sum || C++ || Leetcode Daily Challenge
YouTube video 'Leetcode 64 - Minimum Path Sum (JAVA Solution Explained!)'
LC Bear 9 mins
Leetcode 64 - Minimum Path Sum (JAVA Solution Explained!)
YouTube video 'Leetcode 64: Minimum Path Sum'
Algorithms Casts 37 mins
Leetcode 64: Minimum Path Sum
YouTube video 'Minimum Path Sum - Leetcode 64 - Part 1 - Java'
Mastering Programming 7 mins
Minimum Path Sum - Leetcode 64 - Part 1 - Java
YouTube video 'LeetCode 64: Minimum Path Sum | Java Solution | Dynamic Programming'
Code Scribbler 8 mins
LeetCode 64: Minimum Path Sum | Java Solution | Dynamic Programming
YouTube video 'LeetCode 64: Minimum Path Sum | Python Solution | Dynamic Programming'
Code Scribbler 8 mins
LeetCode 64: Minimum Path Sum | Python Solution | Dynamic Programming
YouTube video 'Daily Leetcode #1091: Mar 27, 2023 - 64. Minimum Path Sum'
Programming Live with Larry 10 mins
Daily Leetcode #1091: Mar 27, 2023 - 64. Minimum Path Sum
YouTube video 'LeetCode: 64. Minimum Path Sum (Visualized)'
Code With Zi 14 mins
LeetCode: 64. Minimum Path Sum (Visualized)
YouTube video 'Minimum Path Sum || LeetCode 64 || C++'
Nipun Mittal 15 mins
Minimum Path Sum || LeetCode 64 || C++
YouTube video '64. Minimum Path Sum | JavaScript | Recursion | Memoization | LeetCode Daily Challenge'
LeetCodeWithMonu 24 mins
64. Minimum Path Sum | JavaScript | Recursion | Memoization | LeetCode Daily Challenge
YouTube video 'Day 288: LeetCode Problem 64. Minimum Path Sum - Swift'
iOSxBank 12 mins
Day 288: LeetCode Problem 64. Minimum Path Sum - Swift
YouTube video '64. Minimum Path Sum (Leetcode Medium)'
Programming Live with Larry 16 mins
64. Minimum Path Sum (Leetcode Medium)
YouTube video 'Minimum Path Sum - Leetcode 64 - Python'
Lit Code 7 mins
Minimum Path Sum - Leetcode 64 - Python
YouTube video 'LeetCode 64 - Minimum Path Sum [Daily Challenge]'
Code with Carter 16 mins
LeetCode 64 - Minimum Path Sum [Daily Challenge]
YouTube video '203. Leetcode 64. Minimum Path Sum : JAVA'
Web Fusion with Bharadwaj 16 mins
203. Leetcode 64. Minimum Path Sum : JAVA
YouTube video 'LeetCode 64: Minimum Path Sum | CSharp Solution | Dynamic Programming'
Code Scribbler 8 mins
LeetCode 64: Minimum Path Sum | CSharp Solution | Dynamic Programming
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

8 similar problems

Solved On The Same Day

40 easy 30 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality