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];
}
};
Difficulty
and has an acceptance rate of about 69% (2+ million submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
- Matrix
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 62: Unique Paths
- problem 174: Dungeon Game
- problem 741: Cherry Pickup
- problem 1937: Maximum Number of Points with Cost
- problem 2087: Minimum Cost Homecoming of a Robot in a Grid
- problem 2304: Minimum Path Cost in a Grid
- problem 2435: Paths in Matrix Whose Sum Is Divisible by K
- problem 2662: Minimum Cost of a Path With Special Roads
Solved On The Same Day
- problem 13: Roman to Integer
- problem 21: Merge Two Sorted Lists
- problem 28: Find the Index of the First Occurrence in a String
- problem 35: Search Insert Position
- problem 58: Length of Last Word
- problem 66: Plus One
- problem 67: Add Binary
- problem 69: Sqrt(x)
- problem 70: Climbing Stairs
- problem 206: Reverse Linked List
- problem 242: Valid Anagram
- problem 278: First Bad Version
- problem 283: Move Zeroes
- problem 367: Valid Perfect Square
- problem 374: Guess Number Higher or Lower
- problem 389: Find the Difference
- problem 441: Arranging Coins
- problem 459: Repeated Substring Pattern
- problem 509: Fibonacci Number
- problem 657: Robot Return to Origin
- problem 682: Baseball Game
- problem 704: Binary Search
- problem 709: To Lower Case
- problem 744: Find Smallest Letter Greater Than Target
- problem 746: Min Cost Climbing Stairs
- problem 860: Lemonade Change
- problem 896: Monotonic Array
- problem 976: Largest Perimeter Triangle
- problem 1137: N-th Tribonacci Number
- problem 1232: Check If It Is a Straight Line
- problem 1275: Find Winner on a Tic Tac Toe Game
- problem 1351: Count Negative Numbers in a Sorted Matrix
- problem 1491: Average Salary Excluding the Minimum and Maximum Salary
- problem 1502: Can Make Arithmetic Progression From Sequence
- problem 1523: Count Odd Numbers in an Interval Range
- problem 1539: Kth Missing Positive Number
- problem 1572: Matrix Diagonal Sum
- problem 1672: Richest Customer Wealth
- problem 1768: Merge Strings Alternately
- problem 1822: Sign of the Product of an Array
- problem 2: Add Two Numbers
- problem 5: Longest Palindromic Substring
- problem 33: Search in Rotated Sorted Array
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 43: Multiply Strings
- problem 50: Pow(x, n)
- problem 54: Spiral Matrix
- problem 62: Unique Paths
- problem 63: Unique Paths II
- problem 73: Set Matrix Zeroes
- problem 74: Search a 2D Matrix
- problem 120: Triangle
- problem 139: Word Break
- problem 153: Find Minimum in Rotated Sorted Array
- problem 198: House Robber
- problem 221: Maximal Square
- problem 275: H-Index II
- problem 279: Perfect Squares
- problem 300: Longest Increasing Subsequence
- problem 436: Find Right Interval
- problem 445: Add Two Numbers II
- problem 528: Random Pick with Weight
- problem 540: Single Element in a Sorted Array
- problem 611: Valid Triangle Number
- problem 658: Find K Closest Elements
- problem 852: Peak Index in a Mountain Array
- problem 981: Time Based Key-Value Store
- problem 1041: Robot Bounded In Circle
- problem 1146: Snapshot Array
- problem 2300: Successful Pairs of Spells and Potions
- problem 154: Find Minimum in Rotated Sorted Array II
Extra
- 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