Coin Collection

A new online game is gaining popularity. It is based on a matrix of size 2 x n (2 rows and n columns) where a cell formed by the ith row and jth column initially contains coins[i][j] number of coins. The number of coins in each cell is increasing over time. More precisely, at some time k, the number of coins in the cell(i, j) is k * coins[i][j].

A player has to start from the point (0, 0) at time t = 0 and in a single unit of time is allowed to move to any neighboring cell. A player collects all the coins in the cell they visit and each cell must be visited exactly once. Given the initial number of coins in the matrix, coins, find the maximum possible number of coins that a player can collect.

Example:

Suppose n = 4, coins = [[1, 4, 3, 2], [2, 1, 3, 2]]. The optimal path is described below:

Time 0, Cell (0, 0), Coins: 0 Time 1, Cell (1, 0), Coins: 1 * 2 = 2 Time 2, Cell (1, 1), Coins: 2 * 1 = 2 Time 3, Cell (1, 2), Coins: 3 * 3 = 9 Time 4, Cell (1, 3), Coins: 4 * 2 = 8 Time 5, Cell (0, 3), Coins: 5 * 2 = 10 Time 6, Cell (0, 2), Coins: 6 * 3 = 18

Function Description

Complete the function getMaxCoins that has the parameter: int coins[n][2]: the initial number of coins in the matrix.

Returns: long: the maximum total number of coins that can be collected.

Constraints

1 <= n <= 10^5 1 <= coins[i][j] <= 10^5

Here is one approach to solve this problem of finding the maximum coins a player can collect from a 2 x n matrix where the number of coins in each cell increases over time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import heapq

def getMaxCoins(coins):
  # Create min heap to store next cell options ordered by current coins  
  minHeap = []
  heapq.heappush(minHeap, (0, 0, 0)) # (coins, row, col)
  
  maxCoins = 0
  seen = set([(0,0)])
  
  while minHeap:
    coins, row, col = heapq.heappop(minHeap)

    # Add coins collected at this cell
    maxCoins += coins

    # Check neighboring cells
    for drow, dcol in [(0,1),(0,-1),(1,0),(-1,0)]:
      nrow = row + drow
      ncol = col + dcol

      # Check if in bounds and not visited
      if 0 <= nrow < 2 and 0 <= ncol < len(coins[0]) and (nrow, ncol) not in seen:
        seen.add((nrow, ncol))
        heapq.heappush(minHeap, (ncol*coins[nrow][ncol], nrow, ncol))

  return maxCoins

The key ideas are:

  • Use a min heap to get next cell with minimum coins
  • Keep accumulating coins collected at each cell
  • Check and enqueue unvisited neighboring cells
  • Return total coins after full traversal

This allows always moving to the next cell with lowest coins but highest rate of increase, optimizing total coins collected.