# Minimum Cost Homecoming of a Robot in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-homecoming-of-a-robot-in-a-grid
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [HP](https://scaleengineer.com/companies/hp)
---
## Problem
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`.

* If the robot moves **up** or **down** into a cell whose **row** is `r`, then this move costs `rowCosts[r]`.
* If the robot moves **left** or **right** into a cell whose **column** is `c`, then this move costs `colCosts[c]`.

Return _the **minimum total cost** for this robot to return home_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-cost-homecoming-of-a-robot-in-a-grid/image0.png) 

**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.length`
* `n == colCosts.length`
* `1 <= m, n <= 105`
* `0 <= rowCosts[r], colCosts[c] <= 104`
* `startPos.length == 2`
* `homePos.length == 2`
* `0 <= startrow, homerow < m`
* `0 <= startcol, homecol < n`

# Approaches
## Graph Traversal using Dijkstra's Algorithm
This approach models the grid as a weighted graph and applies a standard shortest path algorithm, like Dijkstra's, to find the minimum cost path. Each cell in the grid `(r, c)` becomes a node in the graph. An edge exists between any two adjacent cells, and its weight is the cost of moving into the destination cell. Dijkstra's algorithm is then initiated from the `startPos` node. It explores the grid by always expanding the path with the current minimum accumulated cost until it finds the shortest path to the `homePos` node.
**Time:** O(m * n * log(m * n)) - The number of nodes in the graph is `V = m * n`. Dijkstra's with a binary heap has this complexity, where each of the `V` nodes is processed, and priority queue operations take `O(log V)` time. · **Space:** O(m * n) - This space is required for the distance matrix `dist` and the priority queue, which in the worst case can store all `m*n` cells.
**Pros:** It's a general-purpose algorithm that correctly solves many shortest path problems on grids.; Guaranteed to find the optimal solution for any non-negative edge weights.
**Cons:** Highly inefficient for this specific problem due to its generality.; The time complexity `O(m*n * log(m*n))` and space complexity `O(m*n)` are prohibitive for the given constraints (`m, n <= 10^5`), leading to Time Limit Exceeded or Memory Limit Exceeded errors.; It fails to exploit the special structure of the cost function, where the cost of a move only depends on the destination cell.
### Explanation
This method provides a general solution for finding the shortest path in a weighted grid. It correctly finds the minimum cost by exploring all possible paths in an efficient manner for a generic graph. However, it does not take advantage of the problem's specific properties, making it unnecessarily complex and slow for this particular scenario.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minCostHomecomingOfARobot(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int m = rowCosts.length;
        int n = colCosts.length;
        
        int startRow = startPos[0];
        int startCol = startPos[1];
        int homeRow = homePos[0];
        int homeCol = homePos[1];

        // dist[row][col] stores the minimum cost to reach (row, col)
        long[][] dist = new long[m][n];
        for (long[] row : dist) {
            Arrays.fill(row, Long.MAX_VALUE);
        }

        // Priority queue stores {cost, row, col}
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        dist[startRow][startCol] = 0;
        pq.offer(new long[]{0, startRow, startCol});

        int[] dr = {-1, 1, 0, 0}; // up, down
        int[] dc = {0, 0, -1, 1}; // left, right

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentCost = current[0];
            int r = (int) current[1];
            int c = (int) current[2];

            if (currentCost > dist[r][c]) {
                continue;
            }

            if (r == homeRow && c == homeCol) {
                return (int) currentCost;
            }

            // Explore neighbors
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    long moveCost = (nr != r) ? rowCosts[nr] : colCosts[nc];
                    
                    if (dist[r][c] + moveCost < dist[nr][nc]) {
                        dist[nr][nc] = dist[r][c] + moveCost;
                        pq.offer(new long[]{dist[nr][nc], nr, nc});
                    }
                }
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
- **Graph Representation**: Treat the `m x n` grid as a graph where each cell `(r, c)` is a node.
- **Edge Weights**: An edge exists between any two adjacent cells. The weight of an edge is the cost to move into the destination cell. For example, moving from `(r, c)` to `(r+1, c)` has a cost of `rowCosts[r+1]`.
- **Initialization**: 
    - Create a 2D array `dist[m][n]` to store the minimum cost to reach each cell, initializing all values to infinity.
    - Set the cost to reach the starting cell `(startRow, startCol)` to 0: `dist[startRow][startCol] = 0`.
    - Use a priority queue to store tuples of `(cost, row, col)`, ordered by `cost`. Add `(0, startRow, startCol)` to the priority queue.
- **Dijkstra's Algorithm**: 
    - While the priority queue is not empty, extract the cell `(r, c)` with the minimum cost `d`.
    - If `(r, c)` is the `homePos`, the algorithm terminates, and `d` is the minimum cost.
    - For each valid neighbor `(nr, nc)` of `(r, c)`:
        - Calculate the cost to move to the neighbor (`moveCost`).
        - If `dist[r][c] + moveCost < dist[nr][nc]`, update the neighbor's distance: `dist[nr][nc] = dist[r][c] + moveCost`, and add `(dist[nr][nc], nr, nc)` to the priority queue.
- **Result**: The final cost stored in `dist[homeRow][homeCol]` is the minimum total cost.

## Greedy Approach with Direct Summation
A careful analysis of the problem reveals a crucial insight: the cost of any move depends only on the destination row or column. Since all costs are non-negative, any move that takes the robot away from its destination will only add unnecessary cost. This means the optimal path must be monotonic—the robot should only move towards the home row and home column.

Because any such monotonic path from `startPos` to `homePos` involves traversing the exact same set of intermediate rows and columns, the total cost is independent of the specific path taken. The minimum cost is simply the sum of costs for all required row movements and all required column movements.
**Time:** O(m + n) - In the worst case, the robot travels from one corner of the grid to the opposite. The row-cost loop runs at most `m-1` times, and the column-cost loop runs at most `n-1` times. · **Space:** O(1) - We only use a few variables to keep track of the coordinates and the total cost, requiring constant extra space.
**Pros:** Extremely efficient in both time and space.; Simple and easy to implement.; Directly solves the problem by leveraging its unique cost structure.
**Cons:** This approach is highly specific to this problem's cost structure and is not a general solution for other grid-based shortest path problems where path choices matter.
### Explanation
This greedy approach directly calculates the total cost without simulating the path or exploring a graph. It leverages the problem's structure to arrive at the solution with optimal efficiency.

The algorithm is a straightforward summation:
1.  Initialize `totalCost = 0`.
2.  Sum the costs of all rows the robot must pass through to get from `startRow` to `homeRow`.
3.  Sum the costs of all columns the robot must pass through to get from `startCol` to `homeCol`.
4.  The result is the sum of these two values.

```java
class Solution {
    public int minCostHomecomingOfARobot(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int r1 = startPos[0], c1 = startPos[1];
        int r2 = homePos[0], c2 = homePos[1];
        
        long cost = 0;
        
        // Sum row costs
        // Move from r1 to r2, excluding the cost of the starting row r1.
        if (r1 < r2) {
            for (int i = r1 + 1; i <= r2; i++) {
                cost += rowCosts[i];
            }
        } else {
            for (int i = r1 - 1; i >= r2; i--) {
                cost += rowCosts[i];
            }
        }
        
        // Sum column costs
        // Move from c1 to c2, excluding the cost of the starting col c1.
        if (c1 < c2) {
            for (int i = c1 + 1; i <= c2; i++) {
                cost += colCosts[i];
            }
        } else {
            for (int i = c1 - 1; i >= c2; i--) {
                cost += colCosts[i];
            }
        }
        
        return (int) cost;
    }
}
```
### Algorithm
- **Insight**: Recognize that the cost of moving depends only on the destination cell, and all costs are non-negative. This implies that any move away from the target home position (e.g., moving up when home is below) will only increase the total cost. Therefore, an optimal path must be monotonic, only moving towards the home row and column.
- **Cost Independence**: The total cost of all necessary vertical moves is independent of the horizontal moves, and vice-versa. The minimum total cost is the sum of the costs of all required row moves and all required column moves.
- **Initialization**: Start with `totalCost = 0`.
- **Calculate Row Costs**: Iterate from the starting row towards the home row. For each row `r` the robot must enter, add `rowCosts[r]` to `totalCost`. The starting row's cost is not included.
- **Calculate Column Costs**: Iterate from the starting column towards the home column. For each column `c` the robot must enter, add `colCosts[c]` to `totalCost`. The starting column's cost is not included.
- **Return**: The final `totalCost` is the minimum cost.

# Solutions
### Java

```java
class Solution {
public
  int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
    int i = startPos[0], j = startPos[1];
    int x = homePos[0], y = homePos[1];
    int ans = 0;
    if (i < x) {
      for (int k = i + 1; k <= x; ++k) {
        ans += rowCosts[k];
      }
    } else {
      for (int k = x; k < i; ++k) {
        ans += rowCosts[k];
      }
    }
    if (j < y) {
      for (int k = j + 1; k <= y; ++k) {
        ans += colCosts[k];
      }
    } else {
      for (int k = y; k < j; ++k) {
        ans += colCosts[k];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCost(vector<int> &startPos, vector<int> &homePos,
              vector<int> &rowCosts, vector<int> &colCosts) {
    int i = startPos[0], j = startPos[1];
    int x = homePos[0], y = homePos[1];
    int ans = 0;
    if (i < x) {
      ans += accumulate(rowCosts.begin() + i + 1, rowCosts.begin() + x + 1, 0);
    } else {
      ans += accumulate(rowCosts.begin() + x, rowCosts.begin() + i, 0);
    }
    if (j < y) {
      ans += accumulate(colCosts.begin() + j + 1, colCosts.begin() + y + 1, 0);
    } else {
      ans += accumulate(colCosts.begin() + y, colCosts.begin() + j, 0);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int], ) -> int: i, j = startPos x, y = homePos ans = 0 if i < x: ans += sum(rowCosts[i + 1: x + 1]) else: ans += sum(rowCosts[x: i]) if j < y: ans += sum(colCosts[j + 1: y + 1]) else: ans += sum(colCosts[y: j]) return ans

```