Sliding Window Problems | Identify, Solve and Interview Questions - Coding

When we are dealing with problems that require checking answers of some ranges in an array, the Sliding window algorithm can be a very powerful technique.

What are Sliding Window Problems?

Sliding window problems are computational problems in which a fixed/variable-size window is moved through a data structure, typically an array or string, to efficiently process or analyze the continuous subsets of elements. This technique is used to optimize calculations and find patterns, making it a common approach in algorithm design.

Follow the Sliding Window Technique post to learn more about this algorithm.

Key Points to Identify Sliding Window Problems:

These problems generally evolve around Finding Maximum / Minimum Subarray, Substrings which satisfy some specific condition.

The size of the subarray or substring ‘K’ will be given or asked in some of the problems.

These problem can easily be solved in O(n²) time complexity using nested loops, using sliding window we can solve these in O(n) Time Complexity.

Required Time Complexity: O(n) or O(nlog(n))

Constraints: n <= 10⁶, If n is the size of the Array / String.

In this following article, we’ll explore the different patterns where we can apply the sliding window technique with the help of problems and examples.

There are generally two categories of Sliding window problems:

Fixed Size Sliding Window Problems
Variable Size Sliding Window Problems

Fixed Size Sliding Window

Type 1: Problems where we are generally given a specific size of window ‘K’ in the question itself.

For example: Given an array of integers and a number K, find the maximum sum of a subarray of size K.

Post Link: Click Here

Intuition: In this question we already given the size of the subarray we just have to iterate in the array and calculate the sum of each subarray of size k with sliding window technique.

Similar problems following same approach:

Problem	Practice Link
Sum of minimum and maximum elements of all subarrays of given size K	Solve
Count Distinct elements in each window of size K	Solve
Find first negative integer in every k size window	Solve
Maximum of all subarray of size K	Solve
Maximum MEX of all subarray of size K	Solve

Type 2: Problems in which rather than giving the length question ask about the maximum / minimum fixed length then we can also apply the fixed size sliding window technique.

For example: Maximum subarray size, such that all subarrays of that size have sum less than K.

Post Link: Click Here

Intuition: In this question we have to find the maximum size of the subarray which satisfy the given condition. In these type of questions we can apply Binary Search on Answer + Sliding Window to solve the question, We can find our possible size of subarray by applying binary search on subarray size and find the condition validation using sliding window of fixed size K , which will be equal to mid value in Binary Search.

Similar problems following same approach:

Problem	Practice Link
Maximum number of toys that can be purchased with amount K	Solve
Longest Subarray with sum K	Solve
Smallest Distinct Window	Solve
Largest Subarray of equal number of 0’s and 1’s	Solve
Longest Subarray with sum divisible by K	Solve

Variable Size Sliding Window Problem

In these sliding window questions we have been asked about the maximum or minimum subarray/substring with some conditions (like having largest sum, smallest sum etc.)

For example: Find length of the longest substring without repeating characters.

Post Link: Click Here

Intuition: To solve the problems based on the above category follow the below intuition steps:

In these kind of problems we can increase right pointer till we found some character (say ‘x‘) which is already in our range, store the answer and increase left pointer till we found that character (‘x’) again, We can keep moving forward and store the answer.
As we can see in this question our window size is variable so that’s why these problems are called variable size sliding window problem.

Similar problems following same approach:

Problem	Practice Link
Find length of the longest substring without repeating characters.	Solve
Search all permutations of pattern string	Solve
Longest K unique characters substring	Solve
Count of subarrays with sum equals k in given Binary array	Solve
Find Subarrays with given sum	Solve

What are Sliding Window Problems?

Key Points to Identify Sliding Window Problems:

Fixed Size Sliding Window

Variable Size Sliding Window Problem

Other problems based on Sliding Window:

Link for Practice Problems of Sliding Window

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12