Data Structures and Algorithms in C (DSA)

📘 Chapter: Sliding Window Technique

Imagine you're inspecting a long conveyor belt of items, and you need to calculate the sum of items in a specific section, then move that section forward without re-calculating everything from scratch. This is the essence of the Sliding Window Technique! It's a powerful and efficient algorithmic approach used to solve problems that involve finding a contiguous subarray, substring, or subsegment in a data structure (like an array or string) that satisfies certain conditions.

🤔 What is the Sliding Window Technique? The Core Idea

At its core, the sliding window technique maintains a "window" (a range of elements) that slides over the input data. Instead of re-evaluating the entire subsegment for each position, it efficiently updates the window's properties (like sum, count of distinct elements, max/min, etc.) by "removing" the element leaving the window and "adding" the new element entering the window. This reduces redundant computations.

Think of it like a fixed-size camera frame moving across a landscape, or a flexible net expanding and contracting to catch a certain number of fish.

🖼️ Key Components of a Sliding Window

• Two Pointers (`left` and `right`): These define the boundaries of the current "window". `left` marks the start, and `right` marks the end.
• Window State: A variable or data structure (e.g., `current_sum`, `frequency_map`, `set`) that maintains the property of the elements currently within the window.
• Sliding Logic:
  • Move `right` pointer to expand the window and include a new element. Update window state.
  • If the window condition is met (or violated), move `left` pointer to shrink the window. Update window state.
  • Record or update the result/answer based on the current window.

📋 Types of Sliding Window Problems

Sliding window problems typically fall into two categories:

1. Fixed-Size Sliding Window

The window always maintains a constant size `K`. This is useful for problems like "Find the maximum sum subarray of size K".

// Example: Maximum sum subarray of size K
// Input: arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], K = 3
// Output: 25 (from [10, 2, 3, 1, 0, 20] -> max sum is 10+2+3=15, 2+3+1=6, 3+1+0=4, 1+0+20=21) Oh, typo in example. Let's trace it.
// Correct example: [1, 4, 2, 10, 2, 3, 1, 0, 20], K=3
// Window 1: [1, 4, 2] -> Sum = 7
// Window 2: [4, 2, 10] -> Sum = 16 (max_so_far = 16)
// Window 3: [2, 10, 2] -> Sum = 14
// Window 4: [10, 2, 3] -> Sum = 15
// Window 5: [2, 3, 1] -> Sum = 6
// Window 6: [3, 1, 0] -> Sum = 4
// Window 7: [1, 0, 20] -> Sum = 21 (max_so_far = 21)
// Result: 21

int max_sum_fixed_window(vector<int>& arr, int K) {
    int N = arr.size();
    if (N < K) return 0; // Or handle error

    int current_sum = 0;
    for (int i = 0; i < K; ++i) { // Initialize first window
        current_sum += arr[i];
    }

    int max_sum = current_sum;

    for (int right = K; right < N; ++right) {
        current_sum += arr[right];     // Add new element to window
        current_sum -= arr[right - K]; // Remove element leaving window
        max_sum = max(max_sum, current_sum); // Update max sum found
    }
    return max_sum;
}
  

2. Variable-Size Sliding Window

The window size changes dynamically based on a condition. This is common for problems like "Find the smallest subarray with sum greater than or equal to S", or "Longest substring with K distinct characters".

// Example: Smallest subarray with sum >= S
// Input: arr = [2, 1, 5, 2, 3, 2], S = 7
// Output: 2 (subarray [5, 2])

int min_len_subarray_sum(vector<int>& arr, int S) {
    int N = arr.size();
    int min_length = INT_MAX;
    int current_sum = 0;
    int left = 0;

    for (int right = 0; right < N; ++right) {
        current_sum += arr[right]; // Expand window by adding element at 'right'

        // While current_sum meets the condition, shrink window from 'left'
        while (current_sum >= S) {
            min_length = min(min_length, right - left + 1); // Record current window length
            current_sum -= arr[left]; // Remove element at 'left'
            left++;                   // Shrink window from left
        }
    }
    return (min_length == INT_MAX) ? 0 : min_length; // Return 0 if no such subarray
}
  

🔬 Visualization: Fixed-Size Window (K=3)

⚡ Time and Space Complexity

One of the main reasons for using the Sliding Window technique is its efficiency:

• Time Complexity: Typically $O(N)$ because each element is visited by the `right` pointer once, and by the `left` pointer at most once. This makes it much faster than brute-force $O(N^2)$ approaches.
• Space Complexity: Usually $O(1)$ if only simple variables (like `current_sum`) are needed. If a frequency map or similar data structure is required (e.g., for `K` distinct characters), it can be $O(alphabet\_size)$ or $O(K)$, depending on the problem constraints.

⚖️ Advantages and Disadvantages

Advantages:

• Efficiency: Transforms $O(N^2)$ or $O(N^3)$ brute force solutions into $O(N)$ solutions.
• Simplicity: Once understood, the logic is quite intuitive and elegant.
• Versatility: Applicable to a wide range of problems involving contiguous subsegments.

Disadvantages:

• Contiguous Requirement: Only works for problems involving contiguous subarrays/subsequences.
• Problem Specific: The exact logic for expanding and shrinking the window (and what condition to check) is highly dependent on the specific problem.

📌 Real-Life Example (UdaanPath)

The Sliding Window technique is incredibly practical in scenarios where you need to process streams of data or analyze segments efficiently:

• User Activity Analysis: On UdaanPath, imagine tracking the activity of a user. You might want to find the "busiest 30-minute period" or the "longest continuous session" a user had on the platform. Sliding window can help by efficiently calculating metrics (like number of clicks, courses viewed) over rolling time windows.
• Content Recommendation: Analyzing a user's recent Browse history (a window of, say, 50 recently viewed courses) to recommend similar content. As the user views new courses, the window slides, keeping only the most relevant recent history.
• Traffic Monitoring: For an internal system monitoring API calls, you might want to find the peak number of requests in any 5-minute interval. A fixed-size sliding window can compute this sum efficiently.
• Log Analysis: Finding patterns or errors in log files by looking for specific sequences or frequency thresholds within a certain number of log entries.

✅ Summary: Slide to Success!

• Sliding Window is an optimization technique for problems on contiguous subarrays/substrings.
• It uses `left` and `right` pointers to define a dynamic "window".
• Achieves $O(N)$ time complexity by avoiding redundant calculations.
• Can be fixed-size or variable-size, depending on the problem's condition.
• Ideal for problems requiring maximum/minimum sum, longest/shortest subsegment with a property, etc.

📤 Coming Next: Two Pointers Technique

Building on the concept of multiple pointers, our next chapter explores the **Two Pointers Technique**. While often used within a sliding window, it's also a standalone powerful method for solving array and list problems by efficiently traversing data from different directions or at different speeds.