Find minimum sum subarray of size `k`
Given an integer array, find the minimum sum subarray of size k, where k is a positive integer.
For example,
Output: Minimum sum subarray of size 3 is (1, 3)
The problem differs from the problem of finding the minimum sum subsequence of size k. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.
We can solve this problem by using the sliding window technique. The idea is to maintain a window of size k. For every array element, include it in the window and remove the window’s leftmost element if the window size is more than k. Also maintain the sum of elements in the current window. If the sum of the current window is less than the minimum found so far, update the minimum sum to the current window sum and store the window’s endpoints.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <stdio.h> #include <limits.h> // Find the minimum sum subarray of a given size `k` void findSubarray(int arr[], int n, int k) { // base case if (n == 0 || n <= k) { return; } // stores the sum of elements in the current window int window_sum = 0; // stores the sum of minimum sum subarray found so far int min_window = INT_MAX; // stores ending index of the minimum sum subarray found so far int last = 0; for (int i = 0; i < n; i++) { // add the current element to the window window_sum += arr[i]; // if the window size is more than equal to `k` if (i + 1 >= k) { // update the minimum sum window if (min_window > window_sum) { min_window = window_sum; last = i; } // remove a leftmost element from the window window_sum -= arr[i + 1 - k]; } } printf("The minimum sum subarray is (%d, %d)", last - k + 1, last); } int main(void) { int arr[] = { 10, 4, 2, 5, 6, 3, 8, 1 }; int k = 3; int n = sizeof(arr)/sizeof(arr[0]); findSubarray(arr, n, k); return 0; } |
Output:
The minimum sum subarray is (1, 3)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Main { // Find the minimum sum subarray of a given size `k` public static void findSubarray(int[] arr, int k) { // base case if (arr.length == 0 || arr.length <= k) { return; } // stores the sum of elements in the current window int window_sum = 0; // stores the sum of minimum sum subarray found so far int min_window = Integer.MAX_VALUE; // stores ending index of the minimum sum subarray found so far int last = 0; for (int i = 0; i < arr.length; i++) { // add the current element to the window window_sum += arr[i]; // if the window size is more than equal to `k` if (i + 1 >= k) { // update the minimum sum window if (min_window > window_sum) { min_window = window_sum; last = i; } // remove a leftmost element from the window window_sum -= arr[i + 1 - k]; } } System.out.printf("The minimum sum subarray is (%d, %d)", last - k + 1, last); } public static void main(String[] args) { int[] arr = { 10, 4, 2, 5, 6, 3, 8, 1 }; int k = 3; findSubarray(arr, k); } } |
Output:
The minimum sum subarray is (1, 3)
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import sys # Find the minimum sum sublist of a given size `k` def findSublist(A, k): # base case if not len(A) or k >= len(A): return # stores the sum of elements in the current window window_sum = 0 # stores the sum of minimum sum sublist found so far min_window = sys.maxsize # stores ending index of the minimum sum sublist found so far last = 0 for i in range(len(A)): # add the current element to the window window_sum += A[i] # if the window size is more than equal to `k` if i + 1 >= k: # update the minimum sum window if min_window > window_sum: min_window = window_sum last = i # remove a leftmost element from the window window_sum -= A[i + 1 - k] print("The minimum sum sublist is", (last - k + 1, last)) if __name__ == '__main__': A = [10, 4, 2, 5, 6, 3, 8, 1] k = 3 findSublist(A, k) |
Output:
The minimum sum subarray is (1, 3)
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.
Exercise: Find the minimum product subarray of a given size k
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)