# Maximum Coins From K Consecutive Bags
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags)
Canonical: https://scaleengineer.com/dsa/problems/maximum-coins-from-k-consecutive-bags
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
There are an infinite amount of bags on a number line, one bag for each coordinate. Some of these bags contain coins.

You are given a 2D array `coins`, where `coins[i] = [li, ri, ci]` denotes that every bag from `li` to `ri` contains `ci` 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.

**Example 1:**

**Input:** coins = \[\[8,10,1\],\[1,3,2\],\[5,6,4\]\], k = 4

**Output:** 10

**Explanation:**

Selecting bags at positions `[3, 4, 5, 6]` gives the maximum number of coins: `2 + 0 + 4 + 4 = 10`.

**Example 2:**

**Input:** coins = \[\[1,10,3\]\], k = 2

**Output:** 6

**Explanation:**

Selecting bags at positions `[1, 2]` gives the maximum number of coins: `3 + 3 = 6`.

**Constraints:**

* `1 <= coins.length <= 105`
* `1 <= k <= 109`
* `coins[i] == [li, ri, ci]`
* `1 <= li <= ri <= 109`
* `1 <= ci <= 1000`
* The given segments are non-overlapping.

# Approaches
## Brute-force over Candidate Start Positions
A straightforward but inefficient approach is to identify a set of potential optimal starting positions for the `k` consecutive bags and then calculate the sum for each. The key insight is that the maximum sum is likely achieved when the window of `k` bags aligns with the start or end of one of the coin intervals. This leads to a set of candidate start positions. For each candidate, we can perform a full calculation of the coins within that window by checking against all given coin intervals.
**Time:** O(N^2), where N is the number of coin intervals. There are up to 2N candidate start positions. For each candidate, we iterate through all N intervals to calculate the sum, leading to a quadratic time complexity. · **Space:** O(N), where N is the number of coin intervals. This space is used to store the set of candidate start positions.
**Pros:** Relatively simple to understand and implement.; Correctly identifies a smaller, finite set of candidate solutions to check.
**Cons:** The time complexity of `O(N^2)` is too slow and will not pass the time limits for the given constraints (`N` up to 10^5).
### Explanation
This method is based on a brute-force check over a reduced search space. Instead of checking every possible start position on the number line (which is infinite), we only check positions that are 'critical'.

1.  **Generate Candidate Start Positions**: We create a list of candidate start positions. For each interval `[l_i, r_i, c_i]`, the critical start points for a window of size `k` are `l_i` (aligning the window's start with the interval's start) and `r_i - k + 1` (aligning the window's end with the interval's end). We collect all such unique, positive positions.

2.  **Calculate Sum for Each Candidate**: For each candidate start position `s`, we calculate the total coins in the window `[s, s + k - 1]`. This is done by iterating through all `N` original coin intervals `[l_j, r_j, c_j]`. For each interval, we find the length of its overlap with our window `[s, s + k - 1]`. The overlap length is `max(0, min(s + k - 1, r_j) - max(s, l_j) + 1)`. We multiply this length by `c_j` and add it to the total for the current window.

3.  **Find Maximum**: We maintain a variable `max_coins` and update it with the highest total found among all candidate windows.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long maximumCoins(int[][] coins, int k) {
        Set<Long> candidates = new HashSet<>();
        for (int[] coin : coins) {
            long l = coin[0];
            long r = coin[1];
            candidates.add(l);
            if (r - k + 1 > 0) {
                candidates.add(r - k + 1);
            }
        }

        long maxTotalCoins = 0;

        for (long startPos : candidates) {
            long endPos = startPos + k - 1;
            long currentTotalCoins = 0;
            for (int[] coin : coins) {
                long l = coin[0];
                long r = coin[1];
                long c = coin[2];

                long overlapStart = Math.max(startPos, l);
                long overlapEnd = Math.min(endPos, r);

                if (overlapStart <= overlapEnd) {
                    long overlapLength = overlapEnd - overlapStart + 1;
                    currentTotalCoins += overlapLength * c;
                }
            }
            maxTotalCoins = Math.max(maxTotalCoins, currentTotalCoins);
        }

        return maxTotalCoins;
    }
}
```
### Algorithm
*   **Identify Candidate Start Positions**: The total number of coins in a window of `k` bags changes only when the window's start or end crosses the boundary of a coin interval. This suggests that the optimal window likely starts at a position related to these boundaries. A reasonable set of candidate start positions for the window `[s, s+k-1]` are `s = l_i` or `s = r_i - k + 1` for every given interval `[l_i, r_i, c_i]`.
*   **Iterate and Calculate**: The algorithm iterates through each of these `O(N)` candidate start positions.
*   **Summation**: For each candidate start position `s`, it calculates the total coins in the window `[s, s+k-1]`. This is done by iterating through all `N` coin intervals and summing up the contributions from each interval that overlaps with the window.
*   **Overlap Calculation**: The contribution of an interval `[l_j, r_j, c_j]` is `c_j` multiplied by the length of the intersection between `[s, s+k-1]` and `[l_j, r_j]`.
*   **Track Maximum**: The algorithm keeps track of the maximum sum found across all candidate windows and returns it as the result.

## Sweep-line with Prefix Sums
A highly efficient approach uses a sweep-line algorithm combined with prefix sums. The core idea is to first discretize the number line based on the start and end points of the coin intervals. This creates a set of elementary segments where the coin count per bag is constant. By pre-calculating prefix sums on these segments, we can quickly find the total coins in any given `k`-length window. We only need to test a linear number of 'critical' windows to find the maximum.
**Time:** O(N log N), where N is the number of coin intervals. Sorting the event points takes `O(N log N)`. Building segments and prefix sums takes `O(N)`. Evaluating `O(N)` candidates with `O(log N)` per query results in `O(N log N)`. The dominant factor is sorting or the evaluation loop. · **Space:** O(N), where N is the number of coin intervals. This is for storing the event points, segments, prefix sums, and candidate positions.
**Pros:** Efficient, with `O(N log N)` time complexity that passes the given constraints.; Systematic and robust approach for problems involving intervals on a number line.
**Cons:** More complex to implement correctly, requiring careful handling of event points, segments, prefix sums, and binary search.; Uses more memory to store segments and prefix sums.
### Explanation
This approach optimizes the calculation for each candidate window from `O(N)` down to `O(log N)`, resulting in a much faster overall algorithm.

1.  **Create Event Points**: We use a `TreeMap` to store the change in coins per bag at each interval boundary. For each `[l, r, c]`, we do `map[l] += c` and `map[r+1] -= c`. The `TreeMap` automatically keeps the points sorted and aggregates changes at the same position.

2.  **Construct Segments and Prefix Sums**: We iterate through the `TreeMap` to build an explicit list of segments. Let's say the sorted unique positions are `p_0, p_1, ..., p_m`. We can determine the constant number of coins `C_i` in each segment `[p_i, p_{i+1}-1]`. Simultaneously, we can build a prefix sum array, `prefix_sum[i]`, storing the total coins from `p_0` up to `p_i-1`.

3.  **Identify Candidate Start Positions**: The set of critical start positions for a window of size `k` are `p_i` and `p_i - k + 1` for each event point `p_i`.

4.  **Efficiently Calculate Window Sum**: We create a helper function, say `getSum(p)`, which calculates the total coins in all bags from position 1 to `p`. This function works by first using binary search to find which segment `p` falls into. Then, it uses the pre-calculated prefix sum to get the total coins up to the start of that segment and adds the contribution from the partial segment.

5.  **Evaluate Candidates**: For each candidate start position `s > 0`, the window is `[s, s+k-1]`. The total coins are calculated as `getSum(s+k-1) - getSum(s-1)`. We track the maximum value found.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

class Solution {
    public long maximumCoins(int[][] coins, int k) {
        Map<Long, Long> delta = new TreeMap<>();
        for (int[] coin : coins) {
            long l = coin[0];
            long r = coin[1];
            long c = coin[2];
            delta.put(l, delta.getOrDefault(l, 0L) + c);
            delta.put(r + 1, delta.getOrDefault(r + 1, 0L) - c);
        }

        List<Long> pos = new ArrayList<>();
        List<Long> segmentCoins = new ArrayList<>();
        long currentCoinsPerBag = 0;
        long lastPos = 1;

        for (Map.Entry<Long, Long> entry : delta.entrySet()) {
            long p = entry.getKey();
            if (p > lastPos) {
                pos.add(lastPos);
                segmentCoins.add(currentCoinsPerBag);
            }
            currentCoinsPerBag += entry.getValue();
            lastPos = p;
        }
        pos.add(lastPos);
        segmentCoins.add(currentCoinsPerBag);

        int n = pos.size();
        long[] prefixSum = new long[n + 1];
        prefixSum[0] = 0;
        for (int i = 0; i < n - 1; i++) {
            prefixSum[i + 1] = prefixSum[i] + (pos.get(i + 1) - pos.get(i)) * segmentCoins.get(i);
        }
        prefixSum[n] = prefixSum[n-1];

        Set<Long> candidates = new HashSet<>();
        for (long p : delta.keySet()) {
            candidates.add(p);
            if (p - k > 0) {
                candidates.add(p - k);
            }
        }
        if (!candidates.contains(1L)) candidates.add(1L);

        long maxCoins = 0;
        for (long start : candidates) {
            if (start <= 0) continue;
            long end = start + k - 1;
            maxCoins = Math.max(maxCoins, getSum(end, pos, segmentCoins, prefixSum) - getSum(start - 1, pos, segmentCoins, prefixSum));
        }

        return maxCoins;
    }

    private long getSum(long p, List<Long> pos, List<Long> segmentCoins, long[] prefixSum) {
        if (p <= 0) return 0;
        
        int i = Collections.binarySearch(pos, p + 1);
        i = (i < 0) ? (-i - 1) - 1 : i - 1;

        if (i < 0) return 0;

        long sum = prefixSum[i];
        sum += (p - pos.get(i) + 1) * segmentCoins.get(i);
        return sum;
    }
}
```
### Algorithm
*   **Event Points and Segments**: First, we process the `coins` array to find all 'event points'. For each interval `[l, r, c]`, `l` is an event point where the number of coins per bag increases by `c`, and `r+1` is an event point where it decreases by `c`. We use a map (like `TreeMap` in Java) to store the net change at each unique position.
*   **Build Segments**: By iterating through the sorted event points, we can construct a list of contiguous segments on the number line. Each segment `[p_i, p_{i+1}-1]` has a constant number of coins per bag, which we can calculate by accumulating the changes from the event points.
*   **Prefix Sums**: We then build a prefix sum array over these segments. `prefix_sum[i]` will store the total number of coins from the beginning of the first segment up to the start of the `i`-th segment. This allows for quick calculation of the total coins over a large range of segments.
*   **Identify Candidate Windows**: The optimal window `[s, s+k-1]` must start or end at an event point. Thus, the candidate start positions `s` are `p_j` or `p_j - k + 1` for each event point `p_j`.
*   **Query for Sum**: For each candidate start `s`, we calculate the sum of coins in `[s, s+k-1]` by using a helper function `query(p)`. This function calculates the total coins from the beginning up to position `p`. The sum for the window is then `query(s+k-1) - query(s-1)`. The `query` function uses binary search on the segment positions and the prefix sum array to compute the result in `O(log N)` time.
*   **Find Maximum**: We find the maximum sum among all candidates.