Arrays January 01 ,2026

1. Sliding Window Technique –

Sliding Window Technique –

Introduction

The Sliding Window Technique is an optimization strategy used to process a contiguous subset (window) of elements in an array or string. Instead of recalculating values for every possible subarray, the window slides across the data structure while maintaining required information.

This technique significantly reduces time complexity from O(n²) to O(n) in many problems involving subarrays or substrings.

Why Sliding Window?

Many problems require:

Finding maximum or minimum values in subarrays
Counting valid subarrays or substrings
Maintaining a running condition over contiguous elements

A brute-force approach checks all possible windows, leading to inefficiency. Sliding Window optimizes this by reusing previous computations.

When to Use Sliding Window

Use Sliding Window when:

The problem involves contiguous subarrays or substrings
You need to maintain a running condition
The window can grow or shrink based on constraints
Repeated recalculation of overlapping subarrays exists

Types of Sliding Window

Fixed Size Window

The window size remains constant throughout the process.

Examples:

Maximum sum of subarray of size K
Average of subarrays of size K

Variable Size Window

The window size changes dynamically based on conditions.

Examples:

Longest substring without repeating characters
Smallest subarray with sum ≥ K

Fixed Size Sliding Window – Concept

Problem Example

Find the maximum sum of a subarray of size K.

Illustration

Array:  [2, 1, 5, 1, 3, 2]
K = 3

Window 1: [2, 1, 5] → Sum = 8
Window 2: [1, 5, 1] → Sum = 7
Window 3: [5, 1, 3] → Sum = 9  ← Maximum
Window 4: [1, 3, 2] → Sum = 6

Algorithm – Fixed Window

Compute sum of first K elements
Slide window by:
- Subtracting the element leaving the window
- Adding the new element entering the window
Track maximum sum

Fixed Size Window Implementation

C++ Code

#include 
#include 
using namespace std;

int maxSumSubarray(vector& arr, int k) {
    int windowSum = 0, maxSum = 0;

    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    maxSum = windowSum;

    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

int main() {
    vector arr = {2, 1, 5, 1, 3, 2};
    int k = 3;
    cout << maxSumSubarray(arr, k);
    return 0;
}

Output

C Code

#include 

int maxSumSubarray(int arr[], int n, int k) {
    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];
        if (windowSum > maxSum)
            maxSum = windowSum;
    }

    return maxSum;
}

int main() {
    int arr[] = {2, 1, 5, 1, 3, 2};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("%d", maxSumSubarray(arr, n, k));
    return 0;
}

Output

Java Code

class SlidingWindow {
    static int maxSumSubarray(int[] arr, int k) {
        int 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];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSumSubarray(arr, k));
    }
}

Output

Python Code

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

arr = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(arr, k))

Output

C# Code

using System;

class Program {
    static int MaxSumSubarray(int[] arr, int k) {
        int 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];
            maxSum = Math.Max(maxSum, windowSum);
        }

        return maxSum;
    }

    static void Main() {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        Console.WriteLine(MaxSumSubarray(arr, k));
    }
}

Output

JavaScript Code

function maxSumSubarray(arr, k) {
    let windowSum = 0;

    for (let i = 0; i < k; i++)
        windowSum += arr[i];

    let maxSum = windowSum;

    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

let arr = [2, 1, 5, 1, 3, 2];
let k = 3;
console.log(maxSumSubarray(arr, k));

Output

Variable Size Sliding Window –

In variable window problems:

Window expands by moving the right pointer
Window shrinks by moving the left pointer
Goal is to maintain a condition

Example

Smallest subarray with sum ≥ K

Problem Statement

Find the smallest subarray length whose sum is greater than or equal to a given value K.

Concept Explanation

In variable-size sliding window problems:

The window expands by moving the right pointer
The window shrinks by moving the left pointer
The goal is to maintain a valid condition while minimizing or maximizing a metric

Unlike fixed-size windows, the window size is not predefined.

Illustration (Language Independent)

Array: [2, 1, 5, 2, 3, 2]
K = 7

Window expansion:
[2] → sum = 2
[2,1] → sum = 3
[2,1,5] → sum = 8 (valid)

Now shrink:
[1,5] → sum = 6 (invalid)

Continue expanding:
[1,5,2] → sum = 8 (valid)

Algorithm

Initialize left = 0, sum = 0, minLength = infinity
Iterate right from 0 to n-1
Add arr[right] to sum
While sum >= K:
- Update minLength
- Subtract arr[left] from sum
- Increment left
Return minLength

C++ Code

#include 
#include 
#include 
using namespace std;

int minSubArrayLen(int k, vector& arr) {
    int left = 0, sum = 0, minLen = INT_MAX;

    for (int right = 0; right < arr.size(); right++) {
        sum += arr[right];

        while (sum >= k) {
            minLen = min(minLen, right - left + 1);
            sum -= arr[left++];
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

int main() {
    vector arr = {2, 1, 5, 2, 3, 2};
    cout << minSubArrayLen(7, arr);
    return 0;
}

Output

Python Code

def min_subarray_len(k, arr):
    left = 0
    curr_sum = 0
    min_len = float('inf')

    for right in range(len(arr)):
        curr_sum += arr[right]

        while curr_sum >= k:
            min_len = min(min_len, right - left + 1)
            curr_sum -= arr[left]
            left += 1

    return 0 if min_len == float('inf') else min_len

arr = [2, 1, 5, 2, 3, 2]
print(min_subarray_len(7, arr))

Output

(Logic is identical in Java, C, C#, and JavaScript.)

Time and Space Complexity

Type	Time	Space
Fixed Window	O(n)	O(1)
Variable Window	O(n)	O(1)

Common Mistakes

Forgetting to shrink the window
Using sliding window for non-contiguous problems
Ignoring negative numbers where sliding window may fail
Incorrect window initialization

Sliding Window with HashMap

Problem Example

Find the longest substring without repeating characters.

Core Idea

Use a hashmap to store character frequency
Expand window until duplicate appears
Shrink window until condition is restored

Algorithm

Initialize left = 0
Use a hashmap to track character counts
Expand right pointer
If duplicate exists:
- Shrink from left
Track maximum window size

Java Implementation

import java.util.HashMap;

public class LongestUniqueSubstring {
    public static int longestUniqueSubstring(String s) {
        HashMap map = new HashMap<>();
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            map.put(ch, map.getOrDefault(ch, 0) + 1);

            while (map.get(ch) > 1) {
                char leftChar = s.charAt(left);
                map.put(leftChar, map.get(leftChar) - 1);
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestUniqueSubstring("abcabcbb"));
    }
}

Output

C++ Implementation

#include 
#include 
using namespace std;

int longestUniqueSubstring(string s) {
    unordered_map mp;
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        mp[s[right]]++;

        while (mp[s[right]] > 1) {
            mp[s[left]]--;
            left++;
        }

        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    cout << longestUniqueSubstring("abcabcbb");
    return 0;
}

Output

Python Implementation

def longest_unique_substring(s):
    freq = {}
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1

        while freq[s[right]] > 1:
            freq[s[left]] -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

print(longest_unique_substring("abcabcbb"))

Output

Sliding Window vs Prefix Sum

Aspect	Sliding Window	Prefix Sum
Best for	Single-pass contiguous problems	Multiple range queries
Space	O(1)	O(n)
Handles negatives	Limited	Yes
Query speed	O(n)	O(1)
Dynamic window	Yes	No

Sliding Window vs Two Pointers

Aspect	Sliding Window	Two Pointers
Window based	Yes	No
Always contiguous	Yes	No
Typical use	Subarrays / substrings	Pairs / comparisons
Complexity	O(n)	O(n)

Common Interview Problems on Sliding Window

Maximum sum subarray of size K
Smallest subarray with sum ≥ K
Longest substring without repeating characters
Longest substring with at most K distinct characters
Count of subarrays with product less than K
Minimum window substring

Practice Problems

Problem 1

Find the maximum number of vowels in a substring of size K.

Problem 2

Count the number of subarrays with sum less than K.

Problem 3

Find the longest substring with at most two distinct characters.

Problem 4

Find the minimum window substring containing all characters of another string.

Interview Tips

Sliding window only works on contiguous data
Be cautious with negative numbers
Always identify whether window is fixed or variable
Often combined with hashmaps

Summary

The Sliding Window Technique is a critical optimization approach for solving problems involving contiguous subarrays or substrings. By dynamically maintaining a window and updating values incrementally, it eliminates redundant computations and achieves linear time complexity.

Understanding both fixed-size and variable-size sliding window patterns, along with hashmap integration, enables efficient solutions to a wide range of real-world and interview problems. Sliding window frequently works alongside techniques such as Two Pointers and Prefix Sum, making it an essential part of any algorithmic toolkit.

Mastery of this technique significantly enhances problem-solving efficiency and is indispensable for competitive programming and technical interviews.

Next Blog-

Basics of Hashing for Arrays

Sanjiv

You must logged in to post comments.

JavaScript Arrays

Data Structure

Data Structure

Table of Contents

Sliding Window Technique –

Introduction

Why Sliding Window?

When to Use Sliding Window

Types of Sliding Window

Fixed Size Window

Variable Size Window

Fixed Size Sliding Window – Concept

Problem Example

Illustration

Algorithm – Fixed Window

Fixed Size Window Implementation

C++ Code

C Code

Java Code

Python Code

C# Code

JavaScript Code

Variable Size Sliding Window –

Example

Problem Statement

Concept Explanation

Illustration (Language Independent)

Algorithm

C++ Code

Python Code

Time and Space Complexity

Common Mistakes

Sliding Window with HashMap

Problem Example

Core Idea

Algorithm

Java Implementation

Output

C++ Implementation

Output

Python Implementation

Output

Sliding Window vs Prefix Sum

Sliding Window vs Two Pointers

Common Interview Problems on Sliding Window

Practice Problems

Problem 1

Problem 2

Problem 3

Problem 4

Interview Tips

Summary

Next Blog-

Related Blogs

Find the Second Smal...

Array Data Structure

Array Memory Represe...

Array Operations and...

Advantages and Disad...

Arrays in C

Vector in C++ STL

Arrays vs ArrayList...

JavaScript Arrays

Binary Search on Arr...

Two Pointers Techniq...

Prefix Sum Technique

Basics of Hashing fo...

Traverse an Array

Find the Sum of All...

Find the Maximum Ele...

Find the Minimum Ele...

Count Even and Odd N...

Search an Element in...

Copy One Array into...

Reverse an Array

Print Alternate Elem...

Find the Length of a...

Check if an Array is...

Find the First Eleme...

Find the Last Elemen...

Count the Number of...