### General - implemented using two pointers for arrays - treat a subset/subarray as the "window" - gets you the widest valid window for each possible end of window (right pointer) ![[sliding window.png]] ### Identifying Sliding Window Problems 1. problem defines a criteria that makes a subarray "valid" - (i.e sum, number of unique elements, frequency of an element etc) 2. asks you to find the valid subarray in a **specific** way - most common is finding the *best* valid subarray (i.e the *longest* valid subarray) - or commonly they'll ask to find the *number* of valid subarrays ### The Algorithm - initially we have left = right = 0 - first subarray we look at is just the 1st element on its own - then we expand right, but if adding this makes things invalid, we need to increment left to remove elements to try to get something valid again - as we add and remove elements, we "slide" our window from left to right ![[sliding window algorithm.png]] ``` function fn(arr): left = 0 for (int right = 0; right < arr.length; right++): Do some logic to "add" element at arr[right] to window while WINDOW_IS_INVALID: Do some logic to "remove" element at arr[left] from window left++ Do some logic to update the answer ``` - sliding window guarantees $O(n)$ runtime - there is a max of $2n$ window iterations, right pointer can move $n$ times and left pointer can move $n$ times - we get $O(1)$ space complexity, we only store indices of two pointers ### Number of Subarrays Problem Type - to still use sliding window, we need to use a unique math trick - how many valid windows end at index right? - from left index to right index, you can keep moving left index up for smaller arrays - this would give us right - left + 1 arrays - this relies on all increments of right to be valid subarrays as well ### Fixed Window Size Problem Type - in examples above, the window size was dynamic - sometimes the window length might be fixed ``` function fn(arr, k): curr = some data to track the window // build the first window for (int i = 0; i < k; i++) Do something with curr or other variables to build first window ans = answer variable, probably equal to curr here depending on the problem for (int i = k; i < arr.length; i++) Add arr[i] to window Remove arr[i - k] from window Update ans return ans ``` - in terms of required memory storage, the above code removes the need to use two pointer indices - only the "curr" condition checker and "ans" answer is left - total loop iterations is equal exactly to $n$, the length of $nums$ - runtime is $O(n)$, using space complexity of $O(1)$