Sliding Window Technique
In this page:
Sliding Window Idea
A sliding window keeps track of a contiguous range of elements and moves that range across the array or string instead of recomputing everything from scratch each time, which avoids a lot of repeated work compared to a naive nested-loop approach.
Example: Sliding Window Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9};
int k = 3;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i]; // build the first window once
cout << "First window sum: " << windowSum << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int k = 3, windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
System.out.println("First window sum: " + windowSum);
}
}arr = [1, 3, 5, 7, 9]
k = 3
window_sum = sum(arr[:k]) # build the first window once
print("First window sum:", window_sum)#include <stdio.h>
int main() {
int arr[] = {1, 3, 5, 7, 9};
int k = 3, windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
printf("First window sum: %d\n", windowSum);
return 0;
}Login to try C/C++/Java code in the editor
Fixed-size Window
A fixed-size window always spans exactly k elements: as it slides one step forward, you add the new element entering on the right and remove the one leaving on the left, updating your running result in O(1) per step instead of recalculating the whole window.
Example: Fixed-size Window
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3, n = 6;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k]; // add entering, remove leaving: O(1)/step
if (windowSum > maxSum) maxSum = windowSum;
}
cout << "Max sum of window size " << k << ": " << maxSum << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 1, 5, 1, 3, 2};
int k = 3, windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
if (windowSum > maxSum) maxSum = windowSum;
}
System.out.println("Max sum of window size " + k + ": " + maxSum);
}
}arr = [2, 1, 5, 1, 3, 2]
k = 3
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # add entering, remove leaving: O(1)/step
max_sum = max(max_sum, window_sum)
print(f"Max sum of window size {k}:", max_sum)#include <stdio.h>
int main() {
int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3, n = 6, windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k];
if (windowSum > maxSum) maxSum = windowSum;
}
printf("Max sum of window size %d: %d\n", k, maxSum);
return 0;
}Login to try C/C++/Java code in the editor
Distinct Elements in Window
Sliding a window while tracking a frequency map lets you answer questions like 'how many distinct values are in this window' efficiently, since you only need to update the counts for the one element entering and the one leaving.
Example: Distinct Elements in Window
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int arr[] = {1, 2, 1, 3, 2};
int k = 3;
unordered_map<int, int> freq;
for (int i = 0; i < k; i++) freq[arr[i]]++;
cout << "Distinct in first window: " << freq.size() << endl;
return 0;
}import java.util.HashMap;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 1, 3, 2};
int k = 3;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < k; i++) freq.merge(arr[i], 1, Integer::sum);
System.out.println("Distinct in first window: " + freq.size());
}
}arr = [1, 2, 1, 3, 2]
k = 3
freq = {}
for x in arr[:k]:
freq[x] = freq.get(x, 0) + 1
print("Distinct in first window:", len(freq))#include <stdio.h>
int main() {
int arr[] = {1, 2, 1, 3, 2};
int k = 3;
int seen[10] = {0}, distinct = 0;
for (int i = 0; i < k; i++) {
if (seen[arr[i]] == 0) distinct++;
seen[arr[i]]++;
}
printf("Distinct in first window: %d\n", distinct);
return 0;
}Login to try C/C++/Java code in the editor
Variable-size Window
A variable-size window grows by moving its right edge forward and shrinks by moving its left edge forward, expanding while some condition holds and contracting once it's violated, which is the classic pattern for 'longest substring with X property' problems.
Example: Variable-size Window
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 1, 5, 2, 3, 2};
int target = 7, n = 6;
int left = 0, sum = 0, minLen = 100;
for (int right = 0; right < n; right++) {
sum += arr[right]; // expand right
while (sum >= target) {
if (right - left + 1 < minLen) minLen = right - left + 1;
sum -= arr[left]; // shrink left
left++;
}
}
cout << "Smallest subarray length with sum >= " << target << ": " << minLen << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 1, 5, 2, 3, 2};
int target = 7;
int left = 0, sum = 0, minLen = 100;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= arr[left];
left++;
}
}
System.out.println("Smallest subarray length with sum >= " + target + ": " + minLen);
}
}arr = [2, 1, 5, 2, 3, 2]
target = 7
left = total = 0
min_len = float("inf")
for right in range(len(arr)):
total += arr[right] # expand right
while total >= target:
min_len = min(min_len, right - left + 1)
total -= arr[left] # shrink left
left += 1
print(f"Smallest subarray length with sum >= {target}:", min_len)#include <stdio.h>
int main() {
int arr[] = {2, 1, 5, 2, 3, 2};
int target = 7, n = 6, left = 0, sum = 0, minLen = 100;
for (int right = 0; right < n; right++) {
sum += arr[right];
while (sum >= target) {
if (right - left + 1 < minLen) minLen = right - left + 1;
sum -= arr[left];
left++;
}
}
printf("Smallest subarray length with sum >= %d: %d\n", target, minLen);
return 0;
}Login to try C/C++/Java code in the editor
Sliding Window Practice
Sliding window is most useful for problems about contiguous subarrays or substrings, like maximum sum of size k or longest substring without repeats. The main things to get right are exactly when to move each pointer and how to update your tracked result as you go.
Example: Sliding Window Practice
#include <iostream>
using namespace std;
int main() {
// Longest substring without repeating chars (window over indices)
string s = "abcabcbb";
int freq[256] = {0};
int left = 0, maxLen = 0;
for (int right = 0; right < (int)s.size(); right++) {
freq[(int)s[right]]++;
while (freq[(int)s[right]] > 1) {
freq[(int)s[left]]--;
left++;
}
if (right - left + 1 > maxLen) maxLen = right - left + 1;
}
cout << "Longest substring without repeats: " << maxLen << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String s = "abcabcbb";
int[] freq = new int[256];
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
freq[s.charAt(right)]++;
while (freq[s.charAt(right)] > 1) {
freq[s.charAt(left)]--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
System.out.println("Longest substring without repeats: " + maxLen);
}
}s = "abcabcbb"
seen = {}
left = max_len = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
max_len = max(max_len, right - left + 1)
print("Longest substring without repeats:", max_len)#include <stdio.h>
#include <string.h>
int main() {
char s[] = "abcabcbb";
int freq[256] = {0};
int left = 0, maxLen = 0, n = strlen(s);
for (int right = 0; right < n; right++) {
freq[(unsigned char)s[right]]++;
while (freq[(unsigned char)s[right]] > 1) {
freq[(unsigned char)s[left]]--;
left++;
}
if (right - left + 1 > maxLen) maxLen = right - left + 1;
}
printf("Longest substring without repeats: %d\n", maxLen);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: