LeetCode 2087 - Minimum Cost Homecoming of a Robot in a Grid

LeetCode Problem 2087

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us a robot located on a two dimensional grid. The robot starts at startPos = [startrow, startcol] and wants to reach homePos = [homerow, homecol]. The robot can move one cell at a time in four directions: up, down, left, and right.

Unlike a standard shortest path problem where every move has the same cost, the cost here depends on the row or column that the robot enters.

If the robot moves vertically, either up or down, the cost is determined by the destination row:

• Moving into row r costs rowCosts[r]

If the robot moves horizontally, either left or right, the cost is determined by the destination column:

• Moving into column c costs colCosts[c]

The task is to compute the minimum total cost required for the robot to travel from its starting position to its home position.

An important detail is that movement cost depends only on the row or column being entered, not on the direction itself. Entering row 5 costs the same whether the robot came from row 4 or row 6.

The constraints are large:

• m, n <= 10^5

This immediately tells us that algorithms exploring many paths or using full graph traversal over the grid are not practical. Even storing the entire grid explicitly could become expensive.

Another important observation is that there are no blocked cells or obstacles. The robot can always move directly toward its destination. Since every move changes either the row or column by exactly one, the robot must eventually perform:

• abs(homerow - startrow) vertical moves
• abs(homecol - startcol) horizontal moves

The order of these moves may vary, but the set of rows and columns entered is fixed.

Some important edge cases include:

• The robot already starts at home, so the answer should be 0
• Movement may occur only vertically or only horizontally
• Costs may contain zeros
• The robot may need to move upward or leftward, not only downward or rightward
• Very large grids require an efficient linear solution

Approaches

Brute Force Approach

A brute force solution would treat the grid as a weighted graph. Each cell becomes a node, and moving to neighboring cells creates edges with costs determined by the destination row or column.

We could then apply a shortest path algorithm such as Dijkstra's algorithm.

This approach is correct because Dijkstra guarantees the minimum path cost in graphs with non negative edge weights.

However, this solution is far too expensive for the problem constraints. The grid may contain up to:

$$10^5 \times 10^5 = 10^{10}$$

cells in theory, which is completely impossible to represent or traverse.

Even though actual test cases are smaller in practice, the constraints clearly indicate that a graph based shortest path approach is not intended.

Key Insight

The crucial observation is that there are no obstacles and no alternative weighted routes that can reduce cost.

To move from row startrow to homerow, the robot must enter every intermediate row exactly once. There is no way to avoid paying those row costs.

Similarly, to move from column startcol to homecol, the robot must enter every intermediate column exactly once.

Because vertical and horizontal movement costs are independent, the total minimum cost is simply:

• Sum of all required row entry costs
• Plus sum of all required column entry costs

The order of movement does not matter.

This turns the problem from a graph shortest path problem into a simple range summation problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(mn log(mn))	O(mn)	Treats grid as a weighted graph and runs Dijkstra
Optimal	O(m + n) worst case	O(1)	Directly sums required row and column costs

Algorithm Walkthrough

1. Extract the starting row and column from startPos, and the target row and column from homePos.
2. Initialize a variable total_cost to 0. This will accumulate the minimum travel cost.
3. Handle vertical movement first.

If the robot needs to move downward, iterate from startrow + 1 through homerow, adding each corresponding rowCosts[r].

If the robot needs to move upward, iterate from startrow - 1 down through homerow, again adding each rowCosts[r].

We do not include the starting row because cost is only paid when entering a row. 4. Handle horizontal movement similarly.

If moving right, iterate from startcol + 1 through homecol, adding colCosts[c].

If moving left, iterate from startcol - 1 down through homecol, adding colCosts[c]. 5. Return the accumulated total_cost.

Why it works

The robot cannot teleport or skip rows and columns. Every path from the starting position to the home position must enter exactly the same set of required rows and columns.

Since each required row and column contributes a fixed unavoidable cost, every valid path has the same total cost. Therefore, simply summing those mandatory costs produces the minimum possible answer.

Python Solution

from typing import List

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int]
    ) -> int:
        start_row, start_col = startPos
        home_row, home_col = homePos

        total_cost = 0

        # Move vertically
        if start_row < home_row:
            for row in range(start_row + 1, home_row + 1):
                total_cost += rowCosts[row]
        else:
            for row in range(start_row - 1, home_row - 1, -1):
                total_cost += rowCosts[row]

        # Move horizontally
        if start_col < home_col:
            for col in range(start_col + 1, home_col + 1):
                total_cost += colCosts[col]
        else:
            for col in range(start_col - 1, home_col - 1, -1):
                total_cost += colCosts[col]

        return total_cost

The implementation follows the algorithm directly.

First, the code extracts the row and column coordinates from the input arrays. This improves readability and avoids repeated indexing operations later.

The variable total_cost stores the running sum of all required movement costs.

The vertical movement section determines whether the robot moves upward or downward. Depending on the direction, the code iterates through all rows that the robot enters and adds their associated costs.

The horizontal movement section works the same way for columns.

Notice that the loops always start one step away from the current position because the robot does not pay for the row or column it is already occupying. Costs are paid only when entering a new row or column.

Finally, the accumulated total is returned.

Go Solution

func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) int {
    startRow, startCol := startPos[0], startPos[1]
    homeRow, homeCol := homePos[0], homePos[1]

    totalCost := 0

    // Move vertically
    if startRow < homeRow {
        for row := startRow + 1; row <= homeRow; row++ {
            totalCost += rowCosts[row]
        }
    } else {
        for row := startRow - 1; row >= homeRow; row-- {
            totalCost += rowCosts[row]
        }
    }

    // Move horizontally
    if startCol < homeCol {
        for col := startCol + 1; col <= homeCol; col++ {
            totalCost += colCosts[col]
        }
    } else {
        for col := startCol - 1; col >= homeCol; col-- {
            totalCost += colCosts[col]
        }
    }

    return totalCost
}

The Go implementation mirrors the Python logic closely.

Go slices are used directly for startPos, homePos, rowCosts, and colCosts. Since Go integers are sufficient for the problem constraints, no special overflow handling is necessary.

The loops explicitly move in increasing or decreasing order depending on direction. This keeps the implementation simple and avoids needing helper functions.

Unlike Python, Go does not support reverse ranges directly, so the decrementing loops are written manually using row-- and col--.

Worked Examples

Example 1

Input:

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

The robot starts at (1, 0) and must reach (2, 3).

Vertical Movement

The robot moves from row 1 to row 2.

Step	Entered Row	Cost Added	Total
1	2	3	3

Horizontal Movement

The robot moves from column 0 to column 3.

Step	Entered Column	Cost Added	Total
1	1	2	5
2	2	6	11
3	3	7	18

Final answer:

18

Example 2

Input:

startPos = [0, 0]
homePos = [0, 0]
rowCosts = [5]
colCosts = [26]

The robot already starts at home.

No rows or columns are entered.

Action	Cost
No movement	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n) worst case	At most all rows and columns between start and home are traversed once
Space	O(1)	Only a few variables are used

The algorithm performs a simple linear scan over the rows and columns that must be traversed. No auxiliary data structures proportional to input size are required.

Even in the worst case, the robot moves across every row and every column at most once, giving linear complexity.

Test Cases

from typing import List

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int]
    ) -> int:
        start_row, start_col = startPos
        home_row, home_col = homePos

        total_cost = 0

        if start_row < home_row:
            for row in range(start_row + 1, home_row + 1):
                total_cost += rowCosts[row]
        else:
            for row in range(start_row - 1, home_row - 1, -1):
                total_cost += rowCosts[row]

        if start_col < home_col:
            for col in range(start_col + 1, home_col + 1):
                total_cost += colCosts[col]
        else:
            for col in range(start_col - 1, home_col - 1, -1):
                total_cost += colCosts[col]

        return total_cost

sol = Solution()

assert sol.minCost(
    [1, 0],
    [2, 3],
    [5, 4, 3],
    [8, 2, 6, 7]
) == 18  # Provided example

assert sol.minCost(
    [0, 0],
    [0, 0],
    [5],
    [26]
) == 0  # Already at home

assert sol.minCost(
    [3, 3],
    [0, 0],
    [1, 2, 3, 4],
    [5, 6, 7, 8]
) == 21  # Moving upward and leftward

assert sol.minCost(
    [0, 1],
    [3, 1],
    [1, 2, 3, 4],
    [10, 10]
) == 9  # Vertical movement only

assert sol.minCost(
    [2, 0],
    [2, 3],
    [1, 1, 1],
    [2, 3, 4, 5]
) == 12  # Horizontal movement only

assert sol.minCost(
    [0, 0],
    [2, 2],
    [0, 0, 0],
    [0, 0, 0]
) == 0  # Zero movement costs

assert sol.minCost(
    [4, 1],
    [1, 4],
    [5, 1, 2, 3, 4],
    [7, 8, 9, 10, 11]
) == 34  # Mixed movement directions

assert sol.minCost(
    [0, 0],
    [4, 4],
    [10000, 10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000, 10000]
) == 80000  # Large costs

Test Summary

Test	Why
Example 1	Validates normal mixed movement
Example 2	Validates zero movement
Moving upward and leftward	Ensures reverse iteration works correctly
Vertical movement only	Ensures column logic is skipped properly
Horizontal movement only	Ensures row logic is skipped properly
Zero movement costs	Verifies handling of zero values
Mixed movement directions	Tests combined upward and rightward movement
Large costs	Verifies handling of large numeric totals

Edge Cases

One important edge case occurs when the robot already starts at its home position. In this situation, no movement occurs, so no costs should be added. A buggy implementation might accidentally include the starting row or column cost. This implementation avoids that by always starting iteration one step away from the current position.

Another important case is moving upward or leftward. Many implementations only handle increasing indices correctly. Reverse traversal requires careful loop bounds, especially in languages like Go where reverse ranges are manual. The implementation explicitly handles both movement directions separately, ensuring correctness.

A third edge case involves zero costs. Some rows or columns may have cost 0, meaning entering them is free. The algorithm simply adds these values normally, so zero cost movements naturally work without any special handling.

A final subtle edge case is when movement occurs in only one dimension. For example, the robot may need to move only vertically while staying in the same column. The implementation handles this correctly because the horizontal loop becomes empty when the start and destination columns are equal.