11. Sliding Window - Basic

Sliding Window টেকনিক নেস্টেড লুপের ব্যবহার কমিয়ে টাইম কমপ্লেক্সিটি অনেক উন্নত করতে পারে। এটি রেঞ্জ-ভিত্তিক (Range-based) সমস্যার জন্য অত্যন্ত কার্যকর।

---

1. ম্যাক্সিমাম সাম সাব-অ্যারে (Maximum Sum Subarray of size k)

একটি নির্দিষ্ট আকার k এর সাব-অ্যারের মধ্যে সর্বোচ্চ যোগফল বের করা।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. প্রথম k এলিমেন্টের যোগফল বের করুন। একে currentSum এবং maxSum হিসেবে ধরুন।
2. এবার উইন্ডোটিকে এক ঘর ডানে সরান।
3. নতুন এলিমেন্ট যোগ করুন এবং উইন্ডোর আগের প্রথম এলিমেন্টটি বিয়োগ করুন:
   currentSum = currentSum + newElement - oldElement
4. প্রতি পদক্ষেপে maxSum-কে আপডেট করুন যদি currentSum বড় হয়।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(n) - মাত্র একবার পুরো অ্যারে ট্রাভার্স করতে হয়।
• Space Complexity: O(1)

// Java
public int maxSum(int[] arr, int k) {
    int maxVal = 0, currentSum = 0;
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    maxVal = currentSum;
    for (int i = k; i < arr.length; i++) {
        currentSum += arr[i] - arr[i - k];
        maxVal = Math.max(maxVal, currentSum);
    }
    return maxVal;
}

# Python
def max_sum(arr, k):
    max_val = current_sum = sum(arr[:k])
    for i in range(k, len(arr)):
        current_sum += arr[i] - arr[i-k]
        max_val = max(max_val, current_sum)
    return max_val

---

2. ক্ষুদ্রতম সাব-অ্যারের লেন্থ (Minimum Subarray for Target Sum)

এমন একটি ক্ষুদ্রতম সাব-অ্যারের সাইজ বের করা যার যোগফল S এর সমান বা বড়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic) - Variable Size Window

1. left এবং right দুটি পয়েন্টার শুরু থেকে আরম্ভ করুন।
2. right পয়েন্টার দিয়ে এলিমেন্ট যোগ করতে থাকুন যতক্ষণ না যোগফল টার্গেট পূর্ণ করে।
3. যখন যোগফল টার্গেট ফিল করে, তখন উইন্ডোটি ছোট করার চেষ্টা করুন (left পয়েন্টার ডানে সরিয়ে) এবং লেন্থ ট্র্যাক করুন।
4. এভাবে বারবার উইন্ডো বাড়ানো এবং কমানোর মাধ্যমে ক্ষুদ্রতম লেন্থ খুঁজে বের করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(n) - যদিও দুটি পয়েন্টার আছে, প্রতিটি এলিমেন্ট সর্বোচ্চ দুবার প্রসেস হয়।
• Space Complexity: O(1)

Implementation

// Java
public int minSubArrayLen(int target, int[] nums) {
    int left = 0, currentSum = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        currentSum += nums[right];
        while (currentSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            currentSum -= nums[left++];
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

# Python
def min_subarray_len(target, nums):
    left = current_sum = 0
    min_len = float('inf')
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_len == float('inf') else min_len

---

TIP

যদি কোনো অ্যার প্রবলেমে "Subarray" এর যোগফল বা এভারেজ নিয়ে কাজ করতে বলা হয়, তখন স্লাইডিং উইন্ডো কাজটিকে অনেক সহজ করে দেয়।