Sliding Window Technique with Two Practical Examples
 Introduction
 Types of Sliding Window
 FixedSize Sliding Window
 DynamicSize Sliding Window
 Applications of the Sliding Window Technique
 Run C Programming Online Compiler
¶Introduction
The sliding window technique is a method for iterating through an array or list to find a subset of elements that meet a particular condition. It involves maintaining a window that slides over the array, either by fixing the size of the window or dynamically adjusting it based on the problem’s requirements. The essence of the sliding window technique lies in its ability to reduce the time complexity of certain problems from O(𝑛 ^{2} ) to O(𝑛) by avoiding the need for nested loops. Instead of recomputing the entire subset of elements for each position, the window “slides” over the array, updating the required values incrementally. The sliding window technique is generally used in problems like Checking for the presence of a fixed or dynamic size subarray with certain properties, String problems like finding the longest substring with unique characters or matching patterns.
¶Types of Sliding Window
There are two primary types of sliding windows:
FixedSize Sliding Window: The window has a fixed size and slides from the beginning to the end of the array.
DynamicSize Sliding Window: The size of the window can expand or contract based on the conditions specified in the problem.
¶FixedSize Sliding Window
A fixedsize sliding window is used when the problem requires processing subarrays of a given size. This involves initializing the window with the first set of elements and then moving it one element at a time while updating the necessary values.
Consider an array of integers and we have to find the maximum sum of the all possible subarrays of size
k
.
To solve this problem, we slide a window of size k
across the array. We calculate the sum of elements within the window. In each iteration, we “slide” the window by one element:
 We remove the element leaving the window from the sum.
 We add the element entering the window to the sum.
 We keep track of the maximum sum encountered so far.
This approach has time complexity of O(n)
rather than calculating answer using nested loops with O(n * k)
time complexity.
#include <stdio.h>
int maxSubarraySum(int arr[], int n, int k) {
int max_sum = 0;
int current_sum = 0;
// Calculate the sum of the first k elements
for (int i = 0; i < k; i++) {
current_sum += arr[i];
}
max_sum = current_sum; // Initially, max_sum is the sum of the first window
// Slide the window
for (int i = k; i < n; i++) {
current_sum = arr[i  k]; // Remove element leaving the window
current_sum += arr[i]; // Add element entering the window
max_sum = current_sum > max_sum ? current_sum : max_sum; // Update max_sum if necessary
}
return max_sum;
}
int main() {
int arr[] = {1, 4, 2, 10, 6, 3, 3};
int k = 3; // Subarray size
int n = sizeof(arr) / sizeof(arr[0]);
int max_sum = maxSubarraySum(arr, n, k);
printf("Maximum sum of subarray of size %d: %d\n", k, max_sum);
return 0;
}
Maximum sum of subarray of size 3: 19
¶DynamicSize Sliding Window
A dynamicsize sliding window is useful when the problem requires finding subarrays or substrings that satisfy certain conditions, which may cause the window size to change dynamically.
Consider a string and we have to find the length of the longest substring without repeating characters.
To solve this problem, we will again slide a window across the string. This window represents the current substring we’re considering. Unlike the previous example where we calculated sums, we’re interested in finding the longest substring that contains all unique characters. Using a data structure like a hash table (or a simple array for smaller character sets), we’ll keep track of the characters within the window. This allows us to efficiently check if a character has already appeared in the current substring.
As we slide the window:

Element Leaving the Window: If the character leaving the window (the one at the leftmost position) already exists in the data structure, it means the current substring is no longer unique. We remove this character from the data structure.

Element Entering the Window: Add the character entering the window (the one at the rightmost position) to the data structure.

Track the Maximum Length: In each iteration, we check the current window’s length (right index minus left index plus 1). If this length is greater than the currently stored maximum length, we update the maximum length.
This approach has a time complexity of O(n)
. This is significantly faster than checking every possible substring using nested loops.
#include <stdio.h>
#include <stdbool.h> // for boolean values
int longestUniqueSubstr(char str[], int n) {
int left = 0, right = 0;
int max_length = 0;
// Use an array to track character presence (can replace with a hash table)
bool char_present[256] = {false}; // Assuming ASCII characters
while (right < n) {
// Check if character already present (repeated)
if (char_present[str[right]]) {
// Slide the window until the repeating character is removed
while (str[left] != str[right]) {
char_present[str[left]] = false; // Mark character leaving the window
left++;
}
// Move left pointer one more to exclude the repeated character
left++;
}
char_present[str[right]] = true; // Mark character entering the window
// Update maximum length if necessary
max_length = (right  left + 1) > max_length ? (right  left + 1) : max_length;
right++; // Slide the window by one
}
return max_length;
}
int main() {
char str[] = "abcabcbb";
int length = longestUniqueSubstr(str, 8);
printf("Length of the longest unique substring: %d\n", length);
return 0;
}
Length of the longest unique substring: 3
¶Applications of the Sliding Window Technique
The Sliding Window Technique is versatile and finds applications in various domains:
Natural Language Processing: sliding window is used to extract features or ngrams from text data.
Image Processing: sliding window is used to extract features from different parts of an image. Also used in detecting objects in image by sliding a window across the image and applying a classifier.
Bioinformatics: DNA Sequence Analysis: Analyze DNA sequences to find regions with specific characteristics, like high GC content or motifs.
Signal Processing: Analyze timeseries data to capture local patterns, trends, or anomalie. Also sliding window is used to smooth signals and reduce noise.
Array and String Manipulation:
 Maximum/Minimum Subarray Sum: Efficiently find the subarray with the maximum or minimum sum.
 Longest Substring Without Repeating Characters: Identify the longest substring with all unique characters.
 Anagram Checks: Check for anagrams within a string by maintaining a frequency count in a sliding window.
Data Compression: in LZ77 Algorithm
a sliding window is used to detect repeated patterns and replace them with references to previous occurrences, leading to data compression.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Learn the Sliding Window technique and how to use it. Reduce the time complexity of problems from O(n^2) to O(n) by using the sliding window approach, avoiding nested loops, and optimizing your algorithm designs.
Introduction to Binary Search with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
14

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development