Watch 6 video solutions for Minimum Cost Homecoming of a Robot in a Grid, a medium level problem involving Array, Greedy. This walkthrough by Programming Live with Larry has 867 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |