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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Coins From K Consecutive Bags

Difficulty: Medium

Problem Description

You are given a 2D array coins, where coins[i] = [l_i, r_i, c_i] denotes that every bag from l_i to r_i contains c_i coins. The segments that coins contain are non-overlapping. You are also given an integer k. Return the maximum amount of coins you can obtain by collecting k consecutive bags.

Key Insights

  • The problem involves selecting k consecutive bags from potentially large ranges.
  • We need to account for the overlap of bag ranges and how many coins they contain.
  • The non-overlapping property of the segments allows for efficient calculations.
  • A sliding window approach can be beneficial to keep track of the sums of coins in a window of size k.

Space and Time Complexity

Time Complexity: O(n + k) where n is the number of segments in coins and k is the maximum range. Space Complexity: O(1) for the sliding window approach as we only need a few variables to keep track of sums.

Solution

To solve the problem, we can utilize a combination of a frequency map and a sliding window technique. We will first create a mapping of the coin counts in bags based on their positions. Then, we will iterate through the mapped values, maintaining a running sum of coins in a window of size k. This allows us to efficiently calculate the maximum coins obtainable in any k consecutive bags.

Code Solutions

def maxCoins(coins, k):
    # Create a map to hold the coin values at each position
    coin_map = {}
    
    # Populate the coin_map with the values from the coins array
    for l, r, c in coins:
        for i in range(l, r + 1):
            if i in coin_map:
                coin_map[i] += c
            else:
                coin_map[i] = c
                
    # Now, we will use a sliding window to find the max sum in k consecutive bags
    max_coins = 0
    current_sum = 0
    start = min(coin_map.keys())
    
    # Iterate through each position in the coin_map
    for i in range(start, start + k):
        current_sum += coin_map.get(i, 0)
    
    max_coins = current_sum
    
    # Slide the window across the positions
    for i in range(start + k, max(coin_map.keys()) + 1):
        current_sum += coin_map.get(i, 0) - coin_map.get(i - k, 0)
        max_coins = max(max_coins, current_sum)
    
    return max_coins
← Back to All Questions