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

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 69 70 71 |
#include <stdio.h> #include <limits.h> // Utility function to find minimum of two numbers int min(int x, int y) { return (x < y) ? x : y; } // 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) printf("Smallest sub-array length is %d", len); else printf("No sub-array exists"); return 0; } |

`Output:`

Smallest sub-array length is 4

## 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 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Util { // Function to find the length of smallest subarray whose sum // of elements is greater than the given number public static int smallestSubarray(int[] A, int k) { // stores the current window sum int windowSum = 0; // stores the result int len = Integer.MAX_VALUE; // stores window's starting index int left = 0; // maintain a sliding window [left..right] for (int right = 0; right < A.length; right++) { // include current element in the window windowSum += A[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 = Integer.min(len, right - left + 1); // remove elements from the window's left side till window // becomes stable again windowSum -= A[left]; left++; } } // return result return len; } // main function public static void main(String[] args) { int[] A = {1, 2, 3, 4, 5, 6, 7, 8}; int k = 21; // positive number // find length of the smallest sub-array int len = smallestSubarray(A, k); if (len != Integer.MAX_VALUE) { System.out.print("Smallest sub-array length is " + len); } else { System.out.print("No sub-array exists"); } } } |

`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 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

I guess complexity wouold be O(n^2) which is not good.

Thanks for sharing your concern. Please take closer look at the code. The complexity of the solution is

O(n).wont the solution fail for say -1 -4 6 and sum=1

Hello, thanks for sharing your concern. The solution seems to be working fine for the array

{ -1, -4, 6 }andk = 6. It returns 1 as smallest sub-array length, which holds true for subarray{ 6 }. Hope you’re clear now.solution fails for the array A = {84,-37,32,40,95} and K = 167

It works fine. The question explicitly mentions

greater thanand notgreater than or equal to.