Maximum Coins From K Consecutive Bags - Solution & Explanation

Problem Overview: You are given ranges of bags where each bag in the range contains a certain number of coins. The task is to choose exactly k consecutive bag indices and collect the maximum total coins possible. Since ranges can overlap and bag indices can be large, the challenge is computing the maximum sum efficiently without iterating every bag index.

Approach 1: Brute Force Range Simulation (High Complexity)

The direct idea is to simulate the number of coins in every bag, then evaluate every window of length k. Build an array representing coins per bag by expanding each range and accumulating contributions. After that, iterate through all possible windows and track the maximum sum. This works conceptually but fails when bag indices are large because the array size becomes impractical. Time complexity is O(N * range + M) where M is the maximum bag index, and space complexity is O(M). This approach mainly helps understand the structure of the problem.

Approach 2: Prefix Sum on Compressed Coordinates (O(n log n))

Instead of expanding every bag index, compress the coordinates of all relevant boundaries. Convert ranges into events and compute coin contributions using a prefix sum. After building the cumulative coins for each compressed segment, evaluate the total coins inside any window of length k. This reduces memory usage dramatically because you only track meaningful breakpoints. Time complexity becomes O(n log n) due to sorting and coordinate compression, with O(n) extra space.

Approach 3: Sorting + Sliding Window on Intervals (Optimal)

The efficient solution works directly on the interval representation. First sort the coin ranges by starting index using standard sorting. Then treat the chosen segment [x, x + k - 1] as a window and compute how much each interval contributes based on overlap length. Use a sliding window with two pointers to maintain intervals intersecting the current window while adjusting contributions when the window shifts. Prefix sums or partial overlap calculations ensure each interval is processed once. Sorting dominates the runtime, giving O(n log n) time and O(n) space.

Recommended for interviews: Interviewers expect the interval-based sliding window solution. Starting with the brute force approach shows you understand the problem constraints, but recognizing that bag indices can be large leads naturally to sorting ranges and computing overlaps. Using sliding window with prefix-style accumulation demonstrates strong knowledge of interval processing and optimization techniques.