Explained sliding window solution [C++/Java/Python/Javascript] || Beats 100%
IntuitionInput Description:
coins is a list of intervals:
[𝑠𝑡𝑎rt,end,coins]sorted by their starting index.
k is the size of the range (or sliding window) within
# Intuition
# Input Description:
1. coins is a list of intervals: 
[𝑠𝑡𝑎rt,end,coins]sorted by their starting index.
2. k is the size of the range (or sliding window) within which we can collect coins.
# Overall Goal:

1. For any sliding window of size k, calculate the maximum coins that can be collected.
2. To achieve this, the solution considers two cases:
Case 1: Include the entire current interval and part of the next interval.
Case 2: Include the entire current interval and part of the previous interval.
# Key Observations:

1. The coin intervals can partially or fully overlap the sliding window of size 𝑘
2. The solution leverages a sliding window technique to efficiently calculate the coin sums within any range of 𝑘

# Complexity
- Time complexity:
O(n*logn)

- Space complexity:
O(1)

# Code
```cpp []
class Solution {
public:
    #define ll long long

    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());
        int n = coins.size();

        ll curr_sum = 0;
        ll ans = 0;

        // Case 1: Forward partial
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && coins[j][1] <= coins[i][0] + k - 1) {
                curr_sum += (1ll) * (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            if (j < n) {
                ll partial = max((1ll) * 0, (1ll) * (coins[i][0] + k - 1 - coins[j][0] + 1) * coins[j][2]);
                ans = max(ans, curr_sum + partial);
            }

            curr_sum -= ((1ll) * (coins[i][1] - coins[i][0] + 1) * coins[i][2]);
        }

        // Case 2: Back partial sum
        curr_sum = 0;
        for (int i = 0, j = 0; i < n; i++) {
            curr_sum += (1ll) * (coins[i][1] - coins[i][0] + 1) * coins[i][2];

            while (coins[j][1] < coins[i][1] - k + 1) {
                curr_sum -= (1ll) * (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            ll partial = max((1ll) * 0, (1ll) * ((coins[i][1] - k + 1) - coins[j][0]) * coins[j][2]);
            ans = max(ans, curr_sum - partial);
        }

        return ans;
    }
};

```
```java []
import java.util.*;

class Solution {
    public long maximumCoins(int[][] coins, int k) {
        Arrays.sort(coins, (a, b) -> Integer.compare(a[0], b[0]));
        int n = coins.length;

        long currSum = 0;
        long ans = 0;

        // Case 1: Forward partial
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && coins[j][1] <= coins[i][0] + k - 1) {
                currSum += (long) (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            if (j < n) {
                long partial = Math.max(0, (long) (coins[i][0] + k - 1 - coins[j][0] + 1) * coins[j][2]);
                ans = Math.max(ans, currSum + partial);
            }

            currSum -= (long) (coins[i][1] - coins[i][0] + 1) * coins[i][2];
        }

        // Case 2: Back partial sum
        currSum = 0;
        for (int i = 0, j = 0; i < n; i++) {
            currSum += (long) (coins[i][1] - coins[i][0] + 1) * coins[i][2];

            while (coins[j][1] < coins[i][1] - k + 1) {
                currSum -= (long) (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            long partial = Math.max(0, (long) ((coins[i][1] - k + 1) - coins[j][0]) * coins[j][2]);
            ans = Math.max(ans, currSum - partial);
        }

        return ans;
    }
}

```
```python []
class Solution:
    def maximumCoins(self, coins: list[list[int]], k: int) -> int:
        coins.sort()
        n = len(coins)

        curr_sum = 0
        ans = 0

        # Case 1: Forward partial
        j = 0
        for i in range(n):
            while j < n and coins[j][1] <= coins[i][0] + k - 1:
                curr_sum += (coins[j][1] - coins[j][0] + 1) * coins[j][2]
                j += 1

            if j < n:
                partial = max(0, (coins[i][0] + k - 1 - coins[j][0] + 1) * coins[j][2])
                ans = max(ans, curr_sum + partial)

            curr_sum -= (coins[i][1] - coins[i][0] + 1) * coins[i][2]

        # Case 2: Back partial sum
        curr_sum = 0
        j = 0
        for i in range(n):
            curr_sum += (coins[i][1] - coins[i][0] + 1) * coins[i][2]

            while coins[j][1] < coins[i][1] - k + 1:
                curr_sum -= (coins[j][1] - coins[j][0] + 1) * coins[j][2]
                j += 1

            partial = max(0, ((coins[i][1] - k + 1) - coins[j][0]) * coins[j][2])
            ans = max(ans, curr_sum - partial)

        return ans

```
```javascript []
class Solution {
    maximumCoins(coins, k) {
        coins.sort((a, b) => a[0] - b[0]);
        const n = coins.length;

        let currSum = 0;
        let ans = 0;

        // Case 1: Forward partial
        let j = 0;
        for (let i = 0; i < n; i++) {
            while (j < n && coins[j][1] <= coins[i][0] + k - 1) {
                currSum += (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            if (j < n) {
                let partial = Math.max(0, (coins[i][0] + k - 1 - coins[j][0] + 1) * coins[j][2]);
                ans = Math.max(ans, currSum + partial);
            }

            currSum -= (coins[i][1] - coins[i][0] + 1) * coins[i][2];
        }

        // Case 2: Back partial sum
        currSum = 0;
        j = 0;
        for (let i = 0; i < n; i++) {
            currSum += (coins[i][1] - coins[i][0] + 1) * coins[i][2];

            while (coins[j][1] < coins[i][1] - k + 1) {
                currSum -= (coins[j][1] - coins[j][0] + 1) * coins[j][2];
                j++;
            }

            let partial = Math.max(0, ((coins[i][1] - k + 1) - coins[j][0]) * coins[j][2]);
            ans = Math.max(ans, currSum - partial);
        }

        return ans;
    }
}

```

['Array', 'Binary Search', 'Greedy', 'Sliding Window', 'Sorting', 'Prefix Sum', 'Python', 'C++', 'Java', 'JavaScript']