We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Homecoming of a Robot in a Grid

Number: 2192

Difficulty: Medium

Paid? No

Companies: Goldman Sachs

Problem Description

Given a grid of size m x n with costs associated to moving into rows and columns, the robot starts at a given position and must reach its home position. Moving vertically (up or down) incurs a cost based on the destination row (from rowCosts) and moving horizontally (left or right) incurs a cost based on the destination column (from colCosts). The task is to determine the minimum total cost required for the robot to reach its home.

Key Insights

  • The order of moves does not affect the total cost because the costs are independent and additive.
  • For vertical moves, sum the rowCosts for every row the robot enters, excluding its starting row.
  • For horizontal moves, sum the colCosts for every column the robot enters, excluding its starting column.
  • The direction (increasing or decreasing index) determines which segment of the cost array to sum.
  • The problem has a straightforward O(distance) solution (where distance is the number of rows/cols moved) which is efficient given the constraints.

Space and Time Complexity

Time Complexity: O(|homeRow - startRow| + |homeCol - startCol|) Space Complexity: O(1)

Solution

We calculate the cost in two separate parts: vertical and horizontal.

  1. To compute the vertical cost:
    • If the destination row is greater than the start row, iterate from startRow+1 to homeRow and add the corresponding rowCosts.
    • Otherwise if the destination row is less than the start row, iterate backwards from startRow-1 to homeRow and add the corresponding rowCosts.
  2. To compute the horizontal cost:
    • If the destination column is greater than the start column, iterate from startCol+1 to homeCol and add the corresponding colCosts.
    • Otherwise if the destination column is less than the start column, iterate backwards from startCol-1 to homeCol and add the corresponding colCosts.
  3. The total minimum cost is the sum of vertical and horizontal costs.

The solution leverages simple iteration and basic arithmetic without the need for complex data structures.

Code Solutions

# Python solution for Minimum Cost Homecoming of a Robot in a Grid

def minCost(startPos, homePos, rowCosts, colCosts):
    start_row, start_col = startPos
    home_row, home_col = homePos
    total_cost = 0
    
    # Compute vertical move cost
    if home_row > start_row:  # moving downwards
        for r in range(start_row + 1, home_row + 1):
            total_cost += rowCosts[r]  # cost to move into this row
    else:  # moving upwards
        for r in range(start_row - 1, home_row - 1, -1):
            total_cost += rowCosts[r]  # cost to move into this row
    
    # Compute horizontal move cost
    if home_col > start_col:  # moving right
        for c in range(start_col + 1, home_col + 1):
            total_cost += colCosts[c]  # cost to move into this column
    else:  # moving left
        for c in range(start_col - 1, home_col - 1, -1):
            total_cost += colCosts[c]  # cost to move into this column
    
    return total_cost

# Example usage:
if __name__ == "__main__":
    print(minCost([1, 0], [2, 3], [5, 4, 3], [8, 2, 6, 7]))  # Expected output: 18
← Back to All Questions