Sliding Window

May 16, 2021
Algorithms

Introduction

Sliding window problems require you to keep a fixed size window that satisfies a certain criteria and shift or slide the window as soon as a violation is encountered.

A Few Examples

Problem

Given an array of integers A and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Algorithm

The key idea is to maintain an ordered multiset of elements and compare the max and the min values to see if they exceed limit. Each time we encounter a violation we will decrease the window size by one beginning from the left hand side. The gap of the largest possible subarray we have seen will remain and at the end the array size - our ending left pointer (i) will give us the answer.

Longest Continuous Subarray with Absolute Diff Less Than or Equal to Limit

Problem

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

Algorithm

There are several problems that will ask you to find the number of continuous subarrays containing k properties (odd #s in this example). The key insight to remember here is that to arrive at exactly k items which satisfy a certain property, we just have to count the total length of continuous subarrays which satisfy atmost k elements and those that satisfy at most k-1 elements and take the difference between two. Where the at most k-1 and the at most k differ means we have exclusive subarrays that only work for the exactly k case. Solution follows below:

exactly(k) = atmost(k) - atmost(k-1)

Practice Problems

MEDIUM

Minimum size subarray sum

Binary Subarrays with Sum

Max Consecutive Ones III

Count Number of Nice Subarrays

Number of Substrings Containing All Three Characters

Replace the Substring for Balanced String

Fruit Into Baskets

HARD

Shortest Subarray with Sum at least K

Subarrays with K Different Integers

Constrained Subsequence Sum

Related Posts

Stay Updated

Thank you! Your submission has been received!

Oops! Something went wrong while submitting the form