Skip to main content

Arrays Hands-On: Warming Up

Sliding Window - 1

To sum up the previous articles of this section, we looked a couple of different patterns, one being simply iterating and doing something or the other with the elements while doing it, second being where more than one iterative pointers are in use.

In the next couple of articles, let's warm up another standard way, i.e. sliding window.

Max Sum Subarray of size K

The problem says that we'll be given an array, let's say, arr, and a number K ( 1 <= K <= len(arr) ); we need to find the maximum sum that a subarray of size K has.

What is a f***ing subarray?

In layman's language, a subarray is a contiguous sub-part of a given array. It'll be easier to understand using an example.

If a given array is [5, 2, 8, 8], then:

  1. [5], [2], [8] and [8] are its subarrays of size/length equal to 1.
  2. [5, 2], [2, 8] and [8, 8] are the subarrays of size 2.
  3. [5, 2, 8] and [2, 8, 8] are the subarrays of size 3.
  4. [5, 2, 8, 8] is the one and only subarray of size 4.
  5. [5, 8], [5, 8, 8] are not subarrays because they are not contiguous because 2 is missing.

A small exercise for you: how many subarrays do you think an array of size N will have?

Hint Try to think about each different possibility of size and how many subarrays will be there for that particular size. Add the number of subarrays for each subarray_size, and you'll have the total number. Simple math, or not?
Answer If you observe carefully:
  1. There will be exactly N subarrays of size = 1.
  2. There will be exactly N - 1 subarrays of size = 2.
  3. There will be exactly N - 2 subarrays of size = 3.
  4. the trend carries on...
  5. There will be exactly 3 subarrays of size = N - 2.
  6. There will be exactly 2 subarrays of size = N - 1.
  7. There will be exactly 1 subarray of size = N.
Therefore, the total number of subarrays = 1 + 2 + 3 + ... + (N - 2) + (N - 1) + N = N*(N+1)/2

How to solve the problem?

As always, let's begin with a beginner-friendly brute-force approach. We'll go to all subarrays of size K, find their sum, and keep track of the maximum sum encountered so far.

Implementation 
long maximumSumSubarray(int K, vector<int> &Arr , int N){
	// code here
	long max_sum = 0;
	for(int st = 0, en = K-1; st < N && en < N; st++, en++) {
		// Find the sum: arr[st] + arr[st+1] ... arr[en-1] + arr[en]
		long cur_sum = 0;
		for(int i = st; i <= en; ++i) {
			cur_sum += arr[i];
		}
		max_sum = max(max_sum, cur_sum);
	}
	return max_sum;
}

I hope you folks have learned enough by now that you can understand the above code without needing an explanation. (or not?)

Time & Space Complexity

Space Complexity: O(1) [simply because no extra space is used to get the answer]

Time Complexity: O(N*K). If you use some math, you'll see that the outer loop will run (N-K+1) number of times, and the inner loop will run K times every time. Therefore, operations = N*K - K*K + K. Now, according to what we learned in the time complexity section, if we only take the most significant term, time complexity = O(N*K)

How to solve the problem efficiently?

Here comes the technique to slide our way to efficiency.

Hint 1 When we look at the 1st subarray of size K, i.e. arr[0...(K-1)], surely, calculate the sum, but what about the subsequent window/subarrays of size K, do we need to calculate the sum from scratch every time?
Hint 2
Complete Explanation

A suggestion: keep the above image open while reading; it'll probably help in better visualisation.

So, the idea, as visible in the above illustration, is that when we move from 1 particular subarray of size k (let's say i-1 to j-1), to the just next subarray (i to j), the elements arr[i], arr[i+1] ... arr[j-1] are common among the two.

The only differentiating elements are:

  1. arr[i-1]: present in window 1 but not in window 2.
  2. arr[j]: present in window 2 but not in window 1.

So, based on the above intuition, we can do the following:

  1. Calculate the subarray sum (let's say cur_sum) for the 1st subarray of size K.
  2. Then keep on sliding the window.
  3. If the current window is from st to en, but the cur_sum variable represents the subarray sum for st-1 to en-1, just subtract arr[st-1] from cur_sum and add arr[en] to cur_sum.
  4. Keep track of the maximum subarray sum seen so far.

Return the max_sum after having gone through all the subarrays of size K.
Implementation 
long maximumSumSubarray(int K, vector<int> &arr , int N){
	// code here
	long cur_sum = 0;

	// find the sum for 1st window of size k
	for(int i = 0; i < k; ++i)
		cur_sum += arr[i];

	long max_sum = cur_sum;

	// keep updating cur_sum as we
	// slide through other windows
	// and track max_sum
	for(int st = 1, en = k; en < N; st++, en++) {
		cur_sum -= arr[st - 1];
		cur_sum += arr[en];

		max_sum = max(max_sum, cur_sum);
	}

	return max_sum;
}
This is another problem very similar to the above problem that you can try to solve.