Sliding Windows

Navneet KumarNavneet Kumar
15 min read

Utility of sliding window

  1. SUBARRAY =[1] [1, 2] [1, 2, 3] [1, 2, 3, 4] [1, 2, 3, 4, 5] [2] [2, 3] [2, 3, 4] [2, 3, 4, 5] [3] [3, 4] [3, 4, 5] [4] [4, 5] [5] ye sare sabarray hai iske

  2. SUBSTINGS

  3. TYPES: K SIZE/VARIABLE SIZED

jaha de rakha ho k size ka arrya hai or size banatana ho something to ham sliding windows use karte hai

Ab question karte hai like
Maximum sum Subarray of size k(mujhe aasa subarray nekalana hai jiska size max ho in k value matlb k=3 to 3 size ke kitani array hai )

pehlae ham isko broutfrose se karte hai acche se ok
1. Package aur Class Declaration

javaCopy codepackage Slidingwindow;

public class MaximumsumSubarraysizek {
  • package Slidingwindow; – Yeh code ek package ke andar likha gaya hai jiska naam hai Slidingwindow.

  • public class MaximumsumSubarraysizek – Yeh class ka naam hai, jisme pura logic likha gaya hai.


2. main Method Start

javaCopy codepublic static void main(String[] args) {
  • Java ka entry point hota hai main method.

  • Yahin se program chalna start karta hai.


3. Array aur Variables Initialization

javaCopy codeint[] arr = {10, 20, 1, 3, -40, 80, 10};
int k = 2;
int n = arr.length;
int maxsum = 0;
  • arr → Input array diya gaya hai.

  • k = 2 → Yeh batata hai ki hume kitne size ki subarray ka maximum sum chahiye.

  • n = arr.length → Array ka length nikal rahe hain.

  • maxsum = 0 → Yeh variable hume final answer dega (maximum sum of subarray of size k).


4. Outer Loop – Subarray Start Index

javaCopy codefor (int i = 0; i < n - k + 1; i++) {
  • Yeh loop har possible subarray of size k ke starting index i ko cover karega.

  • n - k + 1 tak isliye ja rahe hain, taaki i + k - 1 array ke bounds ke bahar na chala jaye.


5. Inner Loop – Subarray Sum Calculation

javaCopy codeint sum = 0;
for (int j = i; j < i + k; j++) {
    sum += arr[j];
}
  • Har outer loop ke iteration pe, yeh inner loop ek subarray banata hai starting at i aur length k.

  • sum variable mein us subarray ke elements ka total add kiya ja raha hai.


6. Maximum Sum Update

javaCopy codemaxsum = Math.max(maxsum, sum);
  • Har subarray ke baad check kar rahe hain ki kya yeh sum ab tak ke maximum se bada hai.

  • Agar haan, to maxsum update kar diya jata hai.

  • ye hai iske time complexcity hai k squar to ye bahut gandi hai caho to im improve kar sakteahi with the help of Sliding Windows

  • Agar chaho to mai isko optimized sliding window version mein bhi aur ache se explain kar sakta hoon.

To ab ham Sliding Windows use karege ok two pointer use karege or uske baad ham jab ye chalayenge to ye hamko us hee time sum nekal lennge wahi per to seen kay hoga to ham

Two consecutive windown of size ‘K‘ have ‘K-1‘ element commen to iske leye ham ek fromula lagayegnge sum = sum-arr[i-1] + arr[i]

🔄 Sliding Window Concept:

✅ Basic Idea:

Agar aapko size k ke sabhi subarrays ka sum nikalna hai, to har baar naye se k elements ka sum nikalna time-consuming hai (O(n*k)).

Lekin, agar hum notice karein to:

Two consecutive subarrays of size k have k-1 elements in common.

🤔 Example:

Array: [10, 20, 30, 40]
Size k = 2

Subarrays:

  • [10, 20] → sum = 30

  • [20, 30] → sum = 50

  • [30, 40] → sum = 70

Notice:

  • [10, 20] → [20, 30] mein 20 common hai

  • So next sum = previous sum - 10 (jo pehla tha) + 30 (jo naya aaya)


✍️ Formula:

javaCopy codesum = sum - arr[i - 1] + arr[j];

📌 Meaning:

  • arr[i - 1] → Pehle window ka pehla element (jo ab nikal gaya hai)

  • arr[j] → Naya element jo ab window mein aaya hai

  • Is tarah se hum O(1) time mein next window ka sum nikal lete hain


✅ Code Explanation Line by Line:

javaCopy codeint i = 0, j = k - 1, sum = 0;
  • i → window ka start index

  • j → window ka end index (pehla window k-1 tak jaata hai)

  • sum → pehle window ka total sum nikalne ke liye

javaCopy codefor (int a = i; a <= j; a++) {
    sum += arr[a];
}
  • Yeh loop pehle window ke k elements ka sum nikalta hai
javaCopy codei++; 
j++;
  • Ab window ko ek step aage slide kar rahe hain
javaCopy codewhile (j < n) {
    sum = sum - arr[i - 1] + arr[j];
    // yahan pe max sum bhi update karna chahiye
    i++;
    j++;
}
  • Har baar sum ko update kar rahe hain purani value hata ke aur nayi value add karke

  • Window slide ho raha hai left to right

  • Dono i aur j ek ek step aage badh rahe hain


🧾 Final Notes:

  • Ye approach ka time complexity: O(n) (fast and efficient)

  • Har window ka sum ek hi baar calculate ho raha hai

  • No nested loop → zyada fast

  • Real-time sum update ho raha hai


✅ Sample Final Code:

javaCopy codeint[] arr = {10, 20, 1, 3, -40, 80, 10};
int k = 2;
int n = arr.length;

int i = 0, j = k - 1, sum = 0;
for (int a = i; a <= j; a++) {
    sum += arr[a];
}

int maxSum = sum;

i++;
j++;
while (j < n) {
    sum = sum - arr[i - 1] + arr[j];
    maxSum = Math.max(maxSum, sum);
    i++;
    j++;
}

System.out.println("Maximum sum of subarray of size " + k + " is: " + maxSum);TO ab ek qusestion karege uske aawg

To ab ham ek question karege leetcode 1493 uska naam hai or fir ham dekhnge ke ye kaam kase karta hai hot akay isame

🧠 Intuition (Sochne ka Tareeka)

Problem:

Given an array of 0s and 1s, return the length of the longest subarray consisting only of 1s after deleting exactly one element (which must be a 0 or 1).


🔍 Example Se Samajhte Hain

Input:

arr = [1, 1, 0, 1, 1, 1, 0, 1, 1]

Expected Output:

code6  (delete one `0`, e.g. the first 0 at index 2)

🪜 Tumhara Approach (Brute-ish)

Step-by-Step 🔍:

  1. Pehla check — count karo kitne 0s hai:

     int z = 0;
     for (int ele : arr) {
         if (ele == 0) z++;
     }
     if (z == 0) return n - 1;
    

    🧠 Logic: Agar saare 1s hain, to 1 element delete karna hi padega (question ki condition hai), so answer is n-1.

  2. Sliding Window-like process:

    • Start from first non-zero element

    • Traverse while tracking at most 1 zero in window

    • Jaise hi 2nd zero milta hai, window ko shift karo

Tumne ye part manually kiya hai:

     while (j < n) {
        if (arr[j] == 1) j++;
        else {
            if (zeroes == 0) {
                j++;
                zeroes++;
            } else {
                int len = j - i - 1;
                maxLen = Math.max(maxLen, len);
                j++;
                while (i < n && arr[i] == 1) {
                    i++;
                }
            }
        }

        if (zeroes == 1) {
            int len = j - i - 1;
            maxLen = Math.max(maxLen, len);
        }
    }

🧠 Ye logic sahi direction mein hai — tum ek zero ko allow kar rahe ho, aur second zero aate hi left side se window ko adjust kar rahe ho.


📉 Limitation (Why It's Brute-Force-ish)

  1. Tumhara while(i < n && arr[i] == 1) part kaafi manual hai, aur kuch unnecessary calculations ho rahe hain.

  2. Har bar jab 2nd zero milta hai, tum window ko slow way mein shift kar rahe ho — sliding window ka essence yahan thoda miss ho raha hai.

🔸 Java Code (Brute Force)

public class BruteForceLongestSubarray {
    public static int longestSubarray(int[] nums) {
        int maxLen = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int zeroCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) zeroCount++;
                if (zeroCount > 1) break;  // Only 1 zero allowed

                // Length of subarray after deleting 1 element
                int len = j - i + 1;
                maxLen = Math.max(maxLen, len);
            }
        }

        // Since we must delete one element
        return maxLen - 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 0, 1, 1};
        System.out.println("Longest Subarray: " + longestSubarray(arr));
    }
}

🔹 C++ Code (Brute Force)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestSubarray(vector<int>& nums) {
    int maxLen = 0;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        int zeroCount = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 0) zeroCount++;
            if (zeroCount > 1) break;

            int len = j - i + 1;
            maxLen = max(maxLen, len);
        }
    }

    return maxLen - 1;  // One deletion required
}

int main() {
    vector<int> arr = {1, 1, 0, 1, 1};
    cout << "Longest Subarray: " << longestSubarray(arr) << endl;
    return 0;
}

🔸 Python Code (Brute Force)

def longest_subarray(nums):
    max_len = 0
    n = len(nums)

    for i in range(n):
        zero_count = 0
        for j in range(i, n):
            if nums[j] == 0:
                zero_count += 1
            if zero_count > 1:
                break
            max_len = max(max_len, j - i + 1)

    return max_len - 1  # Deleting one element

# Example test
arr = [1, 1, 0, 1, 1]
print("Longest Subarray:", longest_subarray(arr))

🧪 Sample Input & Output:

Input:  [1, 1, 0, 1, 1]
Output: 4
Explanation: Remove the 0 at index 2, resulting in [1,1,1,1]

📝 Time Complexity:

  • Time: O(n²)

  • Space: O(1)

✅ Java – Optimized Sliding Window

public class LongestSubarrayAfterDeletingOne {
    public static int longestSubarray(int[] nums) {
        int left = 0, zeroCount = 0, maxLen = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeroCount++;

            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }

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

        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 0, 1, 1, 1, 0, 1};
        System.out.println("Longest Subarray: " + longestSubarray(arr)); // Output: 5
    }
}

🔹 C++ – Optimized Sliding Window

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestSubarray(vector<int>& nums) {
    int left = 0, zeroCount = 0, maxLen = 0;

    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] == 0) zeroCount++;

        while (zeroCount > 1) {
            if (nums[left] == 0) zeroCount--;
            left++;
        }

        maxLen = max(maxLen, right - left);
    }

    return maxLen;
}

int main() {
    vector<int> arr = {1, 1, 0, 1, 1, 1, 0, 1};
    cout << "Longest Subarray: " << longestSubarray(arr) << endl; // Output: 5
    return 0;
}

🔸 Python – Optimized Sliding Window

def longest_subarray(nums):
    left = 0
    zero_count = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        max_len = max(max_len, right - left)

    return max_len

# Example Test
arr = [1, 1, 0, 1, 1, 1, 0, 1]
print("Longest Subarray:", longest_subarray(arr))  # Output: 5

🧠 Why right - left?

Because we must delete one element, so when the window has at most one 0, the real length of pure 1's is (right - left) — not (right - left + 1).


🕐 Time and Space Complexity

MetricValue
TimeO(n)
SpaceO(1)

AB Ham leetcode ka 1004 karege

ye aap log try karo nahi huaa to last mai saluction hai iska ok

Avb ham jo karege vo 1052 leetcode💕💕

🔍 Problem Summary (in simple terms):

You're given two arrays:

  • customers[i]: Number of customers entering the store at minute i.

  • grumpy[i]: Whether the shopkeeper is grumpy (1 = grumpy, 0 = not grumpy) at minute i.

If the owner is not grumpy, customers are satisfied.
If the owner is grumpy, customers are not satisfied.

👉 The owner has a secret technique that lets them stay not grumpy for k consecutive minutes, but only once.

🧠 Goal: Use this trick wisely once to maximize the total number of satisfied customers.

✅ Intuition and Approach of the Given Java Solution

💡 Key Idea:

  • Some customers are always satisfied (when grumpy[i] == 0).

  • Some customers are only satisfied if we apply the trick in their minute.

  • So we want to find the best window of k minutes where the trick has the maximum positive impact.

🔄 Step-by-step:

  1. Calculate the number of unsatisfied customers in the first k minutes (if owner was grumpy).

  2. Use a sliding window to check every k-minute block in the day:

    • Add new grumpy customer count coming in.

    • Subtract the grumpy one going out.

    • Keep track of the window that saves the most customers.

  3. In that best window, temporarily make grumpy = 0.

  4. Recalculate the total satisfied customers (now including that improved window).


🧾 Code in Java (Given):

class Solution {
    public int maxSatisfied(int[] arr, int[] grumpy, int k) {
        int n = arr.length;
        int unsatisfied = 0;

        // Calculate initial window [0...k-1]
        for (int x = 0; x < k; x++) {
            if (grumpy[x] == 1) {
                unsatisfied += arr[x];
            }
        }

        int maxUnsatisfied = unsatisfied;
        int a = 0, b = k - 1;

        // Sliding window from k to n-1
        for (int i = 1; i + k - 1 < n; i++) {
            int j = i + k - 1;

            if (grumpy[j] == 1) unsatisfied += arr[j];
            if (grumpy[i - 1] == 1) unsatisfied -= arr[i - 1];

            if (unsatisfied > maxUnsatisfied) {
                maxUnsatisfied = unsatisfied;
                a = i;
                b = j;
            }
        }

        // Apply technique in best window
        for (int x = a; x <= b; x++) {
            grumpy[x] = 0;
        }

        // Count satisfied customers
        int satisfied = 0;
        for (int x = 0; x < n; x++) {
            if (grumpy[x] == 0) {
                satisfied += arr[x];
            }
        }

        return satisfied;
    }
}

🐍 Python Version

class Solution:
    def maxSatisfied(self, customers, grumpy, k):
        n = len(customers)
        unsatisfied = 0

        for i in range(k):
            if grumpy[i] == 1:
                unsatisfied += customers[i]

        max_unsatisfied = unsatisfied
        a, b = 0, k - 1

        for i in range(1, n - k + 1):
            j = i + k - 1

            if grumpy[j] == 1:
                unsatisfied += customers[j]
            if grumpy[i - 1] == 1:
                unsatisfied -= customers[i - 1]

            if unsatisfied > max_unsatisfied:
                max_unsatisfied = unsatisfied
                a, b = i, j

        for i in range(a, b + 1):
            grumpy[i] = 0

        satisfied = 0
        for i in range(n):
            if grumpy[i] == 0:
                satisfied += customers[i]

        return satisfied

💻 C++ Version

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int k) {
        int n = customers.size();
        int unsatisfied = 0;

        for (int i = 0; i < k; ++i) {
            if (grumpy[i] == 1) {
                unsatisfied += customers[i];
            }
        }

        int maxUnsatisfied = unsatisfied, a = 0, b = k - 1;

        for (int i = 1; i + k - 1 < n; ++i) {
            int j = i + k - 1;
            if (grumpy[j] == 1) unsatisfied += customers[j];
            if (grumpy[i - 1] == 1) unsatisfied -= customers[i - 1];

            if (unsatisfied > maxUnsatisfied) {
                maxUnsatisfied = unsatisfied;
                a = i;
                b = j;
            }
        }

        for (int i = a; i <= b; ++i) {
            grumpy[i] = 0;
        }

        int satisfied = 0;
        for (int i = 0; i < n; ++i) {
            if (grumpy[i] == 0) {
                satisfied += customers[i];
            }
        }

        return satisfied;
    }
};

🚀 Time and Space Complexity

  • Time Complexity: O(n) – single pass for each of:

    • Initial window

    • Sliding window

    • Final satisfaction count

  • Space Complexity: O(1) – we use only constant extra space (not counting input arrays)

✅ 🔍 Problem Summary (Hinglish): Tumhare paas: Ek array of fruits hai, jisme fruits[i] batata hai ki i-th tree kaunsa fruit de raha hai (fruit type).

Example: fruits = [1, 2, 1, 3, 4]

Rules: Tumhare paas sirf 2 baskets hain.

Har basket sirf ek type ka fruit rakh sakti hai.

Basket mein fruit ki quantity ka koi limit nahi hai.

Tum kisi bhi tree se start kar sakte ho, lekin tumhe continuously right side mein move karna hai.

Har tree se exactly 1 fruit uthana padega.

Agar kisi tree ka fruit tumhare 2 baskets ke types se alag hai (yaani third type), toh wahiin pe ruk jana hoga.

🎯 Goal: Tumhe ye batana hai ki maximum kitne fruits continuously uthaye ja sakte hain (starting from any tree and moving right).

✅ Examples Explained: Example 1: text Copy Edit Input: fruits = [1, 2, 1] Tum start karo 0 se → 1 (basket1), 2 (basket2), 1 (basket1)

Dono baskets use ho gayi aur sab fruits inhi types ke hain.

✅ Answer: 3

Example 2: text Copy Edit Input: fruits = [0, 1, 2, 2] Tum start karo index 1 se → 1 (basket1), 2 (basket2), 2 (basket2)

✅ Answer: 3 fruits collect kiye: [1,2,2]

Example 3: text Copy Edit Input: fruits = [1, 2, 3, 2, 2] Best option: Start from index 1 → [2 (basket1), 3 (basket2), 2, 2]

✅ Answer: 4 fruits

💡 Approach (Sliding Window): Is problem ka best solution hota hai:

➤ Sliding Window Technique – Two Pointers ke saath 🔧 Step-by-step Approach: Left aur Right pointers lo (left = 0, right = 0)

Ek Map (HashMap) banao jo store karega: fruit type → count

right pointer se array traverse karo:

Current fruit ko map mein add karo.

Agar map mein 2 se zyada types ho gaye:

Tab tak left++ karo jab tak sirf 2 types bach jaayein.

Saath hi map se count kam karo, aur 0 hone par remove bhi karo.

Har step pe right - left + 1 nikal ke max length update karo.

✅ Final Code (Java): java Copy Edit import java.util.*;

class Solution { public int totalFruit(int[] fruits) { int left = 0, maxFruits = 0; Map map = new HashMap<>();

for (int right = 0; right < fruits.length; right++) { map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);

while (map.size() > 2) { map.put(fruits[left], map.get(fruits[left]) - 1); if (map.get(fruits[left]) == 0) { map.remove(fruits[left]); } left++; }

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

return maxFruits; } } 🔍 Dry Run (fruits = [1,2,3,2,2]): Start from left = 0

Map grows to [1,2], then [2,3], then [3,2]

Max window = [3,2,2] → size = 3

Final window: [2,3,2,2] → size = 4

✅ Output: 4

To ab ham next question ham karege jo aapke slinding widown ke concept ko or badheyega ok

0
Subscribe to my newsletter

Read articles from Navneet Kumar directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Navneet Kumar
Navneet Kumar