Smallest Subarray with Sum Greater Than or Equal To Given Number

Problem statement:

Find out the length of the minimum subarray whose sum is greater than or equal to the given number.

This question was asked in many product-based companies coding rounds like Goldman Sachs.

Example 1:

Given array: [3, 1, 7, 1, 2]
Given target sum: 11

Output: 3 (Minimum subarray is [3, 1, 7])

Example 2:

Given array=[2, 3, 5, 4, 1]
Given target sum=11

Output: 3 (Minimum subarray is [3, 5, 4])

Example 3:
If there is no as such sub-array, return -1.

Given array=[2, 3, 2, 1, 5]
Given target sum=17

Output: -1 (Target sum is greater than the sum of an array.)

Explanation:

This can be done using dynamic recursion.

First of all, find out all the base conditions where you don’t need recursion.

Base case conditions:

• If the target sum is zero or less than zero, return 0.
• If the sum of the array is smaller than the target sum, return -1.
• If the sum of the array is equal to the target sum, return the length of the array.
• If the first element in the array is greater than one, return 1. (First element in the array is the smaller subset having a sum greater than the target sum.)

Python Program:

#Smallest subarray with sum greater than 
#or equal to the given number.
 
def smallSumSubset(data, target, maxVal):
    #base condition
    if target<=0:
        return 0
    elif sum(data)<target:
        return maxVal
    elif sum(data)==target:
        return len(data)
    elif data[0]>=target:
        return 1

    #recursive dynamic programming
    elif data[0]<target:
        return min(smallSumSubset(data[1:], target, maxVal), \
        1+smallSumSubset(data[1:], target-data[0], maxVal))


data=[2, 3, 5, 4, 1]
target=11
 
val=smallSumSubset(data, target, len(data)+1)
 
if val>len(data):
    print(-1)
else:
    print(val)

Output:

3

Programming concepts used in the above Python code:

• if-elif-else statement in Python
• Different Python list methods like min()

Your actions…

This is the solution for the Smallest subarray with sum greater than given number.

Can you solve this problem in any other programming language like C, Java, etc? If you can take this challenge, submit your code in the comment. I will publish it here.