Coding Patterns: Sliding Window

Sliding Window is used to solve questions when we need to calculate something for subarrays of a given size or find the optimal contiguous subarray in an array. Also used for string questions and they will ask you to find some "substring". What is Contiguous? In simple terms, elements must be next to each other without gaps Tips: - In an interview if they ask to find an optimal subarray ask if it's contiguous. - When you hear "contiguous" you should think if there's a sliding window solution Sliding window can be: - Static: You know the exact window size in advance. i.e. - Dynamic: Expanding and shrinking the window based on some constraint Both maintain two pointers but: - Two-Pointer: Usually refers to having two independent pointers and we don't care about the elements in between those pointers. - Sliding Window: Implies you’re maintaining a contiguous window of interest between the two pointers. Common pitfalls: - Not expanding/shrinking the window correctly. - Updating the Result at the Right Time - For a fixed-size window, only update the result once the window reaches the required size. - For a dynamic window, update result only if your window meets the conditions. Usually you grow your window until it breaks the condition then you shrink from the left until it meets the condition again. _______________________________________ 00:00 - Sliding Window Pattern Explained 06:22 - Q1 - Average of subarrays of size k 18:31 - Q2 - Maximum Consecutive Ones III 27:16 - Common Pitfalls