K-Subarray Sum Editorial

Practice Problem Link: K-Subarray Sum

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array and a number k, find the sum of all the subarrays of size k.

Naive Approach

The naive approach is to iterate over all the subarrays in the array, and if it is of length k, we can calculate its sum and store it in a list.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

vector<int> kSubarraySum(vector<int> A, int k) {
	int n = A.size();
	vector<int> list;
	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			if(j - i + 1 == k) {
				int sum = 0;
				for(int l = i; l <= j; l++) {
					sum += A[l];
				}
				list.push_back(sum);
			}
		}
	}
	return list;
}

Java

class Solution {
	int[] kSubarraySum (int[] A, int k) {
		int n = A.length;
		int[] list = new int[n - k + 1];
		int iterator = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(j - i + 1 == k) {
					int sum = 0;
					for(int l = i; l <= j; l++) {
						sum += A[l];
					}
					list[iterator] = sum;
					iterator++;
				}
			}
		}
		return list;
	}
}

Optimal Approach

In the optimal approach, we will use the sliding window technique to calculate the sum in linear time. We keep erasing the i - kth element from the current sum and add the ith element to the sum, and store all these sums in a list. Finally, we return the list.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

vector<int> kSubarraySum(vector<int> A, int k) {
	int n = A.size();
	vector<int> list(n - k + 1);
	int sum = 0;
	int iterator = 0;
	for(int i = 0; i < k; i++) {
		sum += A[i];
	}
	list[iterator] = sum;
	iterator++;
	for(int i = k; i < n; i++) {
		sum -= A[i - k];
		sum += A[i];
		list[iterator] = sum;
		iterator++;
	}
	return list;
}

Java

class Solution {
	int[] kSubarraySum (int[] A, int k) {
		int n = A.length;
		int[] list = new int[n - k + 1];
		int sum = 0;
		int iterator = 0;
		for(int i = 0; i < k; i++) {
			sum += A[i];
		}
		list[iterator] = sum;
		iterator++;
		for(int i = k; i < n; i++) {
			sum -= A[i - k];
			sum += A[i];
			list[iterator] = sum;
			iterator++;
		}
		return list;
	}
}