Minimum cost homecoming of a robot in a grid

Array Greedy

51.6% acceptance

Feb 25, 2026

744

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

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(start_pos: Vec<i32>, home_pos: Vec<i32>, row_costs: Vec<i32>, col_costs: Vec<i32>) -> i32 {
    let sr = start_pos[0] as usize;
    let sc = start_pos[1] as usize;
    let hr = home_pos[0] as usize;
    let hc = home_pos[1] as usize;

    // Any optimal path must traverse from sr to hr (passing through each row once)
    // and from sc to hc (passing through each column once)
    // Cost = sum of row_costs for rows traversed (excluding start row) + sum of col_costs for cols traversed (excluding start col)

    let row_cost: i32 = if sr <= hr {
      row_costs[(sr + 1)..=hr].iter().sum()
    } else {
      row_costs[hr..sr].iter().sum()
    };

    let col_cost: i32 = if sc <= hc {
      col_costs[(sc + 1)..=hc].iter().sum()
    } else {
      col_costs[hc..sc].iter().sum()
    };

    row_cost + col_cost
  }
}