In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objective: Given an array and an integer, find the smallest subarray whose sum is greater than the given integer.

Examples:

arrA[] = { 1, 5, 20, 70, 8}
Integer = 97
Output : Min Length = 3 Subarray = [20, 70, 8]

 
arrA[] = { 1, 10, 3, 40, 18}
Integer = 50
Output : Min Length = 2 Subarray = [40, 18]

Approach:

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

  • Initialize minLength = length of the array and say the given integer is x.
  • Take variables currSum = 0, start = 0
  • Do the linear scan in array and start adding each element to the currSum.
  • if currSum > x then start subtracting element from the start.(currSum-arrA[start]) check the length of the subarray, if it is less then the minLength (currentIndex-start<minLength)update minLength and store the current index and start index for finding the subarray.

Complete Code:


Output:

Min length of subarray to get 50 is : 2
SubArray is:   40   18

8 thoughts on “In an Array, find the Smallest Subarray with Sum Greater than the Given Value”

  1. it would work only if the array is sorted. if not, it would fail.
    a = [1, 20, 30, 10, 50], min = 51
    will return [1, 20, 30] instead of [1, 50]

    Reply
  2. for array a={ 1, 20, 30, 10} and sum 60, above code will print only length not subarray. Little modification is required in code as mentioned below.

    instead of
    if (i – start < minLen)

    it should be
    if (i – start <= minLen)

    Reply
  3. Hello,

    Given an array {4, 7, 11, 3, 12, 1, 9, 2} and x=22 it returns 11, 3 and 12 as the shortest subarray when {11, 12} is the correct answer.

    Reply
    • Yes , the program is for subarray so elements has to be contiguous so 11,3,12 is the right answer. {11,12} is the sub sequence.

      Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.