Sliding Windows

Utility of sliding window
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
SUBSTINGS
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 haiSlidingwindow
.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 sizek
).
✅ 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 indexi
ko cover karega.n - k + 1
tak isliye ja rahe hain, taakii + 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 lengthk
.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
havek-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 haiSo 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 haiIs 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 indexj
→ window ka end index (pehla windowk-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
aurj
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 🔍:
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
.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)
Tumhara
while(i < n && arr[i] == 1)
part kaafi manual hai, aur kuch unnecessary calculations ho rahe hain.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
Metric | Value |
Time | O(n) |
Space | O(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 minutei
.grumpy[i]
: Whether the shopkeeper is grumpy (1
= grumpy,0
= not grumpy) at minutei
.
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:
Calculate the number of unsatisfied customers in the first
k
minutes (if owner was grumpy).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.
In that best window, temporarily make grumpy = 0.
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
Subscribe to my newsletter
Read articles from Navneet Kumar directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
