Skip to main content

Maximum Coins From K Consecutive Bags | Leetcode | JavaScript Code | Easy Explanation

 In this blog post, we'll explore the LeetCode problem: Maximum Coins From K Consecutive Bags. This is a medium-level problem that involves analyzing a set of non-overlapping intervals and efficiently calculating the maximum sum of coins that can be obtained from k consecutive bags.

We will walk you through the problem, explain the solution approach, and present a JavaScript solution with a focus on clarity and efficiency. By the end of this guide, you’ll not only understand how to solve this problem but also get insights into how to approach similar problems involving intervals and optimization.


Problem Breakdown

Let’s first dive into the problem statement to understand the task clearly:

You are given a 2D array coins, where each element is an array [li, ri, ci], denoting that for each bag from coordinate li to coordinate ri, there are ci coins. In other words, every bag from position li to ri contains ci coins.

Your goal is to collect coins from k consecutive bags and return the maximum amount of coins you can collect.

The segments in the coins array are non-overlapping. You can think of each segment as a range on a number line where bags containing coins are present.

The challenge is to figure out the most efficient way to collect coins from k consecutive bags and maximize the total number of coins obtained.


Example Walkthrough

Let’s work through a couple of examples to understand the problem better:

Example 1:

Input:

coins = [[8,10,1],[1,3,2],[5,6,4]]

k = 4

Output:

10

Explanation:

  • We have three bags:
    • Bags from 8 to 10 contain 1 coin each.
    • Bags from 1 to 3 contain 2 coins each.
    • Bags from 5 to 6 contain 4 coins each.

To maximize the number of coins from k = 4 consecutive bags, we pick bags from position 3 to 6 (inclusive). These bags contain coins as follows:

  • Bag 3: 2 coins
  • Bag 4: 0 coins (since no coin information is provided for bag 4, assume 0)
  • Bag 5: 4 coins
  • Bag 6: 4 coins

So, the maximum number of coins we can collect is: 2 + 0 + 4 + 4 = 10.

Example 2:

Input:

coins = [[1,10,3]] k = 2

Output:

6

Explanation:

Here, there’s only one segment:

  • Bags from 1 to 10 contain 3 coins each.

To maximize the number of coins from k = 2 consecutive bags, we can choose the first two bags, both containing 3 coins. So, the result will be 3 + 3 = 6.


Key Observations

  1. Non-overlapping Intervals: The intervals are non-overlapping, so you don’t have to worry about handling overlapping ranges.
  2. Array Representation: Each segment [li, ri, ci] represents a range where each bag from li to ri contains ci coins.
  3. Optimization Goal: The goal is to find k consecutive bags with the maximum number of coins. This is a classic example of a sliding window problem or range optimization.

Approach

To solve the problem efficiently, we need to keep track of coin counts across the number line and find the maximum number of coins we can collect from k consecutive bags. Here's how we can approach it:

Steps to Solve:

  1. Create a Mapping of Coins on the Number Line: Use an array or a hash map to track how many coins each position on the number line contains.
  2. Sliding Window: Using a sliding window technique, calculate the total number of coins from k consecutive bags. Slide the window across the number line and calculate the sum for each position.
  3. Keep Track of the Maximum: Track the maximum sum of coins obtained from k consecutive bags during the sliding window process.

JavaScript Code Implementation

Here's the JavaScript code that solves the problem:

var maximumCoins = function(coins, k) {
    coins.sort((a, b) => a[0] - b[0]);
   
    let intervals = [];
    let prev_end = -1;
    for (let seg of coins) {
        let li = seg[0];
        let ri = seg[1];
        let ci = seg[2];
        if (prev_end !== -1 && li > prev_end + 1) {
            intervals.push([prev_end + 1, li - 1, 0]);
        }
        intervals.push([li, ri, ci]);
        prev_end = ri;
    }
   
    let parnoktils = coins.slice();
   
    let candidate_starts_set = new Set();
    for (let interval of intervals) {
        let start = interval[0];
        let end = interval[1];
        candidate_starts_set.add(start);
        let cand_start = end - k + 1;
        if (cand_start >= 1) {
            candidate_starts_set.add(cand_start);
        }
    }
   
    let candidates = [];
    for (let x of candidate_starts_set) {
        if (x <= intervals[intervals.length - 1][1]) {
            candidates.push(x);
        }
    }
    candidates.sort((a, b) => a - b);
   
    let n = intervals.length;
    let starts = Array(n);
    let ends = Array(n);
    let sums = Array(n);
    for (let i = 0; i < n; ++i) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
        sums[i] = intervals[i][2];
    }
   
    // Compute prefix sums of coins
    let prefix_sum = Array(n).fill(0);
    prefix_sum[0] = (ends[0] - starts[0] + 1) * sums[0];
    for (let i = 1; i < n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + (ends[i] - starts[i] + 1) * sums[i];
    }
   
    let max_sum = 0;
    for (let x of candidates) {
        let window_end = x + k - 1;
       
        let l = binarySearch(ends, x);
       
        let r = binarySearch(starts, window_end, true) - 1;
       
        if (l > r || l >= n || r < 0) {
            continue;
        }
       
        let sum_coins = prefix_sum[r] - (l > 0 ? prefix_sum[l - 1] : 0);
       
        if (starts[l] < x) {
            let overlap = Math.min(ends[l], window_end) - x + 1;
            sum_coins -= (ends[l] - starts[l] + 1 - overlap) * sums[l];
        }
       
        if (ends[r] > window_end) {
            let overlap = window_end - starts[r] + 1;
            sum_coins -= (ends[r] - starts[r] + 1 - overlap) * sums[r];
        }
       
        max_sum = Math.max(max_sum, sum_coins);
    }
   
    return max_sum;
};


function binarySearch(arr, target, isUpper = false) {
    let low = 0;
    let high = arr.length;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] < target || (isUpper && arr[mid] <= target)) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}


The Maximum Coins From K Consecutive Bags problem is an excellent example of using sliding window techniques and interval mapping to optimize the sum calculation. With efficient tracking of coins in each bag and a sliding window approach, we can solve this problem in linear time, making it scalable even for larger inputs.


Tags

  • LeetCode Problem
  • Sliding Window
  • Coin Collection
  • Interval Problems
  • JavaScript Solutions
  • Competitive Programming
  • Algorithm Explanation
  • Optimization Techniques

Popular posts from this blog

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through   10 beginner-friendly LeetCode questions   that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1.  Two Sum (Easy) Prob...

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....