Minimum Cost Homecoming of a Robot in a Grid

Med

#1899Time: 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.2 companies

Patterns

Greedy

Data structures

Array

Companies

Goldman Sachs HP

Prompt

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 = [start_row, start_col] indicates that initially, a robot is at the cell (start_row, start_col). You are also given an integer array homePos where homePos = [home_row, home_col] indicates that its home is at the cell (home_row, home_col).

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:

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 <= 10⁵
0 <= rowCosts[r], colCosts[c] <= 10⁴
startPos.length == 2
homePos.length == 2
0 <= start_row, home_row < m
0 <= start_col, home_col < n

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int minCostHomecomingOfARobot(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {6        int m = rowCosts.length;7        int n = colCosts.length;8        9        int startRow = startPos[0];10        int startCol = startPos[1];11        int homeRow = homePos[0];12        int homeCol = homePos[1];13 14        // dist[row][col] stores the minimum cost to reach (row, col)15        long[][] dist = new long[m][n];16        for (long[] row : dist) {17            Arrays.fill(row, Long.MAX_VALUE);18        }19 20        // Priority queue stores {cost, row, col}21        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));22 23        dist[startRow][startCol] = 0;24        pq.offer(new long[]{0, startRow, startCol});25 26        int[] dr = {-1, 1, 0, 0}; // up, down27        int[] dc = {0, 0, -1, 1}; // left, right28 29        while (!pq.isEmpty()) {30            long[] current = pq.poll();31            long currentCost = current[0];32            int r = (int) current[1];33            int c = (int) current[2];34 35            if (currentCost > dist[r][c]) {36                continue;37            }38 39            if (r == homeRow && c == homeCol) {40                return (int) currentCost;41            }42 43            // Explore neighbors44            for (int i = 0; i < 4; i++) {45                int nr = r + dr[i];46                int nc = c + dc[i];47 48                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {49                    long moveCost = (nr != r) ? rowCosts[nr] : colCosts[nc];50                    51                    if (dist[r][c] + moveCost < dist[nr][nc]) {52                        dist[nr][nc] = dist[r][c] + moveCost;53                        pq.offer(new long[]{dist[nr][nc], nr, nc});54                    }55                }56            }57        }58        59        return -1; // Should not be reached60    }61}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Initialize totalCost = 0.
Sum the costs of all rows the robot must pass through to get from startRow to homeRow.
Sum the costs of all columns the robot must pass through to get from startCol to homeCol.
The result is the sum of these two values.

1class Solution {2    public int minCostHomecomingOfARobot(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {3        int r1 = startPos[0], c1 = startPos[1];4        int r2 = homePos[0], c2 = homePos[1];5        6        long cost = 0;7        8        // Sum row costs9        // Move from r1 to r2, excluding the cost of the starting row r1.10        if (r1 < r2) {11            for (int i = r1 + 1; i <= r2; i++) {12                cost += rowCosts[i];13            }14        } else {15            for (int i = r1 - 1; i >= r2; i--) {16                cost += rowCosts[i];17            }18        }19        20        // Sum column costs21        // Move from c1 to c2, excluding the cost of the starting col c1.22        if (c1 < c2) {23            for (int i = c1 + 1; i <= c2; i++) {24                cost += colCosts[i];25            }26        } else {27            for (int i = c1 - 1; i >= c2; i--) {28                cost += colCosts[i];29            }30        }31        32        return (int) cost;33    }34}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {4    int i = startPos[0], j = startPos[1];5    int x = homePos[0], y = homePos[1];6    int ans = 0;7    if (i < x) {8      for (int k = i + 1; k <= x; ++k) {9        ans += rowCosts[k];10      }11    } else {12      for (int k = x; k < i; ++k) {13        ans += rowCosts[k];14      }15    }16    if (j < y) {17      for (int k = j + 1; k <= y; ++k) {18        ans += colCosts[k];19      }20    } else {21      for (int k = y; k < j; ++k) {22        ans += colCosts[k];23      }24    }25    return ans;26  }27}

1class Solution {2public:3  int minCost(vector<int> &startPos, vector<int> &homePos,4              vector<int> &rowCosts, vector<int> &colCosts) {5    int i = startPos[0], j = startPos[1];6    int x = homePos[0], y = homePos[1];7    int ans = 0;8    if (i < x) {9      ans += accumulate(rowCosts.begin() + i + 1, rowCosts.begin() + x + 1, 0);10    } else {11      ans += accumulate(rowCosts.begin() + x, rowCosts.begin() + i, 0);12    }13    if (j < y) {14      ans += accumulate(colCosts.begin() + j + 1, colCosts.begin() + y + 1, 0);15    } else {16      ans += accumulate(colCosts.begin() + y, colCosts.begin() + j, 0);17    }18    return ans;19  }20};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem