Given an array of integers, find the length of smallest subarray whose sum of elements is greater than the given positive number.

Input: {1, 2, 3, 4, 5, 6, 7, 8}, k = 20

Output: {6, 7, 8}

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

Output: {8}

Input: {1, 2, 3, 4, 5, 6, 7, 8}, k = 21

Output: {5, 6, 7, 8}

Input: {1, 2, 3, 4, 5, 6, 7, 8}, k = 40

Output: No sub-array exists

Note that we don’t have to print the sub-array but return its length.

We can solve this problem by using a sliding window. The idea is to maintain a window that ends at the current element and sum of its elements is less than or equal to the given sum. If current window’s sum becomes more than the given sum at any point of time, then the window is unstable and continue removing elements from the window’ left till it becomes stable again. We also update the result if unstable window’s length is less than minimum found so far.

**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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <climits> using namespace std; // Function to find the length of smallest subarray whose sum // of elements is greater than the given number int smallestSubarray(int arr[], int n, int k) { // stores the current window sum int windowSum = 0; // stores the result int len = INT_MAX; // stores window's starting index int left = 0; // maintain a sliding window [left..right] for (int right = 0; right < n; right++) { // include current element in the window windowSum += arr[right]; // (to handle negative numbers in the array) // if window's sum becomes negative, discard the window if (windowSum <= 0) // Kadane's algorithm { left = right; windowSum = 0; } // window becomes unstable if its sum becomes more than k while (windowSum > k && left <= right) { // update the result if current window's length is less // than minimum found so far len = min(len, right - left + 1); // remove elements from the window's left side till window // becomes stable again windowSum -= arr[left]; left++; } } // return result return len; } // main function int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int k = 21; // positive number int n = sizeof(arr) / sizeof(arr[0]); // find length of the smallest sub-array int len = smallestSubarray(arr, n, k); if (len != INT_MAX) cout << "Smallest sub-array length is " << len; else cout << "No sub-array exists"; return 0; } |

**Output: **

Smallest sub-array length is 4

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

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

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