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

1
2
3
4
5

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

1
2
3
4
5

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.

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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.