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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Coins From K Consecutive Bags

Number: 3715

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

You are given an infinite number line of bags (one per coordinate) where some bags contain coins. The coins are given as non‐overlapping segments in the array coins, where each element coins[i] = [lᵢ, rᵢ, cᵢ] indicates that every bag from coordinate lᵢ to rᵢ contains cᵢ coins. In addition, you are given an integer k. The task is to select k consecutive bags (i.e. a window of length k) so that the total coins collected from those bags is maximized.

Key Insights

  • The coin distribution is piecewise constant: only segments [lᵢ, rᵢ] have coins (with value cᵢ) and all other positions yield 0.
  • The coin segments do not overlap; hence the coin function is defined by disjoint intervals.
  • Rather than iterating bag‐by‐bag (the coordinates go up to 10^9), we can “compress” the problem into intervals and use prefix sum ideas.
  • The maximum window is achieved when its boundaries align with one or more endpoints of these segments. Thus, only a limited set of candidate starting positions (such as each segment’s l, r, or adjusted r – k + 1) need be considered.
  • With a prefix sum for the coin “integral” (i.e. the cumulative number of coins up to any coordinate), one can answer any query “what is the total coins in [L, R]?” in O(log n) using binary search on the segments.

Space and Time Complexity

Time Complexity: O(n log n + m log n)
  • O(n log n) to sort the segments and build the prefix sums, where n = coins.length.
  • O(m log n) for iterating over m candidate starting positions (m is O(n)) and answering each window query in O(log n).
Space Complexity: O(n)
  • Storing the segments along with helper arrays for binary search and prefix sums.

Solution

We first sort the given coin segments by their starting coordinate. Because only segments have nonzero coin values, we “integrate” the coin contributions in each segment by computing a prefix sum over the intervals. In more detail, we build two helper arrays:   • ends – an array of the ending coordinates from each segment.   • prefix – prefix[i] is the total number of coins in all segments up to index i (each segment’s total coin count is (rᵢ - lᵢ + 1) * cᵢ).

We then build a function query(x) that returns the total coins from coordinate 1 to x. This function works by binary searching the segments array using the “ends” array. For any query x, we add up the full contributions from segments that lie completely before x and add the partial contribution for the first segment that x falls into   (if any).

Once the query function is prepared, note that the total coins in a window [L, L+k-1] are given by query(L+k-1) – query(L-1). The twist is to find the best L. A common observation is that the maximum is achieved when L is “aligned” with one of the boundaries of the coin segments. Therefore, we consider a candidate set for L that includes:   • Each segment’s starting coordinate (lᵢ).   • Each segment’s ending coordinate (rᵢ).   • And also max(1, rᵢ - k + 1) so that the window ending at rᵢ is exactly captured. We iterate over these candidate L values (making sure they are ≥1) and compute the window’s total coins using our query function. The maximum answer is returned.

Below are code solutions with detailed, line‐by‐line comments in Python, JavaScript, C++, and Java.

Code Solutions

# Python solution

import bisect

def maxCoins(coins, k):
    # Sort the coin segments by their starting coordinate.
    # Each coin segment is represented as a tuple: (l, r, c)
    segments = sorted(coins, key=lambda seg: seg[0])
    n = len(segments)
    
    # Prepare helper arrays:
    # 'ends' will store the ending coordinate of each segment.
    ends = []
    # 'prefix' will store the cumulative coin counts (integral) for the segments.
    prefix = []
    
    for l, r, c in segments:
        ends.append(r)
        seg_total = (r - l + 1) * c
        # Compute the running prefix sum.
        if prefix:
            prefix.append(prefix[-1] + seg_total)
        else:
            prefix.append(seg_total)
    
    # query(x) returns the total coins from coordinate 1 to x.
    # It uses binary search on the segments (by their 'ends' coordinate).
    def query(x):
        # If x is less than the start of the first segment, then return 0.
        if x < segments[0][0]:
            return 0
        # Find the rightmost segment whose end is <= x.
        # bisect_right returns the insertion point, so subtract 1.
        idx = bisect.bisect_right(ends, x) - 1
        res = prefix[idx]  # sum of coins fully included up to segment idx
        # Check if there is a segment that partially overlaps x.
        if idx + 1 < n:
            l_j, r_j, c_j = segments[idx + 1]
            if x >= l_j:
                # Compute the partial overlap in the next segment.
                overlap = min(x, r_j) - l_j + 1
                res += overlap * c_j
        return res
    
    # Compute the coins in window [L, L+k-1]
    def window_sum(L):
        return query(L + k - 1) - query(L - 1)
    
    # Build a set of candidate starting positions.
    cand = set()
    for l, r, c in segments:
        # candidate: segment start
        cand.add(l)
        # candidate: segment end
        cand.add(r)
        # candidate: so that window ending at r (i.e. L+k-1 = r)
        cand.add(max(1, r - k + 1))
    
    ans = 0
    # Try every candidate starting position.
    for L in cand:
        # Only consider valid starting positions (L must be positive).
        if L < 1:
            continue
        cur = window_sum(L)
        if cur > ans:
            ans = cur
    return ans

# Example usage:
coins1 = [[8,10,1],[1,3,2],[5,6,4]]
k1 = 4
print(maxCoins(coins1, k1))  # Expected Output: 10
← Back to All Questions