Top Problems on Sliding Window Technique

The sliding window is a very intriguing technique used to solve some of the complex problems involving an array or a string. It is often used to reduce the time complexity of the problem from O(n²) to O(n).

The basic idea is to maintain a window that satisfies the problem constraints. A window can be represented by taking two pointers — say left and right — that points to a specific index in the array or specific character in case of a string.

The window is called “unstable” if it breaks any of the problem conditions. The window then tries to stabilize itself by shrinking (increment left pointer) or expanding (increment right pointer). The process continues until the problem is solved.

Below are some of the top interview questions that take advantage of the sliding window technique -

1. Find the longest substring of a given string containing k distinct characters

2. Find all substrings of a string that are permutation of a given string

3. Longest substring of given string containing distinct characters

4. Find maximum length sequence of continuous ones (Using Sliding Window)

5. Find the maximum sequence of continuous 1’s that can be formed by replacing at-most k zeroes by ones

6. Find minimum sum subarray of given size k

7. Find subarray having given sum in given array of integers

8. Find the length of the smallest subarray whose sum of elements is greater than the given number

9. Find the count of distinct elements in every sub-array of size k

10. Print all sub-arrays of an array having distinct elements

11. Count the distinct absolute values in the sorted array

12. Find duplicates within given range k in an array

Thanks for reading.