Problem Solving Patterns

Welcome Back to the Problem Solving Patterns Series

In our journey to become more efficient problem solvers, we've already explored two fundamental patterns: Frequency Counters and Multiple Pointers. These patterns have given us tools to approach and solve problems with greater clarity and efficiency.

Recap of Previous Patterns

Frequency Counters (Part1): We learned how to use objects or sets to keep track of frequencies in problems where counting or checking for uniqueness is crucial.

Multiple Pointers (Part2): We explored how using pointers to represent different positions in a data structure can help solve problems that involve sequences or pairs, often in a more space-efficient way.

Introducing the Sliding Window Pattern

Now, let's move on to the third pattern in our series: the Sliding Window. This pattern is particularly useful for solving problems involving a contiguous subset of elements in an array or string. Whether it's finding the maximum sum of a subarray of fixed size or checking for the existence of a specific sequence, the Sliding Window technique can significantly reduce time complexity compared to a brute-force approach.

Deep Dive into the Sliding Window Pattern

The Sliding Window pattern is an incredibly efficient technique used when dealing with problems involving a subset of data elements that are contiguous in nature, such as subarrays or substrings. Instead of recalculating for each possible subset, we "slide" a window across the data to find our solution in a more optimized way.

Example Problem: Maximum Sum Subarray of Size K

Problem Statement: Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Example:

Input: arr = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

Basic Solution

function maxSubArraySum(arr, num){
    if(num > arr.length){
        return null;
    }

    var max = -Infinity;

    for (let i = 0; i < arr.length - num + 1; i++) {
        temp = 0;
        for (let j = 0; j < num; j++) {
            temp += arr[i+j]
        }
        if(temp > max){
            max = temp
        }
    }
    return max
}

Time Complexity - O(N^2)

Step-by-Step Guide using Sliding Window Pattern:

1. Understanding the Brute Force Approach:

• In a brute-force solution, we would calculate the sum of every possible subarray of size k and keep track of the maximum sum.

• This approach has a time complexity of O(n * k), where n is the length of the array. For large arrays, this becomes inefficient.

• Space Complexity: O(1) since we only use a few extra variables for calculation.

1. Introducing the Sliding Window Approach:

• Instead of recalculating the sum for each subarray, we maintain a running sum of the current window of size k.

• As we slide the window by one element, we subtract the element that is leaving the window and add the element that is entering the window.

1. Implementing the Sliding Window Approach:

Let’s walk through the problem step by step in JavaScript.

function maxSubarraySum(arr, k) {
    let maxSum = 0;
    let windowSum = 0;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];                // Add the next element to the window

        // Slide the window, we don't need to slide if we've not hit the required window size of 'k'
        if (windowEnd >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);  // Update the maximum sum
            windowSum -= arr[windowStart];         // Subtract the element going out
            windowStart += 1;                      // Slide the window ahead
        }
    }

    return maxSum;
}

// Test the function
const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSubarraySum(arr, k));              // Output: 9

1. Breaking Down the Code:

• Initialize Variables:

  • maxSum: Tracks the maximum sum encountered.
  • windowSum: Stores the sum of the current window.
  • windowStart: The index where the window starts.

• Sliding the Window:

  • We iterate over the array, adding each element to the windowSum.
  • Once the window reaches size k, we check if the current windowSum. is greater than maxSum and update maxSum accordingly.
  • We then slide the window by subtracting the element that is going out and incrementing windowStart.

Conclusion

The Sliding Window pattern is a versatile and powerful technique that can be applied to a variety of problems involving contiguous subarrays or substrings. By understanding and mastering this pattern, you'll be better equipped to tackle more complex challenges efficiently.

Stay tuned! In the next chapter of this series, we will dive into the Divide and Conquer pattern, a fundamental strategy that breaks down complex problems into simpler sub-problems to solve them more effectively.