Taro Logo

Maximum Amount of Money Robot Can Earn

Medium
Asked by:
Profile picture
14 views
Topics:
ArraysDynamic Programming

You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time.

The grid contains a value coins[i][j] in each cell:

  • If coins[i][j] >= 0, the robot gains that many coins.
  • If coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value of coins[i][j] coins.

The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells.

Note: The robot's total coins can be negative.

Return the maximum profit the robot can gain on the route.

Example 1:

Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]

Output: 8

Explanation:

An optimal path for maximum coins is:

  1. Start at (0, 0) with 0 coins (total coins = 0).
  2. Move to (0, 1), gaining 1 coin (total coins = 0 + 1 = 1).
  3. Move to (1, 1), where there's a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1).
  4. Move to (1, 2), gaining 3 coins (total coins = 1 + 3 = 4).
  5. Move to (2, 2), gaining 4 coins (total coins = 4 + 4 = 8).

Example 2:

Input: coins = [[10,10,10],[10,10,10]]

Output: 40

Explanation:

An optimal path for maximum coins is:

  1. Start at (0, 0) with 10 coins (total coins = 10).
  2. Move to (0, 1), gaining 10 coins (total coins = 10 + 10 = 20).
  3. Move to (0, 2), gaining another 10 coins (total coins = 20 + 10 = 30).
  4. Move to (1, 2), gaining the final 10 coins (total coins = 30 + 10 = 40).

Constraints:

  • m == coins.length
  • n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is the street a single line of rooms, so only adjacent rooms set off the alarm?
  2. Can the robot skip a room and still take a later room?
  3. May the collected total be zero when every room is empty?
  4. Does taking a room that holds zero still block its two neighbors?
  5. What is returned when the street contains no rooms?

Brute Force Solution

Approach

Every room offers two choices, and both are explored from scratch. Taking the room adds its money and restarts the decision two rooms ahead, while skipping it restarts at the next room. The larger result is kept, and the first decision begins at the opening room.

Here's how the algorithm would work step-by-step:

  1. Return zero when the current position has moved past the last room.
  2. Add the current room's money to the best total that starts two rooms ahead.
  3. Separately compute the best total that starts at the very next room.
  4. Keep the larger of those two totals for the current position.
  5. Repeat that choice at every later room the chosen branch reaches.
  6. Start the first decision at the opening room and return its total.

Code Implementation

def max_money_brute_force(rooms):
    def find_max_from_index(current_index):
        # Base case: if we've gone past the last room, no more money can be collected.
        if current_index >= len(rooms):
            return 0

        # Explore the first choice: collect money from the current room and skip the next.
        money_if_taken = rooms[current_index] + find_max_from_index(current_index + 2)

        # Explore the second choice: skip the current room and decide on the next one.
        money_if_skipped = find_max_from_index(current_index + 1)

        # The optimal choice for this subproblem is the maximum of the two branching paths.
        return max(money_if_taken, money_if_skipped)

    # The process starts from the very first room (index 0) to find the overall maximum.
    return find_max_from_index(0)

Big(O) Analysis

Time Complexity
O(2^n) – Each room creates two branches, one that takes it and one that skips it. The taken branch jumps ahead by two rooms and the skipped branch jumps ahead by one, so the call tree still covers an exponential number of routes. Nothing is stored, so overlapping suffixes of the street are solved again every time they appear. The number of calls is proportional to the number of ways to walk down a line of n rooms with those two jumps, which is O(2^n). A single call does only a constant amount of arithmetic besides the two recursive calls.
Space Complexity
O(n) – The only extra memory is the chain of recursive calls. Each call waits for a room farther down the street, so the deepest chain has one frame per room and is proportional to n. No cache of earlier answers is allocated. The input amounts are read in place. The extra memory is therefore O(n).

Optimal Solution

Approach

The fast version solves the street from the last room backward, keeping only two running totals. One total is the best money available starting at the next room, and the other is the best money available starting two rooms ahead. Each room chooses the larger of taking its money plus the farther total, or keeping the nearer total, and those two totals then slide one room backward.

Here's how the algorithm would work step-by-step:

  1. Return zero for an empty street, and return the only amount when a single room is present.
  2. Seed the nearer total with the last room's money.
  3. Seed the farther total with zero, because nothing exists beyond the last room.
  4. Move from the second-to-last room back to the first room.
  5. At each room, choose the larger of its money plus the farther total, or the nearer total.
  6. Slide the two totals one room backward before looking at the previous room.
  7. Return the nearer total once the first room has been decided.

Code Implementation

def max_money_robot_can_earn(money_in_each_room):
    number_of_rooms = len(money_in_each_room)

    if number_of_rooms == 0:
        return 0
    if number_of_rooms == 1:
        return money_in_each_room[0]

    # This tracks the max money earnable from the next room onwards.
    max_money_from_next_room = money_in_each_room[number_of_rooms - 1]

    # This tracks the max money earnable from two rooms ahead onwards.
    max_money_from_two_rooms_ahead = 0

    # Iterate backwards from the second-to-last room to solve for each subproblem.
    for current_room_index in range(number_of_rooms - 2, -1, -1):
        # For each room, decide whether to rob it or skip it based on maximum future earnings.
        current_max_earnings = max(
            money_in_each_room[current_room_index] + max_money_from_two_rooms_ahead, 
            max_money_from_next_room
        )

        max_money_from_two_rooms_ahead = max_money_from_next_room
        max_money_from_next_room = current_max_earnings

    return max_money_from_next_room

Big(O) Analysis

Time Complexity
O(n) – The street is scanned once from the end toward the start. Each room performs a fixed amount of arithmetic and then replaces the two saved totals. There is no branching and no nested scan of the remaining rooms. The special cases of an empty street and a single room finish in constant time. Across n rooms the total work is O(n).
Space Complexity
O(1) – Only two running totals and the index of the current room are stored. Those values are overwritten as the scan moves, so their count does not grow with the street. The amounts themselves stay in the input. No recursion and no table of subproblems are required. The extra memory is O(1).

Edge Cases

The street has no rooms
How to Handle:
There is nothing to collect, so the result is zero.
The street has a single room
How to Handle:
That room is taken, because it has no neighbor that could set off the alarm.
The street has exactly two rooms
How to Handle:
Only the larger amount is taken, because the two rooms are adjacent.
Every room holds zero
How to Handle:
Every choice totals zero, so the result is zero.
A rich room sits between poor rooms
How to Handle:
The rich room is taken and both of its neighbors are left behind.
Large and small amounts alternate
How to Handle:
Each room keeps the better of taking it plus the best total from two rooms ahead, or skipping ahead by one room.