Maximize coins that can be collected by moving on given coordinates

19 June 2025

0

Given an array arr[][] of size N*3 where i^th element represents that at time arr[i][0] secs, arr[i][2] coins appear at coordinate arr[i][1]. A player starts on coordinate 0 at time 0sec and can move from one coordinate to any adjacent coordinates in 1 sec and also the player can choose to stay on the same coordinate for the next second. The task is to find how many coins can the player collect.

Note: If a coin appears at time X, it disappears at time X+1.

Examples:

Input: arr[][3] = {{1, 0, 100}, {3, 3, 10}, {5, 4, 1}}
Output: 101
Explanation: The optimal strategy for players is:
At T = 0, wait at coordinate 0 to catch coins at T = 1
At T = 1, collect 100 coins
At T = 2, moves to coordinate 1
At T = 3 moves to coordinate 2
At T = 4 moves to coordinate 3
At T = 5, move to coordinate 4 and collect 1 coin that has just appeared.
Total coins = 100 + 1 = 101

Input: arr[][3] = {{1, 4, 1}, {2, 4, 1}, {3, 4, 1}}
Output: 0

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using recursive approach.

Time Complexity: O(3^N)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the following idea:

Dynamic programming along with hashmap can be used to solve this problem. dp[i][j] = X, represents the maximum coins collected at the time i with coordinate j

it can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by store the value of a state and whenever the function is called, return the stored value without computing again.

Follow the steps below to solve the problem:

Create a hashmap and map time arr[i][0] and coordinate arr[i][1] to coins arr[i][2].
Create a recursive function that takes two parameters i representing the current time and j representing the current coordinate.
Call the recursive function thrice first for moving backward, second for moving ahead, and third for staying on the same coordinate.
Create a 2d array of dp[100001][5] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Dp table initialized with - 1
int dp[100001][5];
 
// Recursive function to count maximum coins
// player can collect
int recur(int i, int j, vector<vector<int> >& HashMap)
{
    // Base case
    if (i == 100001) {
        return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
        return dp[i][j];
 
    int ans = 0;
 
    // Calling recursive function for moving
    // to Right coordinate
    if (j != 4)
        ans = max(ans, recur(i + 1, j + 1, HashMap)
                           + HashMap[i + 1][j + 1]);
 
    // Calling recursive function for
    // staying on same position
    ans = max(ans,
              recur(i + 1, j, HashMap) + HashMap[i + 1][j]);
 
    // Calling recursive function for
    // moving to Left coordinate
    if (j != 0)
        ans = max(ans, recur(i + 1, j - 1, HashMap)
                           + HashMap[i + 1][j - 1]);
 
    // Save and return dp value
    return dp[i][j] = ans;
}
 
// Function to calculate maximum coins
// that player can collect
int findMaximumScore(int arr[][3], int N)
{
    // Filling dp table with -1
    memset(dp, -1, sizeof(dp));
 
    // Initializing hashmap with value 0
    vector<vector<int> > HashMap(100010, vector<int>(6, 0));
 
    // Filling hashmap
    for (int i = 0; i < N; i++) {
 
        // At time arr[i][0] and at coordinate
        // arr[i][1] exactly arr[i][2] coins appear
        HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
    }
 
    return recur(0, 0, HashMap);
}
 
// Driver Code
int main()
{
    // Test Case 1
    int arr[][3]
        = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findMaximumScore(arr, N) << endl;
 
    // Test Case 2
    int arr1[][3]
        = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
    int N1 = sizeof(arr1) / sizeof(arr1[0]);
 
    // Function Call
    cout << findMaximumScore(arr1, N1) << endl;
 
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Dp table initialized with - 1
    static int[][] dp = new int[1001][5];
 
    // Recursive function to count maximum coins
    // player can collect
    static int recur(int i, int j, int[][] HashMap)
    {
        // Base case
        if (i == 1001) {
            return 0;
        }
 
        // If answer for current state is already
        // calculated then just return dp[i][j]
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
 
        int ans = 0;
 
        // Calling recursive function for moving
        // to Right coordinate
        if (j != 4) {
            ans = Math.max(ans,
                           recur(i + 1, j + 1, HashMap)
                               + HashMap[i + 1][j + 1]);
        }
 
        // Calling recursive function for
        // staying on same position
        ans = Math.max(ans, recur(i + 1, j, HashMap)
                                + HashMap[i + 1][j]);
 
        // Calling recursive function for
        // moving to Left coordinate
        if (j != 0) {
            ans = Math.max(ans,
                           recur(i + 1, j - 1, HashMap)
                               + HashMap[i + 1][j - 1]);
        }
 
        // Save and return dp value
        return dp[i][j] = ans;
    }
 
    // Function to calculate maximum coins
    // that player can collect
    static int findMaximumScore(int[][] arr, int N)
    {
        // Filling dp table with -1
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
 
        // Initializing hashmap with value 0
        int[][] HashMap = new int[100010][6];
 
        // Filling hashmap
        for (int i = 0; i < N; i++) {
 
            // At time arr[i][0] and at coordinate
            // arr[i][1] exactly arr[i][2] coins appear
            HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
        }
 
        return recur(0, 0, HashMap);
    }
 
    public static void main(String[] args)
    {
        // Test Case 1
        int[][] arr
            = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
        int N = arr.length;
 
        // Function Call
        System.out.println(findMaximumScore(arr, N));
 
        // Test Case 2
        int[][] arr1
            = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
        int N1 = arr1.length;
 
        // Function Call
        System.out.println(findMaximumScore(arr1, N1));
    }
}
 
// This code is contributed by lokesh.

Python3

# Python code to implement the approach
 
# Dp table initialized with - 1
dp=[[-1 for i in range(5)] for j in range(101)]
 
# Recursive function to count maximum coins
# player can collect
def recur(i,j,HashMap):
    # Base case
    if(i==101):
        return 0
     
    # If answer for current state is already
    # calculated then just return dp[i][j]
    if(dp[i][j]!=-1):
        return dp[i][j]
         
    ans=0
     
    # Calling recursive function for moving
    # to Right coordinate
    if(j!=4):
        ans=max(ans,recur(i + 1, j + 1, HashMap) + HashMap[i + 1][j + 1])
     
    # Calling recursive function for
    # staying on same position
    ans = max(ans,recur(i + 1, j, HashMap) + HashMap[i + 1][j])
     
    # Calling recursive function for
    # moving to Left coordinate
    if(j!=0):
        ans = max(ans,recur(i + 1, j - 1, HashMap) + HashMap[i + 1][j - 1])
     
    # Save and return dp value
    dp[i][j]=ans
    return dp[i][j]
     
# Function to calculate maximum coins
# that player can collect
def findMaximumScore(arr,N):
    # Filling dp table with -1
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            dp[i][j]=-1
     
    # Initializing hashmap with value 0
    HashMap=[[0 for i in range(6)] for j in range(100010)]
     
    # Filling hashmap
    for i in range(N):
        # At time arr[i][0] and at coordinate
        # arr[i][1] exactly arr[i][2] coins appear
        HashMap[arr[i][0]][arr[i][1]] = arr[i][2]
     
    return recur(0,0,HashMap)
     
# Driver Code
 
# Test Case 1
arr=[[1, 0, 100],[3, 3, 10],[5, 4, 1]]
N=len(arr)
 
# Function Call
print(findMaximumScore(arr, N))
 
 
# Test Case 2
arr1=[[1, 4, 1],[2, 4, 1],[3, 4, 1]]
N1=len(arr1)
 
# Function Call
print(findMaximumScore(arr1, N1))
 
# This code is contributed by Pushpesh Raj.

C#

// C# code to implement the approach
 
using System;
using System.Linq;
 
public class GFG{
   
      // Dp table initialized with - 1
    static int[,] dp = new int[1001, 5];
 
    // Recursive function to count maximum coins
    // player can collect
    static int Recur(int i, int j, int[,] hashMap)
    {
        // Base case
        if (i == 1001)
        {
            return 0;
        }
 
        // If answer for current state is already
        // calculated then just return dp[i][j]
        if (dp[i, j] != -1)
        {
            return dp[i, j];
        }
 
        int ans = 0;
 
        // Calling recursive function for moving
        // to Right coordinate
        if (j != 4)
        {
            ans = Math.Max(ans,
                           Recur(i + 1, j + 1, hashMap)
                               + hashMap[i + 1, j + 1]);
        }
 
        // Calling recursive function for
        // staying on same position
        ans = Math.Max(ans, Recur(i + 1, j, hashMap)
                                + hashMap[i + 1, j]);
 
        // Calling recursive function for
        // moving to Left coordinate
        if (j != 0)
        {
            ans = Math.Max(ans,
                           Recur(i + 1, j - 1, hashMap)
                               + hashMap[i + 1, j - 1]);
        }
 
        // Save and return dp value
        return dp[i, j] = ans;
    }
 
    // Function to calculate maximum coins
    // that player can collect
    static int FindMaximumScore(int[,] arr, int N)
    {
        // Filling dp table with -1
        for (int i = 0; i < dp.GetLength(0); i++)
        {
            for (int j = 0; j < dp.GetLength(1); j++)
            {
                dp[i, j] = -1;
            }
        }
 
        // Initializing hashmap with value 0
        int[,] hashMap = new int[100010, 6];
 
        // Filling hashmap
        for (int i = 0; i < N; i++)
        {
            // At time arr[i][0] and at coordinate
            // arr[i][1] exactly arr[i][2] coins appear
            hashMap[arr[i, 0], arr[i, 1]] = arr[i, 2];
        }
 
        return Recur(0, 0, hashMap);
    }
 
    static public void Main (){
 
        // Code
          // Test Case 1
        int[, ] arr
            = { { 1, 0, 100 }, { 3, 3, 10 }, { 5, 4, 1 } };
        int N = arr.GetLength(0);
 
        // Function Call
        Console.WriteLine(FindMaximumScore(arr, N));
 
        // Test Case 2
        int[, ] arr1
            = { { 1, 4, 1 }, { 2, 4, 1 }, { 3, 4, 1 } };
        int N1 = arr1.GetLength(0);
 
        // Function Call
        Console.WriteLine(FindMaximumScore(arr1, N1));
    }
}
 
// This code is contributed by lokeshmvs21.

Javascript

  // JS code to implement the approach
 
  // Dp table initialized with - 1
  let dp = new Array(1001)
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(5);
  }
 
  // Recursive function to count maximum coins
  // player can collect
  function recur(i, j, HashMap) {
    // Base case
    if (i == 1001) {
      return 0;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j] != -1)
      return dp[i][j];
 
    let ans = 0;
 
    // Calling recursive function for moving
    // to Right coordinate
    if (j != 4)
      ans = Math.max(ans, recur(i + 1, j + 1, HashMap)
        + HashMap[i + 1][j + 1]);
 
    // Calling recursive function for
    // staying on same position
    ans = Math.max(ans,
      recur(i + 1, j, HashMap) + HashMap[i + 1][j]);
 
    // Calling recursive function for
    // moving to Left coordinate
    if (j != 0)
      ans = Math.max(ans, recur(i + 1, j - 1, HashMap)
        + HashMap[i + 1][j - 1]);
 
    // Save and return dp value
    return dp[i][j] = ans;
  }
 
  // Function to calculate maximum coins
  // that player can collect
  function findMaximumScore(arr, N) {
    // Filling dp table with -1
    for (let i = 0; i < dp.length; i++) {
      for (let j = 0; j < dp[i].length; j++) {
        dp[i][j] = -1;
      }
    }
    // Initializing hashmap with value 0
    let HashMap = new Array(100010);
    for (let i = 0; i < HashMap.length; i++) {
      HashMap[i] = new Array(6).fill(0)
    }
 
 
    // Filling hashmap
    for (let i = 0; i < N; i++) {
 
      // At time arr[i][0] and at coordinate
      // arr[i][1] exactly arr[i][2] coins appear
      HashMap[arr[i][0]][arr[i][1]] = arr[i][2];
    }
 
    return recur(0, 0, HashMap);
  }
 
  // Driver Code
 
  // Test Case 1
  let arr
    = [[1, 0, 100], [3, 3, 10], [5, 4, 1]];
  let N = arr.length;
 
  // Function Call
  console.log(findMaximumScore(arr, N) + "<br>");
 
  // Test Case 2
  let arr1
    = [[1, 4, 1], [2, 4, 1], [3, 4, 1]];
  let N1 = arr1.length;
 
  // Function Call
  console.log(findMaximumScore(arr1, N1) + "<br>");
 
 
// This code is contributed by Potta Lokesh

Output

101
0

Time Complexity: O(N * M) where M denotes the maximum amount of time present in array.
Auxiliary Space: O(N * M)

Related Articles:

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Maximize coins that can be collected by moving on given coordinates

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US