Maximum Coins From K Consecutive Bags

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.

Examples

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 <= 10^5
• 1 <= k <= 10^9
• coins[i] == [li, ri, ci]
• 1 <= li <= ri <= 10^9
• 1 <= ci <= 1000
• The given segments are non-overlapping.

Solution

Method 1 – Prefix Sum + Sliding Window

Intuition

Since the segments are non-overlapping, we can flatten the segments into a list of (position, coins) and then use a prefix sum array to efficiently compute the sum of coins in any interval. We then slide a window of size k over all possible positions to find the maximum sum.

Approach

1. Collect all unique positions from the segments, and for each position, compute the total coins at that position.
2. Sort the positions and build an array of coins at each position.
3. Use a sliding window of size k over the sorted positions to compute the sum of coins in each window.
4. Return the maximum sum found.

Code

C++

class Solution {
public:
    int maxCoins(vector<vector<int>>& coins, int k) {
        map<int, int> pos;
        for (auto& seg : coins) {
            for (int i = seg[0]; i <= seg[1]; ++i) pos[i] += seg[2];
        }
        vector<pair<int, int>> arr(pos.begin(), pos.end());
        int n = arr.size(), ans = 0, sum = 0, l = 0;
        for (int r = 0; r < n; ++r) {
            sum += arr[r].second;
            while (arr[r].first - arr[l].first + 1 > k) {
                sum -= arr[l].second;
                ++l;
            }
            if (arr[r].first - arr[l].first + 1 == k)
                ans = max(ans, sum);
        }
        return ans;
    }
};

Go

func maxCoins(coins [][]int, k int) int {
    pos := map[int]int{}
    for _, seg := range coins {
        for i := seg[0]; i <= seg[1]; i++ {
            pos[i] += seg[2]
        }
    }
    keys := make([]int, 0, len(pos))
    for p := range pos {
        keys = append(keys, p)
    }
    sort.Ints(keys)
    arr := make([]int, len(keys))
    for i, p := range keys {
        arr[i] = pos[p]
    }
    ans, sum, l := 0, 0, 0
    for r := 0; r < len(keys); r++ {
        sum += arr[r]
        for keys[r]-keys[l]+1 > k {
            sum -= arr[l]
            l++
        }
        if keys[r]-keys[l]+1 == k && sum > ans {
            ans = sum
        }
    }
    return ans
}

Java

class Solution {
    public int maxCoins(int[][] coins, int k) {
        TreeMap<Integer, Integer> pos = new TreeMap<>();
        for (int[] seg : coins) {
            for (int i = seg[0]; i <= seg[1]; ++i) pos.put(i, pos.getOrDefault(i, 0) + seg[2]);
        }
        List<Integer> keys = new ArrayList<>(pos.keySet());
        int n = keys.size(), ans = 0, sum = 0, l = 0;
        for (int r = 0; r < n; ++r) {
            sum += pos.get(keys.get(r));
            while (keys.get(r) - keys.get(l) + 1 > k) {
                sum -= pos.get(keys.get(l));
                ++l;
            }
            if (keys.get(r) - keys.get(l) + 1 == k)
                ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maxCoins(coins: Array<IntArray>, k: Int): Int {
        val pos = mutableMapOf<Int, Int>()
        for (seg in coins) {
            for (i in seg[0]..seg[1]) pos[i] = pos.getOrDefault(i, 0) + seg[2]
        }
        val keys = pos.keys.sorted()
        val arr = keys.map { pos[it]!! }
        var ans = 0
        var sum = 0
        var l = 0
        for (r in keys.indices) {
            sum += arr[r]
            while (keys[r] - keys[l] + 1 > k) {
                sum -= arr[l]
                l++
            }
            if (keys[r] - keys[l] + 1 == k)
                ans = maxOf(ans, sum)
        }
        return ans
    }
}

Python

class Solution:
    def maxCoins(self, coins: list[list[int]], k: int) -> int:
        from collections import defaultdict
        pos = defaultdict(int)
        for l, r, c in coins:
            for i in range(l, r+1):
                pos[i] += c
        keys = sorted(pos)
        arr = [pos[x] for x in keys]
        ans = s = l = 0
        for r in range(len(keys)):
            s += arr[r]
            while keys[r] - keys[l] + 1 > k:
                s -= arr[l]
                l += 1
            if keys[r] - keys[l] + 1 == k:
                ans = max(ans, s)
        return ans

Rust

impl Solution {
    pub fn max_coins(coins: Vec<Vec<i32>>, k: i32) -> i32 {
        use std::collections::BTreeMap;
        let mut pos = BTreeMap::new();
        for seg in coins {
            for i in seg[0]..=seg[1] {
                *pos.entry(i).or_insert(0) += seg[2];
            }
        }
        let keys: Vec<_> = pos.keys().cloned().collect();
        let arr: Vec<_> = keys.iter().map(|&x| pos[&x]).collect();
        let mut ans = 0;
        let mut sum = 0;
        let mut l = 0;
        for r in 0..keys.len() {
            sum += arr[r];
            while keys[r] - keys[l] + 1 > k {
                sum -= arr[l];
                l += 1;
            }
            if keys[r] - keys[l] + 1 == k {
                ans = ans.max(sum);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxCoins(coins: number[][], k: number): number {
        const pos = new Map<number, number>();
        for (const [l, r, c] of coins) {
            for (let i = l; i <= r; ++i) pos.set(i, (pos.get(i) ?? 0) + c);
        }
        const keys = Array.from(pos.keys()).sort((a, b) => a - b);
        const arr = keys.map(x => pos.get(x)!);
        let ans = 0, sum = 0, l = 0;
        for (let r = 0; r < keys.length; ++r) {
            sum += arr[r];
            while (keys[r] - keys[l] + 1 > k) {
                sum -= arr[l];
                l++;
            }
            if (keys[r] - keys[l] + 1 === k)
                ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(M + N log N), where M is the total number of positions covered and N is the number of unique positions.
• 🧺 Space complexity: O(N), for the position map and arrays.