🧠 Sliding Window Pattern: The Secret Sauce for Efficient Algorithms

🚀 Mastering the Sliding Window Technique in C++: Crack DSA Like a Pro!

When you're tackling arrays or strings in competitive programming or coding interviews, efficiency is king. That’s where the Sliding Window technique comes in — a game-changing approach that helps you move from brute-force to optimized solutions.

In this guide, we’ll dive deep into:

• 💡 What is Sliding Window?
• 🧠 Why use it?
• 🧱 Brute Force vs Optimized Approaches
• 📊 Time & Space Complexities
• 🧪 Real-world Examples
• 🔗 My GitHub Repository for Open Source Contribution

---

🧠 What is Sliding Window?

Sliding Window is a technique for solving problems involving linear data structures like arrays and strings. It involves creating a window (usually a subarray or substring) and moving it across the input to find a solution — without recalculating everything inside the window.

---

🤕 The Brute Force Way (Naive Approach)

Problem Example:

Find the maximum sum of a subarray of size k.

Naive Approach (O(n*k)):

cpp
int maxSumBruteForce(vector<int>& nums, int k) {
    int n = nums.size();
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum += nums[i + j];
        }
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

Time Complexity: O(n*k)
Space Complexity: O(1)

🚀 Optimized Sliding Window Approach

cpp

int maxSumSlidingWindow(vector<int>& nums, int k) {
    int windowSum = 0, maxSum = INT_MIN;
    for (int i = 0; i < k; i++) windowSum += nums[i];
    maxSum = windowSum;

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

Time Complexity: O(n)
Space Complexity: O(1)

This approach avoids recalculating sums by adding the next element and removing the first element of the previous window.

🧪 Real Interview Examples Using Sliding Window

1. 🔥 Maximum Sum Subarray of Size K
2. 🍎 Fruit Into Baskets
3. 🥇 Longest Subarray of 1s After Deleting One Element
4. 🧮 Count Number of Nice Subarrays
5. 💼 Minimum Size Subarray Sum

📚 Use-Cases of Sliding Window

• Find the max/min/average of a subarray
• Count distinct elements in a subarray
• Longest substring with at most k distinct characters
• Smallest window that satisfies a condition

⚙️ Template Code (Variable-Size Window):

cpp

int solve(vector<int>& nums) {
    int i = 0, j = 0, answer = 0;
    unordered_map<int, int> freq;

    while (j < nums.size()) {
        freq[nums[j]]++;

        // If condition violated
        while (freq.size() > k) {
            freq[nums[i]]--;
            if (freq[nums[i]] == 0) freq.erase(nums[i]);
            i++;
        }

        answer = max(answer, j - i + 1);
        j++;
    }

    return answer;
}

👨‍💻 Open Source Contribution

All of my DSA solutions using Sliding Window (including the LeetCode/Striver/Nudecode-150 ones) are available in my GitHub repo:

🔗 GitHub Repository:** 👉 Click Here to Explore My Solutions

Make sure to ⭐ star the repo and follow me for more updates!**