0510MediumArrayDynamic ProgrammingMatrix

Courier Rack Capacity

Tracked in this browser only

Trains the technique from

LeetCode 3742Maximum Path Score in a Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A courier drives across a district laid out as m streets by n avenues. grid[i][j] is how many parcels are waiting at the corner on street i and avenue j. The depot sits at corner (0, 0) and has nothing waiting, and the sorting hall sits at corner (m - 1, n - 1).

From a corner the van may drive only to the next avenue, (i, j + 1), or to the next street, (i + 1, j). Whenever the van stands at a corner it must take every parcel waiting there, including at the depot and at the sorting hall, so a route's load is the total of the values of the corners it stands at.

The van's rack holds at most k parcels, so a route is drivable only when its load is at most k. Return the largest load of a drivable route, or -1 when every route from the depot to the sorting hall overloads the rack. A load is never negative, so -1 cannot be confused with a real load.

Examples

Example 1

Input: grid = [[0, 2, 0, 0], [0, 0, 0, 2]], k = 3
Output: 2

Driving to the second street straight away and then along it stands at corners holding 0, 0, 0, 0 and 2 parcels, so that route loads 2 parcels and fits a rack of 3.

Example 2

Input: grid = [[0, 2], [2, 2]], k = 1
Output: -1

There are only two routes across this district, and each of them stands at two corners holding 2 parcels, so each loads 4 parcels and neither fits a rack of 1.

Example 3

Input: grid = [[0, 2, 1, 0, 2], [1, 0, 2, 1, 0], [2, 1, 0, 2, 1]], k = 6
Output: 6

Driving along the first street to its end and then down the last avenue stands at corners holding 0, 2, 1, 0, 2, then 0 and 1, so that route loads 6 parcels and exactly fills the rack.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 2
grid[0][0] == 0
0 <= k <= 10^3

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_rack_load(grid: list[list[int]], k: int) -> int:

Java

public int bestRackLoad(int[][] grid, int k)

The intended approach

Time O(m * n * (m + n) / w) word operations, where w is the machine word size; each of the m * n corners does constant many operations on masks of O(m + n) bits.Space O(n * (m + n)) bits: one mask per avenue for the row being built.

Keeping only the best load per corner is not enough, because a lighter arrival can still be the one that survives the rest of the drive, so carry the entire set of reachable loads per corner instead. Each set is a bitmask with bit s set when a route arrives holding s parcels; standing at a corner shifts the incoming mask up by that corner's count, and two routes meeting at a corner combine with a bitwise or. Sweeping row by row keeps one row of masks alive, and the answer is the highest set bit of the final mask once bits above k are cleared.

Pythonentry point: best_rack_load

def best_rack_load(grid, k):
    # Track, for each cell, the whole set of loads a route can arrive with, held as
    # a bitmask whose bit s is set when load s is reachable. Entering a cell shifts
    # the incoming set up by that cell's parcel count, and merging two incoming
    # routes is a bitwise or. Reading the top set bit at or below k gives the
    # answer.
    # O(m * n * (m + n) / w) word operations for a machine word of w bits,
    # O(n * (m + n)) bits of space for one row of masks.
    rows = len(grid)
    cols = len(grid[0])
    row = [0] * cols
    row[0] = 1 << grid[0][0]
    for j in range(1, cols):
        row[j] = row[j - 1] << grid[0][j]
    for i in range(1, rows):
        nxt = [0] * cols
        nxt[0] = row[0] << grid[i][0]
        for j in range(1, cols):
            nxt[j] = (nxt[j - 1] | row[j]) << grid[i][j]
        row = nxt
    allowed = row[cols - 1] & ((1 << (k + 1)) - 1)
    if allowed == 0:
        return -1
    return allowed.bit_length() - 1

The obvious version

Walk every route from the depot with an explicit stack, carrying the running load, and when a route reaches the sorting hall keep its load if it fits the rack and beats the best seen. Exponential in m + n.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_rack_load(grid, k):
    rows = len(grid)
    cols = len(grid[0])
    best = -1
    stack = [(0, 0, grid[0][0])]
    while stack:
        i, j, load = stack.pop()
        if i == rows - 1 and j == cols - 1:
            if load <= k and load > best:
                best = load
            continue
        if j + 1 < cols:
            stack.append((i, j + 1, load + grid[i][j + 1]))
        if i + 1 < rows:
            stack.append((i + 1, j, load + grid[i + 1][j]))
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in