Mastering Sliding Window Patterns in DSA: Solving Key Problems

Understanding DSA Patterns: Sliding Window Approach

The Sliding Window pattern is a powerful technique in problem-solving within the field of Computer Science, particularly in solving problems related to subarrays and sublists. Here, we'll explore three important problems that utilize this approach: Maximum Sum Subarray, Smallest Subarray with Given Sum, and Smallest Subarray with Sum Greater than a Given Value.

1. Maximum Sum Subarray of Size K

This problem involves finding the maximum sum of a subarray with a fixed size k.

Approach:

int maximumSumSubarray(vector<int>& arr, int k) {
    int sum = 0;
    int maxSum = 0;
    int winStart = 0;

    for (size_t i = 0; i < arr.size(); i++) {
        sum += arr[i];
        if (i >= k - 1) {
            maxSum = max(maxSum, sum);
            sum -= arr[winStart];
            winStart++;
        }
    }
    return maxSum;
}

Explanation:

• sum accumulates elements of the current window.
• maxSum stores the maximum sum encountered.
• The window slides by reducing the sum of the first element and moving the winStart.

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

---

2. Smallest Subarray with a Given Sum

Here, the goal is to find the smallest contiguous subarray whose sum is greater than or equal to a given value S.

Approach:

function smallestSubarrayWithGivenSum(arr, s) {
  let windowSum = 0;
  let minLength = Infinity;
  let windowStart = 0;

  for (windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    windowSum += arr[windowEnd];

    while (windowSum >= s) {
      minLength = Math.min(minLength, windowEnd - windowStart + 1);
      windowSum -= arr[windowStart];
      windowStart++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
}

Explanation:

• The sliding window starts from the beginning and extends until the sum becomes equal or greater than S.
• We then attempt to shrink the window from the start until the sum is smaller again.

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

---

3. Smallest Subarray with Sum Greater than a Given Value

In this variation, the problem requires finding the smallest subarray such that the sum exceeds x.

Approach:

int smallestSubWithSum(int x, vector<int>& arr) {
    int sum = 0;
    int winStart = 0;
    int minLen = INT_MAX;

    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
        while (sum > x) {
            minLen = min(minLen, i - winStart + 1);
            sum -= arr[winStart];
            winStart++;
        }
    }
    return minLen != INT_MAX ? minLen : 0;
}

Explanation:

• Similar to the second approach, but here, we continue shrinking the window while the sum exceeds x.

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

---

Summary

The Sliding Window technique is versatile for solving problems that involve arrays or sequences with dynamic sizes. It efficiently reduces the problem space by continuously adjusting the size of the window to find the optimal result. These patterns are widely applicable across a variety of algorithmic challenges.