Minimum Cost to Move a Robot Home
Company: Juspay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A robot moves one cell at a time up, down, left or right within a rectangular grid. A vertical move into row `r` costs `rowCosts[r]`, and a horizontal move into column `c` costs `colCosts[c]`. Given its starting cell `startPos` and destination `homePos`, return the minimum total cost to reach home. No cost is charged merely for occupying the starting cell.
```cpp
class Solution {
public:
int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts);
};
```
### Examples
**Example 1:**
```text
startPos = [0,0], homePos = [1,1], rowCosts = [8,3], colCosts = [7,4]
Output: 7
Explanation: Enter row 1 for 3 and column 1 for 4, in either order.
```
**Example 2:**
```text
startPos = [1,1], homePos = [0,1], rowCosts = [5,2], colCosts = [9,6]
Output: 5
Explanation: Only the upward move into row 0 is required.
```
### Constraints
- Row and column counts lie in `[1,10^5]`.
- All costs lie in `[0,10^4]`.
- Both positions have two valid zero-based coordinates.
### Clarifying Questions
Only the row cost applies to a vertical move, and only the column cost to a horizontal move. Zero costs are valid.
```hint Inspect the structure
Which row and column entries must every route incur at least once?
```
### Reasoning checkpoints
- Charge the entered coordinate for each move and stay within the grid.
- Prove both a lower bound on the cost and a route that attains the returned value.
- Handle zero costs, movement in either coordinate direction and a start already at home.
### Optional extensions
Would allowing negative movement costs preserve this reasoning?
Overview: Minimum Cost to Move a Robot Home. A robot moves one cell at a time in four directions inside a rectangular grid. A vertical move entering row r costs rowCosts[r]; a horizontal move entering column c costs colCosts[c]. Given startPos and homePos, return the least total cost to reach home. The starting cell itself is not charged.