3418. Maximum Amount of Money Robot Can Earn LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3418. Maximum Amount of Money Robot Can Earn LeetCode Solution with the best time and space complexity. The solution to Maximum Amount of Money Robot Can Earn problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Amount of Money Robot Can Earn solution in C++
Maximum Amount of Money Robot Can Earn solution in Java
Maximum Amount of Money Robot Can Earn solution in Python
Additional Resources

3418. Maximum Amount of Money Robot Can Earn LeetCode Solution image

Problem Statement of Maximum Amount of Money Robot Can Earn

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:

Start at (0, 0) with 0 coins (total coins = 0).
Move to (0, 1), gaining 1 coin (total coins = 0 + 1 = 1).
Move to (1, 1), where there’s a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1).
Move to (1, 2), gaining 3 coins (total coins = 1 + 3 = 4).
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:

Start at (0, 0) with 10 coins (total coins = 10).
Move to (0, 1), gaining 10 coins (total coins = 10 + 10 = 20).
Move to (0, 2), gaining another 10 coins (total coins = 20 + 10 = 30).
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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

3418. Maximum Amount of Money Robot Can Earn LeetCode Solution in C++

class Solution {
 public:
  int maximumAmount(vector<vector<int>>& coins) {
    const int m = coins.size();
    const int n = coins[0].size();
    // dp[i][j][k] := the maximum profit at position (i, j) with k remaining
    // neutralizations
    vector<vector<vector<int>>> dp(
        m, vector<vector<int>>(n, vector<int>(4, -INT_MAX / 2)));

    // Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0];
    if (coins[0][0] < 0)
      dp[0][0][1] = 0;  // Neutralize the robber.

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int k = 0; k < 3; ++k) {
          if (i > 0)
            dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k] + coins[i][j],
                               dp[i - 1][j][k + 1]});
          if (j > 0)
            dp[i][j][k] = max({dp[i][j][k], dp[i][j - 1][k] + coins[i][j],
                               dp[i][j - 1][k + 1]});
        }

    return ranges::max(dp[m - 1][n - 1]);
  }
};
/* code provided by PROGIEZ */

3418. Maximum Amount of Money Robot Can Earn LeetCode Solution in Java

class Solution {
  public int maximumAmount(int[][] coins) {
    final int m = coins.length;
    final int n = coins[0].length;
    // dp[i][j][k] := the maximum profit at position (i, j) with k remaining neutralizations
    int[][][] dp = new int[m][n][4];
    Arrays.stream(dp).forEach(
        A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, Integer.MIN_VALUE / 2)));

    // Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0];
    if (coins[0][0] < 0)
      dp[0][0][1] = 0; // Neutralize the robber.

    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < 3; k++) {
          if (i > 0)
            dp[i][j][k] =
                Math.max(dp[i][j][k], Math.max(dp[i - 1][j][k] + coins[i][j], dp[i - 1][j][k + 1]));
          if (j > 0)
            dp[i][j][k] =
                Math.max(dp[i][j][k], Math.max(dp[i][j - 1][k] + coins[i][j], dp[i][j - 1][k + 1]));
        }

    return Arrays.stream(dp[m - 1][n - 1]).max().getAsInt();
  }
}
// code provided by PROGIEZ

3418. Maximum Amount of Money Robot Can Earn LeetCode Solution in Python

class Solution:
  def maximumAmount(self, coins: list[list[int]]) -> int:
    m = len(coins)
    n = len(coins[0])
    # dp[i][j][k] := the maximum profit at position (i, j) with k remaining
    # neutralizations
    dp = [[[-math.inf] * 4 for _ in range(n)] for _ in range(m)]

    # Base case: the robot starts at the top-left corner.
    dp[0][0][2] = coins[0][0]
    if coins[0][0] < 0:
      dp[0][0][1] = 0  # Neutralize the robber.

    for i in range(m):
      for j in range(n):
        for k in range(3):  # for each number of remaining neutralizations
          if i > 0:
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i - 1][j][k] + coins[i][j],
                              dp[i - 1][j][k + 1])
          if j > 0:
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i][j - 1][k] + coins[i][j],
                              dp[i][j - 1][k + 1])

    return max(dp[-1][-1])
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents