Goldman Sachs Interview:Smallest subarray with sum greater than a given value

Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.

Examples:
arr[] = {1, 4, 45, 6, 0, 19}
   x  =  51
Output: 3
Minimum length subarray is {4, 45, 6}

arr[] = {1, 10, 5, 2, 7}
   x  = 9
Output: 1
Minimum length subarray is {10}

arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}
    x = 280
Output: 4
Minimum length subarray is {100, 1, 0, 200}

arr[] = {1, 2, 4}
    x = 8
Output : Not Possible
Whole array sum is smaller than 8.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

 


 

A simple solution is to use two nested loops. The outer loop picks a starting element, the inner loop considers all elements (on right side of current start) as ending element. Whenever sum of elements between current start and end becomes more than the given number, update the result if current length is smaller than the smallest length so far.
Following is the implementation of simple approach.

C

# include 
using namespace std;

// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
int smallestSubWithSum(int arr[], int n, int x)
{
    //  Initilize length of smallest subarray as n+1
     int min_len = n + 1;

     // Pick every element as starting point
     for (int start=0; start x) return 1;

          // Try different ending points for curremt start
          for (int end=start+1; end x && (end - start + 1) 

Java

class SmallestSubArraySum
{
    // Returns length of smallest subarray with sum greater than x.
    // If there is no subarray with given sum, then returns n+1
    static int smallestSubWithSum(int arr[], int n, int x)
    {
        //  Initilize length of smallest subarray as n+1
        int min_len = n + 1;

        // Pick every element as starting point
        for (int start = 0; start  x)
                return 1;

            // Try different ending points for curremt start
            for (int end = start + 1; end  x && (end - start + 1) 

Python3

# Python3  program to find Smallest 
# subarray with sum greater 
# than a given value

# Returns length of smallest subarray
# with sum greater than x. If there
# is no subarray with given sum, 
# then returns n+1
def smallestSubWithSum(arr, n, x):

    # Initilize length of smallest
    # subarray as n+1
    min_len = n + 1

    # Pick every element as starting point
    for start in range(0,n):
    
        # Initialize sum starting 
        # with current start
        curr_sum = arr[start]

        # If first element itself is greater
        if (curr_sum > x):
            return 1

        # Try different ending points
        # for curremt start
        for end in range(start+1,n):
        
            # add last element to current sum
            curr_sum += arr[end]

            # If sum becomes more than x 
            # and length of this subarray
            # is smaller than current smallest
            # length, update the smallest 
            # length (or result)
            if curr_sum > x and (end - start + 1) 

Output:

3
1
4

Time Complexity: Time complexity of the above approach is clearly O(n2).

Efficient Solution: This problem can be solved in O(n) time using the idea used in this post. Thanks to Ankit and Nitin for suggesting this optimized solution.

C++

// O(n) solution for finding smallest subarray with sum
// greater than x
#include 
using namespace std;

// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
int smallestSubWithSum(int arr[], int n, int x)
{
    // Initialize current sum and minimum length
    int curr_sum = 0, min_len = n+1;

    // Initialize starting and ending indexes
    int start = 0, end = 0;
    while (end  x && start 

Java

// O(n) solution for finding smallest subarray with sum
// greater than x

class SmallestSubArraySum
{
    // Returns length of smallest subarray with sum greater than x.
    // If there is no subarray with given sum, then returns n+1
    static int smallestSubWithSum(int arr[], int n, int x) 
    {
        // Initialize current sum and minimum length
        int curr_sum = 0, min_len = n + 1;

        // Initialize starting and ending indexes
        int start = 0, end = 0;
        while (end  x && start 

Python3

# O(n) solution for finding smallest
# subarray with sum greater than x

# Returns length of smallest subarray
# with sum greater than x. If there 
# is no subarray with given sum, then
# returns n + 1
def smallestSubWithSum(arr, n, x):

    # Initialize current sum and minimum length
    curr_sum = 0
    min_len = n + 1

    # Initialize starting and ending indexes
    start = 0
    end = 0
    while (end  x and start 

Output:

3
1
4

How to handle negative numbers?
The above solution may not work if input array contains negative numbers. For example arr[] = {- 8, 1, 4, 2, -6}. To handle negative numbers, add a condition to ignore subarrays with negative sums.

// O(n) solution for finding smallest subarray with sum
// greater than x
#include 
using namespace std;

// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
int smallestSubWithSum(int arr[], int n, int x)
{
    // Initialize current sum and minimum length
    int curr_sum = 0, min_len = n+1;

    // Initialize starting and ending indexes
    int start = 0, end = 0;
    while (end  0)
            {
                start = end;
                curr_sum = 0;
            }

            curr_sum += arr[end++];
        }

        // If current sum becomes greater than x.
        while (curr_sum > x && start 

Output:

3

This article is contributed by Rahul Jain.

From:GeeksforGeeks