Conquer Sliding Window Approach
What is a sliding window?
The sliding window is a problem-solving technique, which can reduce the time complexity of the algorithm from O(n²), O(n³) to linear time complexity O(n). [n is the number of elements in the array/string/linked list].
So ideally, we can remove the nested loops in some problems that can be converted to a single loop.
What is the window here, and how it slides?
The Window is the size of subrange [substring, subsets, subarray] and at the time of iteration/looping, this window will slide throughout the ordered and linear data structure of the given size.
How to identify a given problem is a sliding window?
- When the problem ask for subrange[aka substring, subsets, subarray, etc] with find longest/shortest/minimum/maximum[kind of optimal] or given some target value
- The given problem should be an ordered and linear data structure [array, strings, linked lists ]
What’s the time and space complexity?
Most of the problems for the sliding window can be solved by O(n) Time Complexity and O(1) Space Complexity.
Below is the category of lists of the sliding window problems from Leetcode and GeeksforGeeks.
Easy:
- https://www.geeksforgeeks.org/find-maximum-minimum-sum-subarray-size-k/
- https://leetcode.com/problems/minimum-size-subarray-sum/
Medium:
- https://leetcode.com/problems/longest-substring-without-repeating-characters/
- https://leetcode.com/problems/sliding-window-maximum/
- https://leetcode.com/problems/longest-repeating-character-replacement/
- https://leetcode.com/problems/permutation-in-string/
- https://leetcode.com/problems/fruit-into-baskets/
- https://leetcode.com/problems/find-all-anagrams-in-a-string/
Hard:
- https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
- https://www.geeksforgeeks.org/print-longest-substring-without-repeating-characters/
- https://www.geeksforgeeks.org/longest-subsegment-1s-formed-changing-k-0s/
- https://leetcode.com/problems/minimum-window-substring/
- https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
Thanks for reading and Happy coding! :)
