Snowplow to the Road
After a storm, a small farm needs one cleared lane from the barn door to the road. The yard is a grid of squares. The barn door is the top-left square and the gate to the road is the bottom-right one. Drifts are uneven, so each square takes a different number of minutes to plough.
The plough only drives forward, so the lane can only go right or down from square to square. Which lane takes the least time to clear?
Your task
Write minClearingTime(snow). snow[r][c] is the minutes needed to clear square (r, c). Return the smallest total time of a lane that starts at the top-left square, ends at the bottom-right square, and moves one square right or down at each step.
The total includes both the first and the last square. Return only the time, not the lane.
minClearingTime(snow: int[][]) → int
Examples
snow = [[2, 1, 4], [3, 8, 1], [6, 2, 1]]
9
Clear 2 → 1 → 4 → 1 → 1 (right, right, down, down): 2 + 1 + 4 + 1 + 1 = 9 minutes. Going down the left side first costs 2 + 3 + 6 + 2 + 1 = 14.
snow = [[1, 2, 9], [5, 9, 9], [1, 1, 1]]
9
Always taking the cheaper next square starts 1 → 2, then is stuck between two 9s and ends with at least 14. The best lane pays 5 early to reach the easy bottom row: 1 + 5 + 1 + 1 + 1 = 9.
Constraints
- 1 ≤ number of rows, number of columns ≤ 100
- Every row has the same length.
- 0 ≤ snow[r][c] ≤ 100
Start with brute force
List every right/down lane and add up its minutes. A 100 × 100 yard has about 10⁵⁸ lanes, so that never finishes.
A greedy plough that always picks the cheaper next square is fast but wrong: the second example shows a cheap first step leading into a costly middle.
Hints
0 of 4 shown- Hint 1
Look at the gate square in the bottom-right corner. The lane reached it from one of only two squares. Which ones, and which would you rather have come from?
- Hint 2
It came from the square above or the square to the left. If you knew the cheapest time to reach each of those, the cheapest time to reach the gate is its own minutes plus the smaller of the two.
- Hint 3
That works for every square:
best(r, c) = snow[r][c] + min(best(r - 1, c), best(r, c - 1)). Squares on the top row only have a left neighbour, and squares on the left edge only have one above. - Hint 4
Fill the table row by row, left to right, so both neighbours are ready when you need them. A single row of values is enough: before you overwrite
best[c], it still holds the value from the row above.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The cheapest lane to any square must arrive from above or from the left, and the part before that must itself be the cheapest lane to that neighbour. So best(r, c) = snow[r][c] + min(above, left).
Trace the first example, one row at a time:
- Row 0
[2, 1, 4]: only from the left, so2, 3, 7. - Row 1
[3, 8, 1]: 2 + 3 = 5; then 8 + min(3, 5) = 11; then 1 + min(7, 11) = 8. - Row 2
[6, 2, 1]: 5 + 6 = 11; then 2 + min(11, 11) = 13; then 1 + min(8, 13) = 9.
The answer is 9. The code starts every cell at infinity so the first row works without a special case: on row 0, "above" is infinity and the left neighbour always wins.
function minClearingTime(snow) {
const cols = snow[0].length;
const best = new Array(cols).fill(Infinity); // best[c] for the current row
best[0] = 0;
for (const row of snow) {
best[0] += row[0]; // left edge: only from above
for (let c = 1; c < cols; c++) {
// best[c] still holds the row above; best[c - 1] is the square on the left
best[c] = row[c] + Math.min(best[c], best[c - 1]);
}
}
return best[cols - 1];
}def min_clearing_time(snow):
cols = len(snow[0])
best = [float("inf")] * cols # best[c] for the current row
best[0] = 0
for row in snow:
best[0] += row[0] # left edge: only from above
for c in range(1, cols):
# best[c] still holds the row above; best[c - 1] is the square on the left
best[c] = row[c] + min(best[c], best[c - 1])
return best[cols - 1]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.