Minimum Cost Homecoming of a Robot in a Grid — LeetCode 2087 Python Solution

The 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).

Example

Input

startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]

Output

18

Explanation

One optimal path is that:

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems