Welcome to my algorithmic journey!
If you've ever looked at a coding challenge and felt like you were staring at a brick wall, you aren't alone. Most of the time, the secret isn't about being a math genius, it's about recognising the pattern.
In this series, we are breaking down the most essential coding patterns from beginner to expert level, keeping things simple, practical, and (hopefully) a little bit fun.
Today, we are diving deep into Sliding Window Technique. Whether you are preparing for a big interview or just trying to write cleaner, faster code, mastering this pattern is a total game-changer.
Let's strip away the jargon and see how it actually works!
What is Sliding Window?
Imagine you have a long, delicious Subway sandwich (our array), and you're trying to find the 3-inch section with the most olives. Instead of cutting a 3-inch piece, measuring the olives, throwing it away, and then cutting another 3-inch piece from scratch, you simply slide a 3-inch magnifying glass along the sandwich. As the glass moves:
- It welcomes a new olive on the right.
- It says goodbye to an old olive on the left.
In the world of coding, a Sliding Window is a technique used to perform operations on a specific "subset" of data (like a subarray or a substring) without re-calculating everything from zero.
The Mathematical Logic
In a standard "Brute Force" approach, if you want to find the sum of every 3-item window in an array, you'd do this:
- Sum items 1, 2, and 3.
- Forget everything.
- Sum items 2, 3, and 4.
- Forget everything.
- Sum items 3, 4, and 5…
That is a lot of wasted energy! The Sliding Window logic says: "Hey, items 2 and 3 were in both windows. Why calculate them again?"
The "Add & Subtract" Trick
Mathematically, the logic is as simple as a revolving door at a mall.
- The Entry: A new element joins the window from the right (+).
- The Exit: The oldest element leaves the window from the left (-).
- The Middle: Everything else stays exactly where it is!
If we are looking for the sum of a window (W), and we move from position i to i+1:
NewSum = OldSum - ElementAt(i) + ElementAt(i + WindowSize)
Efficiency and Complexity
Before we break down the performance of this algorithm, it's important to understand how we measure "speed" and "memory" in the coding world. We use something called Big-O Notation. If you aren't familiar with terms like O(n) or O(1), or if you just need a quick refresher so you don't get lost in the numbers, check out my previous guide here.
How it solves Time Complexity
In a typical "Brute Force" approach (the loop-inside-a-loop nightmare), the time complexity is usually O(N x K), where N is the total number of items and K is the size of your window. If both are large, your program slows down to a crawl. With the Sliding Window, we achieve the holy grail of performance: O(N).
How it solves Space Complexity
Most Sliding Window problems have a Space Complexity of O(1) (Constant Space).
- Why? Because you aren't creating a new array for every window. You are just keeping track of a few variables (like current_sum, max_length, or two pointers called left and right).
- The Exception: If you're using a Hash Map or a Frequency Table to keep track of characters (like in the "Longest Substring with Unique Characters" problem), your space might grow to O(K), where K is the size of your character set. But even then, it's usually much smaller than the original data!
Where is it used? (Applications)
Video Streaming (The "Buffer" Window): Ever notice how YouTube or Netflix loads a little bit of the video ahead of where you are? That's a sliding window! The Window: The 30 seconds of video currently being downloaded. The Slide: As you watch one second, the window "slides" forward to download the next second. It keeps a constant "window" of data ready so your movie doesn't lag.
Network Congestion (TCP/IP): The internet is basically a giant series of tubes. If a computer sends too much data at once, the tubes clog. To fix this, the internet uses a "Sliding Window Protocol." It sends a specific number of packets (the window). It only "slides" to send the next packet once the receiver says, "Got it!" This prevents your Wi-Fi from having a total meltdown.
Health & Fitness Tracking: If your Fitbit or Apple Watch tells you your "Moving Average Heart Rate," it's using this technique. Instead of showing your heart rate from 3 hours ago, it calculates the average of just the last 5 minutes. Every minute that passes, it drops the oldest minute and adds the newest one. This gives you a smooth, real-time update.
Classic Interview Problems
You are given an array and asked to find the highest total you can get by adding up exactly K numbers in a row. This is the "Hello World" of the Fixed Sliding Window.
You are given a string and asked to find the longest part of it that contains only a specific number of unique letters. This is the "Accordion" of Sliding Window, where your window grows and shrinks based on what it finds.
You are given two strings and asked to find the shortest possible "slice" of the first string that has every letter of the second string inside it. This is the "Final Boss" that teaches you how to perfectly balance expanding and contracting your window.
Implementation
Now, let's see this pattern in action!
For these demonstrations, I'll be using C#. However, don't let the language choice stop you if you usually code in Python, Java, JavaScript etc. The logic and the underlying pattern remain exactly the same across all languages, only the syntax changes. Feel free to follow along and implement the logic in your own preferred language.
Fixed Size Sliding Window:
The general steps to solve these questions by following below steps:
- Find the size of the window required, say K.
- Compute the result for 1st window, i.e. include the first K elements of the data structure.
- Then use a loop to slide the window by 1 and keep computing the result window by window.
Ex: You are given an array representing the hourly electricity usage (in kilowatts) of a small neighborhood over a 24-hour period. Find the maximum total energy consumed during any continuous 3-hour "Peak Period.
public class HelloWorld
{
private static int GetMaxTotalEnergy(int[] array, int subArraySize){
// Invalid
if(array.Length < subArraySize) return -1;
int currentSum = 0;
// First window sum
for(int i = 0; i < subArraySize; i++){
currentSum += array[i];
}
int maxSum = currentSum;
int arrayLength = array.Length - subArraySize + 1;
for(int i = 1; i < arrayLength; i++){
currentSum += array[i + subArraySize - 1] - array[i - 1];
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
public static void Main(string[] args)
{
int[] myArray = {4, 2, 10, 8, 7, 6, 3, 2, 1, 5};
int k = 3;
Console.WriteLine("Maximum total energy of a subarray of size " + k + " is: " + GetMaxTotalEnergy(myArray, k));
}
}
Variable Size Sliding Window:
The general steps to solve these questions by following below steps:
- We increase our right pointer one by one till our condition is true.
- At any step if our condition does not match, we shrink the size of our window by increasing left pointer.
- Again, when our condition satisfies, we start increasing the right pointer and follow step 1.
- We follow these steps until we reach to the end of the array.
Ex: Given an array of positive integers and a target sum, find the length of the smallest contiguous subarray whose sum is greater than or equal to that target. If no such subarray exists, return 0.
public class HelloWorld
{
private static int GetSmallestSubarray(int[] array, int target)
{
int left = 0;
int currentSum = 0;
int minLength = int.MaxValue;
for (int right = 0; right < array.Length; right++)
{
currentSum += array[right];
while (currentSum >= target)
{
int currentWindowSize = right - left + 1;
minLength = Math.Min(minLength, currentWindowSize);
currentSum -= array[left];
left++;
}
}
return minLength == int.MaxValue ? 0 : minLength;
}
public static void Main(string[] args)
{
int[] numbers = { 1, 2, 3, 4, 5 };
int targetSum = 7;
Console.WriteLine("Smallest subarray length: " + GetSmallestSubarray(numbers, targetSum));
}
}
Practice Roadmap
Theory is great, but coding is a sport. You only get better by practicing! To help you master this pattern, I've curated a list of LeetCode problems. To get the most out of your study time, I recommend following the 3:6:1 ratio (or the 3:5:2 if you're feeling brave!):
30% Easy to build your confidence and grasp the core logic.
https://leetcode.com/problems/maximum-average-subarray-i
https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/
https://leetcode.com/problems/contains-duplicate-ii/60% Medium to learn how to apply the pattern in tricky scenarios.
https://leetcode.com/problems/longest-substring-without-repeating-characters
https://leetcode.com/problems/max-consecutive-ones-iii
https://leetcode.com/problems/minimum-size-subarray-sum
https://leetcode.com/problems/find-all-anagrams-in-a-string
https://leetcode.com/problems/fruit-into-baskets/10% Hard to challenge your limits and see the pattern at its peak.
https://leetcode.com/problems/minimum-window-substring/
https://leetcode.com/problems/sliding-window-maximum/
Don't get discouraged if you get stuck! The goal isn't to solve it in five minutes; the goal is to recognise the pattern. Happy coding!
Stay updated with the latest insights and tutorials by following me on Medium, dev.io and LinkedIn. For any inquiries for games or questions, feel free to reach out to me via email. I'm here to assist you with any queries you may have!
Don't miss out on future articles and tips!
Top comments (0)