Sliding window pattern

Hello and welcome back, brave human being,

You are going to spend 90,000 hours of your life working. Since you are subscribed to this newsletter, chances are you are a computer scientist.

So what does our profession have to offer that would make you willing to spend 1/3 of your life in it?

Are you in it for the monaaaay? 🤑 Don’t tell your recruiter.

Are you in it for the flexible hours? Don’t tell your recruiter.

Are you in it to make an impact in changing one feature that might not even see the light of day? Don’t tell your recruiter.

These are all jokes and fun but do reflect on why you are studying these problems. Be intentional about the career you choose, and make sure you know why you are in this field.

The days are long and the years are short, make sure you know where you are spending them.

Day 23: Find maximum (or minimum) sum of a subarray of size k

The sliding window pattern is the last pattern of this challenge!!!!!!

What is the problem asking for?

A sliding window problem usually asks for subarrays that satisfy a condition; it may ask for a special subarray such as the shortest or longest that satisfies a certain condition, or the number of subarrays satisfying said condition.

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

Let’s first think about our naive solution…

The naive solution to this problem would be to generate all the subarrays of size k with a nested loop and keep track of the global and local minimum. This naive solution would have a time complexity of O(N^2)

Sliding Window Solution.

The sliding window technique is used when a specific operation needs to be done to just a “window” of the array. The idea is to reduce a nested loop to a single loop and do the operations to the window as it progresses and not calculate all of the subarrays of size k. This solution has a time complexity of O(N) and an auxiliary space of O(1).

First, calculate the sum of the first window by adding the first k elements.

Keep track of the sum with a max_sum variable.

To calculate the next window, subtract the first element of the array and add the arr[k+1] to the sum, updating the max_sum variable.

Iterate through the rest of the array, repeating the same steps.

When finishing all iterations of the array, return max_sum, which will have the maximum sum of a k-length subarray.

Let’s set an example: (Shout out to Fernando!!!! who is helping me with the animations 🤟 )

Complete solution:

int maxSum(int arr[], int array_size, int k) {
    //The window size needs to be larger than the array 
    if (array_size < k) {
        cout << "Invalid";
        return -1;
    }

    // Compute sum of first window of size k
    int max_sum = 0;
    for (int i = 0; i < k; i++)
        max_sum += arr[i];

    // Compute sums of remaining windows by
    // removing first element of previous
    // window and adding last element of 
    // current window.
    int current_sum = max_sum;
    for (int i = k; i < array_size; i++) {
        current_sum += arr[i] - arr[i - k];
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

Cheers to the last pattern!!!