Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. We do this via maintaining a subset of items as our window, and resize and move that window within the larger list until we find a solution. Sliding Window Technique is a subset of Dynamic Programming, and it frequently appears in algorithm interviews. In this video, you will learn how Sliding Window Technique works (with animations), tips and tricks of using it, along with its applications on some sample questions.
Video: https://www.youtube.com/watch?v=jM2dhDPYMQM
Article: http://quanticdev.com/algorithms/dynamic-programming/sliding-window
In the video, you will find the solutions to the following questions, as well as their time and space complexities:
• Easy: Statically Sized Sliding Window: Given an array of integers, find maximum/minimum sum subarray of the required size.
• Medium: Dynamically Sized Sliding Window: Given an array of positive integers, find the subarrays that add up to a given number.
o Variation (Medium): Same question but for an array with all integers (positive, 0, negative). The optimal solution is Kadane's Algorithm, but Sliding Window can still be applied with modifications (not recommended though).
• Medium: Flipping/Swapping: Given an array of 0's and 1's, find the maximum sequence of continuous 1's that can be formed by flipping at-most k 0's to 1's.
• Hard: Strings: Given a string and n characters, find the shortest substring that contains all the desired characters.
Top comments (0)