[Java/C++/Python] Sliding Window
IntuitionThe interval to pick will either/or
Start at A[i][0]
End at A[i][1]
ExplanationOne sliding window to check the interval starting at A[i][0].
One slidin
# **Intuition**
The interval to pick will either/or
- Start at A[i][0]
- End at A[i][1]

# **Explanation**
One sliding window to check the interval starting at `A[i][0]`.
One sliding window to check the interval ending at `A[i][0]`.

`cur` is the `coins` from `k` consecutive bags.
`part` need to calculate if the edge interval is overlapped with `k` bags.

return the bigger result from two passes.

# **Complexity**
Sort
Time `O(sort)`
Space `O(sort)`

Sliding window
Time `O(n)`
Space `O(1)`
<br>

```Java [Java]
    public long maximumCoins(int[][] A, int k) {
        Arrays.sort(A, (a, b) -> a[0] - b[0]);
        int n = A.length;

        // Start at A[i][0]
        long res = 0, cur = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && A[j][1] <= A[i][0] + k - 1) {
                cur += 1L * (A[j][1] - A[j][0] + 1) * A[j][2];
                j++;
            }
            if (j < n) {
                long part = 1L * Math.max(0, A[i][0] + k - 1 - A[j][0] + 1) * A[j][2];
                res = Math.max(res, cur + part);
            }
            cur -= 1L * (A[i][1] - A[i][0] + 1) * A[i][2];
        }

        // End at A[i][1]
        cur = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            cur += 1L * (A[i][1] - A[i][0] + 1) * A[i][2];
            while (A[j][1] < A[i][1] - k + 1) {
                cur -= 1L * (A[j][1] - A[j][0] + 1) * A[j][2];
                j++;
            }
            long part = 1L * Math.max(0, A[i][1] - k - A[j][0] + 1) * A[j][2];
            res = Math.max(res, cur - part);
        }

        return res;
    }
```

```C++ [C++]
    long long maximumCoins(vector<vector<int>>& A, int k) {
        sort(A.begin(), A.end());
        int n = A.size();

        // Start at A[i][0]
        long long res = 0, cur = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && A[j][1] <= A[i][0] + k - 1) {
                cur += 1L * (A[j][1] - A[j][0] + 1) * A[j][2];
                j++;
            }
            if (j < n) {
                long long part = 1L * max(0, A[i][0] + k - 1 - A[j][0] + 1) * A[j][2];
                res = max(res, cur + part);
            }
            cur -= 1L * (A[i][1] - A[i][0] + 1) * A[i][2];
        }

        // End at A[i][1]
        cur = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            cur += 1L * (A[i][1] - A[i][0] + 1) * A[i][2];
            while (A[j][1] < A[i][1] - k + 1) {
                cur -= 1L * (A[j][1] - A[j][0] + 1) * A[j][2];
                j++;
            }
            long long part = 1L * max(0, A[i][1] - k - A[j][0] + 1) * A[j][2];
            res = max(res, cur - part);
        }

        return res;
    }
```

```py [Python3]
    def maximumCoins(self, A: List[List[int]], k: int) -> int:
        def slide(A):
            A.sort()
            res = cur = j = 0
            for i in range(len(A)):
                cur += (A[i][1] - A[i][0] + 1) * A[i][2]
                while A[j][1] < A[i][1] - k + 1:
                    cur -= (A[j][1] - A[j][0] + 1) * A[j][2]
                    j += 1
                part = max(0, A[i][1] - k - A[j][0] + 1) * A[j][2]
                res = max(res, cur - part)
            return res
        return max(slide(A), slide([[-r,-l,w] for l,r,w in A]))
```

# More Similar Sliding Window Problems
Here are some similar sliding window problems.
Also find more explanations and discussion.
Good luck and have fun.

- [3413. Maximum Coins From K Consecutive Bags](https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags/solutions/6232195/javacpython-sliding-window-by-lee215-3418/)
- [3347. Maximum Frequency of an Element After Performing Operations II](https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-ii/discuss/6027259/JavaC%2B%2BPython-Two-cases)
- [2958. Length of Longest Subarray With at Most K Frequency](https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/solutions/4382698/java-c-python-sliding-window/)
- [2831. Find the Longest Equal Subarray](https://leetcode.com/problems/find-the-longest-equal-subarray/discuss/3934172/JavaC%2B%2BPython-One-Pass-Sliding-Window-O(n))
- [2799. Count Complete Subarrays in an Array](https://leetcode.com/problems/count-complete-subarrays-in-an-array/discuss/3836137/JavaC%2B%2BPython-Sliding-Window-O(n))
- [2779. Maximum Beauty of an Array After Applying Operation](https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation/discuss/3771308/JavaC%2B%2BPython-Sliding-Window)
- [2730. Find the Longest Semi-Repetitive Substring](https://leetcode.com/problems/find-the-longest-semi-repetitive-substring/discuss/3629621/JavaC%2B%2BPython-Sliding-Window)
- [2555. Maximize Win From Two Segments](https://leetcode.com/problems/maximize-win-from-two-segments/discuss/3141449/JavaC%2B%2BPython-DP-%2B-Sliding-Segment-O(n))
- [2537. Count the Number of Good Subarrays](https://leetcode.com/problems/count-the-number-of-good-subarrays/discuss/3052559/C%2B%2BPython-Sliding-Window)
- [2401. Longest Nice Subarray](https://leetcode.com/problems/longest-nice-subarray/discuss/2527496/Python-Sliding-Window)
- [2398. Maximum Number of Robots Within Budget](https://leetcode.com/problems/maximum-number-of-robots-within-budget/discuss/2524838/Python-Sliding-Window-O(n))
- [2024. Maximize the Confusion of an Exam](https://leetcode.com/problems/maximize-the-confusion-of-an-exam/discuss/1499049/JavaC%2B%2BPython-Sliding-Window-strict-O(n))
- [1838. Frequency of the Most Frequent Element](https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175090/JavaC%2B%2BPython-Sliding-Window)
- [1493. Longest Subarray of 1's After Deleting One Element](https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/discuss/708112/JavaC%2B%2BPython-Sliding-Window-at-most-one-0)
- [1425. Constrained Subsequence Sum](https://leetcode.com/problems/constrained-subsequence-sum/discuss/597751/JavaC++Python-O(N)-Decreasing-Deque)
- [1358. Number of Substrings Containing All Three Characters](https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/discuss/516977/JavaC++Python-Easy-and-Concise)
- [1248. Count Number of Nice Subarrays](https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419378/JavaC%2B%2BPython-Sliding-Window-atMost(K)-atMost(K-1))
- [1234. Replace the Substring for Balanced String](https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/javacpython-sliding-window/)
- [1004. Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247564/JavaC%2B%2BPython-Sliding-Window)
- [930. Binary Subarrays With Sum](https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/)
- [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/523136/JavaC%2B%2BPython-Sliding-Window)
- [904. Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets/discuss/170740/Sliding-Window-for-K-Elements)
- [862. Shortest Subarray with Sum at Least K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque)
- [424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/discuss/278271/JavaC%2B%2BPython-Sliding-Window-just-O(n))
- [209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/discuss/433123/JavaC++Python-Sliding-Window)

['C++', 'Java', 'Python3']