Scale Engineer

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 SachsHP

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 = [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:

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

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.

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    }}

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.

Solutions

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;  }}

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 →

Next problem