## Pattern Name: Sliding Window ### Overview: Search across a data structure through a fixed window (i.e. constant length of 4) or variable window (i.e., window expands and contracts based on looping logic). The purpose of this approach is to create an algorithm that allows for simplistic computations based on the entering or exiting array values, as opposed to doing operations across an entire subarray. For example, when calculating an average, you can keep track of the total of the values of the subarray by subtracting and adding elements exiting and entering the array. This is much more computationally efficient than calculating the average each time the subarray shifts. ### Applicable Data Structures: - [[Strings]], [[Arrays]], [[LinkedLists]] ### Diagram: ![[SlidingWindow.excalidraw.svg]] ### Key Concepts - High vs. low | left vs. right | start vs. end - the pointers used to keep track of the window ### When to Use: - Iterating sequentially over a data structure - Problems that involve finding: - Max - Min - Longest - Shortest - Determining substrings ## Key Considerations Always consider how using the start vs. end pointer in your loop will impact the algorithm. A `for` loop can be used to specify the when the end pointer should stop. Alternatively, you can use a `while` loop to continue looping while the end pointer is less than the length of the array. Always include a check for if the length of the array is 1, since this case is not effectively handled in a sliding window loop. ### General Tips ### Performance - In general, you can maximize the performance of an algorithm using the sliding window approach by avoiding computationally expensive operations across the entire subarray. Instead, create an algorithm that tracks values and makes decisions based on what the impact is of the specific elements entering or exiting the subarray. For example, avoid repeated use of: - Calculating an average - Instead, keep track of how the total value changes and only conduct division when necessary - Creating Counters - You can use a hash map to keep track of indices and shrink windows quickly using the indices (i.e., shrink the window by more than just 1) ### Space ## Use Cases - TBD #### Working Notes - Take notes on python for loops using sliding window