There is an m x n grid, where (0, 0) is the top-left cell and (m - 1, n - 1) is the bottom-right cell. You are given an integer array startPos where startPos = [startrow, startcol] indicates that initially, a robot is at the cell (startrow, startcol). You are also given an integer array homePos where homePos = [homerow, homecol] indicates that its home is at the cell (homerow, homecol).
The robot needs to go to its home. It can move one cell in four directions: left, right, up, or down, and it can not move outside the boundary. Every move incurs some cost. You are further given two 0-indexed integer arrays: rowCosts of length m and colCosts of length n.
r, then this move costs rowCosts[r].c, then this move costs colCosts[c].Return the minimum total cost for this robot to return home.
Example 1:
Input: startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7] Output: 18 Explanation: One optimal path is that: Starting from (1, 0) -> It goes down to (2, 0). This move costs rowCosts[2] = 3. -> It goes right to (2, 1). This move costs colCosts[1] = 2. -> It goes right to (2, 2). This move costs colCosts[2] = 6. -> It goes right to (2, 3). This move costs colCosts[3] = 7. The total cost is 3 + 2 + 6 + 7 = 18
Example 2:
Input: startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26] Output: 0 Explanation: The robot is already at its home. Since no moves occur, the total cost is 0.
Constraints:
m == rowCosts.lengthn == colCosts.length1 <= m, n <= 1050 <= rowCosts[r], colCosts[c] <= 104startPos.length == 2homePos.length == 20 <= startrow, homerow < m0 <= startcol, homecol < nProblem Overview: A robot starts at one cell in a grid and needs to reach its home cell. Moving into a row or column has a specific cost, and the total cost depends on the rows and columns you enter during the trip. The task is to compute the minimum cost required to move from the start position to the home position.
Approach 1: Grid Traversal with BFS (Brute Force) (Time: O(m*n), Space: O(m*n))
A straightforward idea is to treat the grid as a graph and explore paths using breadth-first search. Each state represents a cell, and transitions correspond to moving up, down, left, or right with the appropriate row or column cost. The algorithm tracks the minimum cost to reach each cell. While correct, this approach explores many unnecessary states because the optimal path never requires detours away from the direct Manhattan route.
Approach 2: Directional Iterative Traversal (Time: O(|r2-r1| + |c2-c1|), Space: O(1))
The robot only needs to move vertically until it reaches the target row and horizontally until it reaches the target column. Instead of exploring the entire grid, iterate step-by-step in the required direction. Each vertical move adds rowCosts[row], and each horizontal move adds colCosts[col]. This approach simulates the movement but only along the necessary path, reducing the work to the number of required row and column transitions.
Approach 3: Direct Cost Calculation Based on Required Movements (Greedy) (Time: O(|r2-r1| + |c2-c1|), Space: O(1))
The key observation: the path order does not affect the total cost because costs depend only on which rows and columns you enter. You can sum all row costs between the start row and home row, and all column costs between the start column and home column. Whether you move horizontally first or vertically first produces the same result. This greedy calculation removes the need for explicit traversal and directly accumulates costs using simple loops.
Recommended for interviews: The greedy direct calculation is the expected solution. It demonstrates that you recognized the independence of row and column costs and avoided unnecessary path exploration. Discussing the traversal or BFS idea first shows problem understanding, but the optimal approach relies on a simple insight about movement constraints. Related concepts appear frequently in array manipulation and greedy decision problems.
This approach focuses on directly calculating the cost incurred for moving from startPos to homePos by traversing row-wise and column-wise. The movement can be made in any order, but the costs remain constant as they depend only on the final positions along each dimension.
This solution iterates over the necessary rows and columns to compute the cost, summing up appropriately based on the direction. If starting less than the home position, it sums forward through the costs, otherwise it sums backward.
Python
JavaScript
C++
Time Complexity: O(m + n), where m is the number of row costs accessed and n is the number of column costs accessed.
Space Complexity: O(1), as no additional space is used.
In this approach, the robot traverses from the start to home in the most straightforward directional steps iteratively, modifying its row or column index each step. This is practically moving cell-by-cell and adding up individual move costs.
The Java function iteratively moves the robot one step at a time towards home, adjusting both coordinates in a loop and accumulating the respective row or column costs, reflecting a step-by-step simulation of the task.
Time Complexity: O(m + n), considering a worst-case traversal covering all intermediate cells.
Space Complexity: O(1), with only a few integer variables utilized in computation.
| Approach | Complexity |
|---|---|
| Direct Calculation Based on Required Movements | Time Complexity: O(m + n), where m is the number of row costs accessed and n is the number of column costs accessed. |
| Directional Iterative Traversal | Time Complexity: O(m + n), considering a worst-case traversal covering all intermediate cells. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Grid Traversal with BFS | O(m*n) | O(m*n) | Conceptual brute-force when modeling the grid as a graph or verifying correctness. |
| Directional Iterative Traversal | O(|r2-r1| + |c2-c1|) | O(1) | When you want a clear step-by-step simulation of the robot's movement. |
| Direct Greedy Cost Calculation | O(|r2-r1| + |c2-c1|) | O(1) | Best approach for interviews and production due to simplicity and optimal complexity. |
2087. Minimum Cost Homecoming of a Robot in a Grid (Leetcode Medium) • Programming Live with Larry • 867 views views
Watch 5 more video solutions →Practice Minimum Cost Homecoming of a Robot in a Grid with our built-in code editor and test cases.
Practice on FleetCode