Given an array of integers, find minimum sum sub-array of given size k.

**Input:** {10, 4, 2, 5, 6, 3, 8, 1}, k = 3

**Output:** Minimum sum sub-array of size 3 is (1, 3)

We can solve this problem by using sliding window technique. The idea is to maintain a window of size k and for every element in the array, we include it in the window and remove leftmost element from the window if window size is more than k. We also maintain sum of elements in current window. If current window sum is more than minimum found so far, we update the minimum sum to current window sum and store window’s end-points.

**C implementation –**

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 |
#include <stdio.h> #include <limits.h> // Find minimum sum sub-array of given size k void findSubarray(int arr[], int n, int k) { // stores sum of element in current window int window_sum = 0; // stores sum of minimum sum sub-array found so far int min_window = INT_MAX; // stores ending index of minimum sum sub-array found so far int last = 0; for (int i = 0; i < n; i++) { // add current element to the window window_sum += arr[i]; // if window size is more than equal to k if (i + 1 >= k) { // update minimum sum window if (min_window > window_sum) { min_window = window_sum; last = i; } // remove leftmost element from the window window_sum -= arr[i + 1 - k]; } } printf("Minimum sum sub-array is (%d, %d)", last-k+1, last); } // main function 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:`

Minimum sum sub-array is (1, 3)

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Exercise:** Find minimum product sub-array of given size k

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply