0852MediumArrayGreedy

Toll to Drive the Rover Home

Tracked in this browser only

Trains the technique from

LeetCode 2087Minimum Cost Homecoming of a Robot 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 rover sits on a grid of m rows by n columns at startPos = [startRow, startCol] and must reach homePos = [homeRow, homeCol].

One move takes the rover to a cell sharing an edge with the one it is on, and the grid may not be left. Moving into the cell at row r, column c costs rowCosts[r] when the move changed the row, and colCosts[c] when the move changed the column. Leaving a cell costs nothing, and the starting cell costs nothing.

Return the least total cost of driving the rover home.

Examples

Example 1

Input: startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
Output: 18

The rover enters row 2 and columns 1, 2 and 3, costing 3 + 2 + 6 + 7 = 18.

Example 2

Input: startPos = [1, 1], homePos = [1, 1], rowCosts = [3, 4], colCosts = [5, 6]
Output: 0

The rover is already home, so it enters no new row or column and pays nothing.

Example 3

Input: startPos = [2, 2], homePos = [0, 0], rowCosts = [1, 2, 3], colCosts = [4, 5, 6]
Output: 12

Driving up and to the left, the rover enters rows 1 and 0 and columns 1 and 0, costing 2 + 1 + 5 + 4 = 12.

Constraints

1 <= rowCosts.length <= 10^5
1 <= colCosts.length <= 10^5
0 <= rowCosts[r] <= 10^4
0 <= colCosts[c] <= 10^4
startPos.length == 2
homePos.length == 2
0 <= startPos[0] <= 99999
0 <= startPos[1] <= 99999
0 <= homePos[0] <= 99999
0 <= homePos[1] <= 99999
Both positions lie inside the grid

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 rover_toll(startPos: list[int], homePos: list[int], rowCosts: list[int], colCosts: list[int]) -> int:

Java

public int roverToll(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts)

The intended approach

Time O(m + n) worst case: one walk over the spanned rows and columns.Space O(1).

The cost of entering a cell depends only on the row or the column reached, never on the route taken to it, so a move that steps away from the target is always paid for and then has to be paid for again on the way back. That makes any route that only ever moves towards the target cheapest, and every such route enters exactly the rows strictly between the start row and the home row plus the home row itself, and likewise for the columns. So the answer is the sum of the row costs and column costs over those spans, in whichever direction the target lies.

Pythonentry point: rover_toll

def rover_toll(startPos, homePos, rowCosts, colCosts):
    sr, sc = startPos[0], startPos[1]
    hr, hc = homePos[0], homePos[1]
    total = 0
    step = 1 if hr > sr else -1
    r = sr
    while r != hr:
        r += step
        total += rowCosts[r]
    step = 1 if hc > sc else -1
    c = sc
    while c != hc:
        c += step
        total += colCosts[c]
    return total

The obvious version

Fill a table of least costs by repeated relaxation: start the rover's own cell at zero and keep pushing each cell's cost into its four neighbours, paying the row or column cost of the cell entered, until a full sweep changes nothing. Explores routes that move away from the target as well, so it makes no assumption about which direction is worth taking.

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_rover_toll(startPos, homePos, rowCosts, colCosts):
    m = len(rowCosts)
    n = len(colCosts)
    INF = float("inf")
    best = [[INF] * n for _ in range(m)]
    best[startPos[0]][startPos[1]] = 0
    moving = True
    while moving:
        moving = False
        for r in range(m):
            for c in range(n):
                if best[r][c] == INF:
                    continue
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr = r + dr
                    nc = c + dc
                    if not (0 <= nr < m and 0 <= nc < n):
                        continue
                    price = rowCosts[nr] if dr else colCosts[nc]
                    if best[r][c] + price < best[nr][nc]:
                        best[nr][nc] = best[r][c] + price
                        moving = True
    return best[homePos[0]][homePos[1]]

How this problem was checked

Reference solution executed against 11 test cases — 11 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