3413. Maximum Coins From K Consecutive Bags LeetCode Solution
In this guide, you will get 3413. Maximum Coins From K Consecutive Bags LeetCode Solution with the best time and space complexity. The solution to Maximum Coins From K Consecutive Bags problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Coins From K Consecutive Bags
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.
3413. Maximum Coins From K Consecutive Bags LeetCode Solution in C++
class Solution {
public:
long long maximumCoins(vector<vector<int>>& coins, int k) {
vector<vector<int>> negatedCoins = negateLeftRight(coins);
return max(slide(coins, k), slide(negatedCoins, k));
}
private:
vector<vector<int>> negateLeftRight(const vector<vector<int>> coins) {
vector<vector<int>> res;
for (const vector<int>& coin : coins) {
const int l = coin[0];
const int r = coin[1];
const int c = coin[2];
res.push_back({-r, -l, c});
}
return res;
}
long slide(vector<vector<int>>& coins, int k) {
long res = 0;
long windowSum = 0;
int j = 0;
ranges::sort(coins);
for (const vector<int>& coin : coins) {
const int li = coin[0];
const int ri = coin[1];
const int ci = coin[2];
const int rightBoundary = li + k;
// [lj, rj] is fully in [li..li + k)
while (j + 1 < coins.size() && coins[j + 1][0] < rightBoundary) {
const int lj = coins[j][0];
const int rj = coins[j][1];
const int cj = coins[j][2];
windowSum += static_cast<long>(rj - lj + 1) * cj;
++j;
}
// [lj, rj] may be partially in [l..l + k)
long last = 0;
if (j < coins.size() && coins[j][0] < rightBoundary) {
const int lj = coins[j][0];
const int rj = coins[j][1];
const int cj = coins[j][2];
last = static_cast<long>(min(rightBoundary - 1, rj) - lj + 1) * cj;
}
res = max(res, windowSum + last);
windowSum -= static_cast<long>(ri - li + 1) * ci;
}
return res;
}
}; /* code provided by PROGIEZ */
3413. Maximum Coins From K Consecutive Bags LeetCode Solution in Java
class Solution {
public long maximumCoins(int[][] coins, int k) {
int[][] negatedCoins = negateLeftRight(coins);
return Math.max(slide(coins, k), slide(negatedCoins, k));
}
private int[][] negateLeftRight(int[][] coins) {
int[][] res = new int[coins.length][3];
for (int i = 0; i < coins.length; ++i) {
final int l = coins[i][0];
final int r = coins[i][1];
final int c = coins[i][2];
res[i][0] = -r;
res[i][1] = -l;
res[i][2] = c;
}
return res;
}
private long slide(int[][] coins, int k) {
long res = 0;
long windowSum = 0;
int j = 0;
Arrays.sort(coins, (a, b) -> Integer.compare(a[0], b[0]));
for (int[] coin : coins) {
final int li = coin[0];
final int ri = coin[1];
final int ci = coin[2];
final int rightBoundary = li + k;
// [lj, rj] is fully in [li..li + k).
while (j + 1 < coins.length && coins[j + 1][0] < rightBoundary) {
final int lj = coins[j][0];
final int rj = coins[j][1];
final int cj = coins[j][2];
windowSum += (long) (rj - lj + 1) * cj;
++j;
}
// [lj, rj] may be partially in [l..l + k).
long last = 0;
if (j < coins.length && coins[j][0] < rightBoundary) {
final int lj = coins[j][0];
final int rj = coins[j][1];
final int cj = coins[j][2];
last = (long) (Math.min(rightBoundary - 1, rj) - lj + 1) * cj;
}
res = Math.max(res, windowSum + last);
windowSum -= (long) (ri - li + 1) * ci;
}
return res;
}
} // code provided by PROGIEZ
3413. Maximum Coins From K Consecutive Bags LeetCode Solution in Python
class Solution:
def maximumCoins(self, coins: list[list[int]], k: int) -> int:
return max(self._slide(coins, k),
self._slide([[-r, -l, c] for l, r, c in coins], k))
def _slide(self, coins: list[list[int]], k: int) -> int:
coins.sort()
res = 0
windowSum = 0
j = 0
for li, ri, ci in coins: # Consider the number line [li..li + k).
rightBoundary = li + k
# [lj, rj] is fully in [li..li + k).
while j + 1 < len(coins) and coins[j + 1][0] < rightBoundary:
lj, rj, cj = coins[j]
windowSum += (rj - lj + 1) * cj
j += 1
# [lj, rj] may be partially in [l..l + k).
last = 0
if j < len(coins) and coins[j][0] < rightBoundary:
lj, rj, cj = coins[j]
last = (min(rightBoundary - 1, rj) - lj + 1) * cj
res = max(res, windowSum + last)
windowSum -= (ri - li + 1) * ci
return res # code by PROGIEZ
