## Sliding Window
#### 2024/12/14
---

### What is Sliding Window
* Two variable `front` and `back` form a range `[front, back]`. When `front` and `back` is moving from left to right, you can perform some calculation dynamically.
* Total Time Complexity is `O(N)`.
>`[front, back]` is inclusive both side.

### Main Idea
1. Moving `back++` and check if `[front, back]` satisfies your requirements.
2. If not, moving `front++` until `[front, back]` satisfies your requirements.
3. Once `[front, back]` satisfies your requirements, you can perform something to the range or something you got during sliding window.
### Code

for (int front = 0, back = 0; back < n; back++) {
    /* Section 1 */
    //------------
    /* do something with respect to back
     * example:
     * list.offerLast(back);
     */
    
    /* Section 2 */
    //------------
    while (front < back && /* some "in bound" condition*/) {

        /* do something with respect to front
         * example:
         * list.remove(front);
         */
        
        front++;
    }
    
    /* Section 3 */
    //-------------
    /* calculate the answer
     * example:
     * total += back - front + 1;
     */
}

* Each Iteration:
* `back++`
* Section 1: initializes or updates values related to back
* we have range `[front, back]`
* Section 2 ensures the range `[front, back]` satisfies conditions:
* `front++` until `[front, back]` is the range you require
* Section 3: performs operations on the valid range
* now you have a valid range `[front, back]`

### Graph
* example: count the number of subarrays of length 3

array = [a, b, c, d, e, f, g, h, i, j, k]
f = front
b = back
---------------------------------
iteration 1：
 f
[a, b, c, d, e, f, g, h, i, j, k]
 b
---------------------------------
iteration 2：
 f
[a, b, c, d, e, f, g, h, i, j, k]
    b
---------------------------------
iteration 3：
 f
[a, b, c, d, e, f, g, h, i, j, k]
       b
count += 1
---------------------------------
iteration 4：
    f
[a, b, c, d, e, f, g, h, i, j, k]
          b
count += 1
---------------------------------
iteration 5：
       f
[a, b, c, d, e, f, g, h, i, j, k]
             b
count += 1
---------------------------------
iteration 6：
          f
[a, b, c, d, e, f, g, h, i, j, k]
                b
count += 1
.
.
.

---
## Example
### LeetCode 632. Smallest Range Covering Elements from K Lists(hard)
* Flatten the `2D List`, and we will get `ArrayList<Pair> arr`
* Sort the `arr` according to `val`
* Use sliding window
* requirement:`number of group == nums.length`
* result: the `front` and `back` with minimum`arr.get(back).val - arr.get(front).val)`

import java.util.HashMap;
import java.util.Collections;
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Pair> arr = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (int val : nums.get(i)) {
                arr.add(new Pair(i, val));
            }
        }
        Collections.sort(arr, (o1, o2) -> o1.val - o2.val);
        int ans = Integer.MAX_VALUE;
        int aF = -1, aB = -1;
        
        // Sliding Window
        for (int front = 0, back = 0; back < arr.size(); back++) {
            // Section 1
            int group = arr.get(back).group;
            map.putIfAbsent(group, 0);
            map.put(group, map.get(group) + 1);
            
            // Section 2
            while (map.size() == nums.size() && front < arr.size() && map.get(arr.get(front).group) > 1) {
                int gFront = arr.get(front).group;
                map.put(gFront, map.get(gFront) - 1);
                front++;
            }
            
            // Section 3
            if (map.size() == nums.size()) {
                int temp = arr.get(back).val - arr.get(front).val;
                if (temp < ans) {
                    ans = temp;
                    aF = front;
                    aB = back;
                }
                map.remove(arr.get(front).group);
                front++;
            }
        }
        // end of Sliding Window
        return new int[] { arr.get(aF).val, arr.get(aB).val };
    }
}

class Pair {
    int group, val;
    Pair (int group, int val) {
        this.group = group;
        this.val = val;
    }
}