Easy to understand!
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

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

class Solution {
    public int bs1(int key, int[][] arr) {
        int l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid][0] <= key) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public int bs2(int key, int[][] arr) {
        int l = 0, r = arr.length - 1, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid][1] >= key) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    public long maximumCoins(int[][] coins, int k) {
        HashMap<Integer, Long> pref = new HashMap<>();
        HashMap<Integer, Long> suff = new HashMap<>();
        Arrays.sort(coins, (a, b) -> Integer.compare(a[0], b[0]));
        int n = coins.length;
        long sum = 0;

        // Compute prefix sum correctly using long
        for (int i = 0; i < n; i++) {
            sum += (long) coins[i][2] * (coins[i][1] - coins[i][0] + 1);
            pref.put(coins[i][1], sum);
        }

        sum = 0;
        // Compute suffix sum correctly using long
        for (int i = n - 1; i >= 0; i--) {
            sum += (long) coins[i][2] * (coins[i][1] - coins[i][0] + 1);
            suff.put(coins[i][0], sum);
        }

        long max = 0;
        for (int i = 0; i < n; i++) {
            int li = coins[i][0];

            int idx = bs1(li + k - 1, coins);
            long curr = 0;
            if (idx >= 1) {
                if (i == 0)
                    curr = pref.getOrDefault(coins[idx - 1][1], 0L);
                else
                    curr = pref.getOrDefault(coins[idx - 1][1], 0L) - pref.getOrDefault(coins[i - 1][1], 0L);
            }

            if (idx >= 0) {
                int rightLim = Math.min(li + k - 1, coins[idx][1]);
                curr += (long) (rightLim - coins[idx][0] + 1) * coins[idx][2];
            }
            max = Math.max(max, curr);
        }

        for (int i = n - 1; i >= 0; i--) {
            int ri = coins[i][1];

            int idx = bs2(ri - k + 1, coins);
            long curr = 0;
            if (idx + 1 < n) {
                if (i == n - 1)
                    curr = suff.getOrDefault(coins[idx + 1][0], 0L);
                else
                    curr = suff.getOrDefault(coins[idx + 1][0], 0L) - suff.getOrDefault(coins[i + 1][0], 0L);
            }

            if (idx >= 0) {
                int leftLim = Math.max(ri - k + 1, coins[idx][0]);
                curr += (long) (coins[idx][1] - leftLim + 1) * coins[idx][2];
            }
            max = Math.max(max, curr);
        }

        return max;
    }
}

```
['Hash Table', 'Binary Search', 'Sorting', 'Prefix Sum', 'Java']