Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given an array and an inte­ger, find the small­est sub­ar­ray whose sum is greater than the given integer.

Exam­ples:

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 Com­plex­ity — O(n2).

Bet­ter Approach: Time Com­plex­ity — O(n)

  • Ini­tial­ize min­Length = length of the array and say the given inte­ger is x.
  • Take vari­ables currSum = 0, start = 0
  • Do the lin­ear scan in array and start adding each ele­ment to the currSum.
  • if currSum > x then start sub­tract­ing ele­ment from the start.(currSum-arrA[start]) check the length of the sub­ar­ray, if it is less then the min­Length (currentIndex-start<minLength)update min­Length and store the cur­rent index and start index for find­ing the subarray.

Com­plete Code:


Out­put:

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

You may also like...

  • sagivo

    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]

    • tuto­ri­al­hori­zon

      The code will return Min­i­mum length of sub­ar­ray to get 51 is : 2
      Sub­Ar­ray is: 10 50

      The pro­gram is correct

  • Princ

    This code returns 40 and 18 for me.

  • dheeraj sing­hal

    for array a={ 1, 20, 30, 10} and sum 60, above code will print only length not sub­ar­ray. Lit­tle mod­i­fi­ca­tion is required in code as men­tioned below.

    instead of
    if (i — start < minLen)

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