Skip to main content
Talentd

Minimum Cost Homecoming of a Robot in a Grid - Solution & Explanation

MediumArrayGreedy9 min readAsked at: Microsoft, Goldman Sachs, HP
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Direct Calculation Based on Required Movements

This approach focuses on directly calculating the cost incurred for moving from startPos to homePos by traversing row-wise and column-wise. The movement can be made in any order, but the costs remain constant as they depend only on the final positions along each dimension.

This solution iterates over the necessary rows and columns to compute the cost, summing up appropriately based on the direction. If starting less than the home position, it sums forward through the costs, otherwise it sums backward.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

Time Complexity: O(m + n), where m is the number of row costs accessed and n is the number of column costs accessed.
Space Complexity: O(1), as no additional space is used.

Try this approach in the editor →

Approach 2: Directional Iterative Traversal

In this approach, the robot traverses from the start to home in the most straightforward directional steps iteratively, modifying its row or column index each step. This is practically moving cell-by-cell and adding up individual move costs.

The Java function iteratively moves the robot one step at a time towards home, adjusting both coordinates in a loop and accumulating the respective row or column costs, reflecting a step-by-step simulation of the task.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(m + n), considering a worst-case traversal covering all intermediate cells.
Space Complexity: O(1), with only a few integer variables utilized in computation.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Calculation Based on Required Movements

Time Complexity: O(m + n), where m is the number of row costs accessed and n is the number of column costs accessed.
Space Complexity: O(1), as no additional space is used.

Directional Iterative Traversal

Time Complexity: O(m + n), considering a worst-case traversal covering all intermediate cells.
Space Complexity: O(1), with only a few integer variables utilized in computation.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Grid Traversal with BFSO(m*n)O(m*n)Conceptual brute-force when modeling the grid as a graph or verifying correctness.
Directional Iterative TraversalO(|r2-r1| + |c2-c1|)O(1)When you want a clear step-by-step simulation of the robot's movement.
Direct Greedy Cost CalculationO(|r2-r1| + |c2-c1|)O(1)Best approach for interviews and production due to simplicity and optimal complexity.

Video Solution

Leetcode Biweekly Contest 66 | PROBLEM 2085 , 2086, 2087 | LEETCODE | CODE EXPLAINER • code Explainer • 1,103 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimum Cost Homecoming of a Robot in a Grid easy or hard?
The problem is rated Medium because the key insight is recognizing that the order of moves does not affect the final cost. Once that observation is made, the implementation becomes a straightforward greedy accumulation.
Minimum Cost Homecoming of a Robot in a Grid Python/Java solution
A typical implementation loops from the start row toward the target row adding rowCosts, then loops across columns adding colCosts. The same logic works in Python, Java, C++, or JavaScript because it only requires simple array indexing and iteration.
How to solve Minimum Cost Homecoming of a Robot in a Grid in O(n)?
Move from the start row toward the home row while adding the corresponding rowCosts for each entered row, then move toward the home column while adding colCosts. The number of operations equals the vertical distance plus the horizontal distance, producing O(|r2-r1| + |c2-c1|) complexity.
What is the best approach for Minimum Cost Homecoming of a Robot in a Grid?
The greedy cost accumulation approach is the most efficient solution. Instead of exploring paths, sum the row costs between the start row and home row and the column costs between the start column and home column. This works because the order of vertical and horizontal moves does not change the total cost.
Is Minimum Cost Homecoming of a Robot in a Grid asked at Google/Amazon/Meta?
Grid traversal and cost-accumulation problems appear frequently in interviews at companies like Amazon and Google. This problem specifically tests recognition of greedy patterns and the ability to simplify pathfinding problems using problem constraints.
What data structure is used in Minimum Cost Homecoming of a Robot in a Grid?
The solution primarily uses arrays for rowCosts and colCosts. The algorithm iterates through these arrays while moving toward the destination, applying a greedy accumulation of costs.
What is the time complexity of Minimum Cost Homecoming of a Robot in a Grid?
The optimal solution runs in O(|r2-r1| + |c2-c1|) time because you only iterate through the rows and columns the robot must enter. Space complexity is O(1) since only a few variables are used to accumulate the total cost.

Ready to solve this problem?

Practice Minimum Cost Homecoming of a Robot in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bomb Enemy

Next

Check if There is a Path With Equal Number of 0's And 1's