Sliding Window तकनीक

एक sliding window एक छोटे picture frame को photos की एक लंबी strip के साथ move करने जैसा है, एक समय में सिर्फ कुछ देखते हुए और इसे एक step आगे slide करते हुए।

In this page:

Sliding Window Idea
Fixed-size Window
Distinct Elements in Window
Variable-size Window
Sliding Window Practice

Syntax

markup

window_sum = sum(arr[:k])
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i - k]   # slide the window
    best = max(best, window_sum)

Sliding Window Idea

एक sliding window elements की एक contiguous range track करता है और हर बार scratch से सब कुछ recompute करने के बजाय उस range को array या string में move करता है, जो एक naive nested-loop approach की तुलना में बहुत सारा repeated work avoid करता है।

उदाहरण: 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;
}

Fixed-size Window

एक fixed-size window हमेशा बिल्कुल k elements span करती है: जैसे यह एक step आगे slide होती है, आप दाईं ओर आने वाले नए element को जोड़ते हैं और बाईं ओर जाने वाले को हटाते हैं, पूरी window recalculate करने के बजाय अपना running result O(1) per step में update करते हुए।

उदाहरण: 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;
}

Distinct Elements in Window

एक frequency map track करते हुए एक window slide करना आपको efficiently सवालों का जवाब देने देता है जैसे 'इस window में कितनी distinct values हैं', क्योंकि आपको सिर्फ entering और leaving वाले एक element के counts update करने हैं।

उदाहरण: 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;
}

Variable-size Window

एक variable-size window इसका right edge आगे move करके बढ़ती है और इसका left edge आगे move करके सिकुड़ती है, किसी condition के true होने तक expanding और violated होने पर contracting, जो 'longest substring with X property' problems के लिए classic pattern है।

उदाहरण: 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;
}

Sliding Window Practice

Sliding window contiguous subarrays या substrings के बारे में problems के लिए सबसे उपयोगी है, जैसे size k का maximum sum या बिना repeats वाला longest substring। सही पाने वाली मुख्य चीज़ें बिल्कुल हैं कि हर pointer कब move करना है और आगे बढ़ते हुए अपना tracked result कैसे update करना है।

उदाहरण: 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;
}

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Multi-dimensional Arrays Next Lesson → Two Pointer Technique