Data Modelling & AI Data Structure & Algorithm

Smallest subarray with sum greater than a given value

31 July 2024

0

Given an array arr[] of integers and a number x, the task is to find the smallest subarray with a 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.

Naive approach: 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.

Below is the implementation of the above approach:

C++

# include <iostream>
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 length of smallest subarray as n+1
     int min_len = n + 1;
 
     // Pick every element as starting point
     for (int start=0; start<n; start++)
     {
          // Initialize sum starting with current start
          int curr_sum = arr[start];
 
          // If first element itself is greater
          if (curr_sum > x) return 1;
 
          // Try different ending points for current start
          for (int end=start+1; end<n; end++)
          {
              // 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 && (end - start + 1) < min_len)
                 min_len = (end - start + 1);
          }
     }
     return min_len;
}
 
/* Driver program to test above function */
int main()
{
    int arr1[] = {1, 4, 45, 6, 10, 19};
    int x = 51;
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    int res1 = smallestSubWithSum(arr1, n1, x);
    (res1 == n1+1)? cout << "Not possible\n" :
                    cout << res1 << endl;
 
    int arr2[] = {1, 10, 5, 2, 7};
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    x  = 9;
    int res2 = smallestSubWithSum(arr2, n2, x);
    (res2 == n2+1)? cout << "Not possible\n" :
                    cout << res2 << endl;
 
    int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
    int n3 = sizeof(arr3)/sizeof(arr3[0]);
    x  = 280;
    int res3 = smallestSubWithSum(arr3, n3, x);
    (res3 == n3+1)? cout << "Not possible\n" :
                    cout << res3 << endl;
 
    return 0;
}

Java

import java.io.*;
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 length of smallest subarray as n+1
        int min_len = n + 1;
 
        // Pick every element as starting point
        for (int start = 0; start < n; start++)
        {
            // Initialize sum starting with current start
            int curr_sum = arr[start];
 
            // If first element itself is greater
            if (curr_sum > x)
                return 1;
 
            // Try different ending points for current start
            for (int end = start + 1; end < n; end++)
            {
                // 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 && (end - start + 1) < min_len)
                    min_len = (end - start + 1);
            }
        }
        return min_len;
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int arr1[] = {1, 4, 45, 6, 10, 19};
        int x = 51;
        int n1 = arr1.length;
        int res1 = smallestSubWithSum(arr1, n1, x);
        if (res1 == n1+1)
           System.out.println("Not Possible");
        else
           System.out.println(res1);
 
 
        int arr2[] = {1, 10, 5, 2, 7};
        int n2 = arr2.length;
        x = 9;
        int res2 = smallestSubWithSum(arr2, n2, x);
        if (res2 == n2+1)
           System.out.println("Not Possible");
        else
           System.out.println(res2);
 
        int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
        int n3 = arr3.length;
        x = 280;
        int res3 = smallestSubWithSum(arr3, n3, x);
        if (res3 == n3+1)
           System.out.println("Not Possible");
        else
           System.out.println(res3);
    }
}
 
// This code has been contributed by Mayank Jaiswal

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):
 
    # Initialize 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 current 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) < min_len:
                min_len = (end - start + 1)
         
    return min_len;
 
 
# Driver program to test above function */
arr1 = [1, 4, 45, 6, 10, 19]
x = 51
n1 = len(arr1)
res1 = smallestSubWithSum(arr1, n1, x);
if res1 == n1+1:
    print("Not possible")
else:
    print(res1)
 
arr2 = [1, 10, 5, 2, 7]
n2 = len(arr2)
x = 9
res2 = smallestSubWithSum(arr2, n2, x);
if res2 == n2+1:
    print("Not possible")
else:
    print(res2)
 
arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
n3 = len(arr3)
x = 280
res3 = smallestSubWithSum(arr3, n3, x)
if res3 == n3+1:
    print("Not possible") 
else:
    print(res3)
     
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to find Smallest 
// subarray with sum greater 
// than a given value
using System;
 
class GFG
{
     
    // 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 length of 
        // smallest subarray as n+1
        int min_len = n + 1;
 
        // Pick every element
        // as starting point
        for (int start = 0; start < n; start++)
        {
            // Initialize sum starting
            // with current start
            int curr_sum = arr[start];
 
            // If first element
            // itself is greater
            if (curr_sum > x)
                return 1;
 
            // Try different ending 
            // points for current start
            for (int end = start + 1; 
                     end < n; end++)
            {
                // 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 && 
                        (end - start + 1) < min_len)
                    min_len = (end - start + 1);
            }
        }
        return min_len;
    }
 
    // Driver Code
    static public void Main ()
    {
        int []arr1 = {1, 4, 45, 
                      6, 10, 19};
        int x = 51;
        int n1 = arr1.Length;
        int res1 = smallestSubWithSum(arr1, 
                                      n1, x);
        if (res1 == n1 + 1)
        Console.WriteLine("Not Possible");
        else
        Console.WriteLine(res1);
 
 
        int []arr2 = {1, 10, 5, 2, 7};
        int n2 = arr2.Length;
        x = 9;
        int res2 = smallestSubWithSum(arr2, 
                                      n2, x);
        if (res2 == n2 + 1)
        Console.WriteLine("Not Possible");
        else
        Console.WriteLine(res2);
 
        int []arr3 = {1, 11, 100, 1, 0, 
                      200, 3, 2, 1, 250};
        int n3 = arr3.Length;
        x = 280;
        int res3 = smallestSubWithSum(arr3, 
                                      n3, x);
        if (res3 == n3 + 1)
        Console.WriteLine("Not Possible");
        else
        Console.WriteLine(res3);
    }
}
 
// This code is contributed by ajit

Javascript

<script>
 
// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
function smallestSubWithSum(arr, n, x)
{
 
    // Initialize length of smallest subarray as n+1
    let min_len = n + 1;
 
    // Pick every element as starting point
    for (let start=0; start<n; start++)
    {
     
        // Initialize sum starting with current start
        let curr_sum = arr[start];
 
        // If first element itself is greater
        if (curr_sum > x) return 1;
 
        // Try different ending points for current start
        for (let end=start+1; end<n; end++)
        {
         
            // 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 && (end - start + 1) < min_len)
                min_len = (end - start + 1);
        }
    }
    return min_len;
}
 
/* Driver program to test above function */
    let arr1 = [1, 4, 45, 6, 10, 19];
    let x = 51;
    let n1 = arr1.length;
    let res1 = smallestSubWithSum(arr1, n1, x);
    (res1 == n1 + 1)? document.write("Not possible<br>") :
                    document.write(res1 + "<br>");
 
    let arr2 = [1, 10, 5, 2, 7];
    let n2 = arr2.length;
    x = 9;
    let res2 = smallestSubWithSum(arr2, n2, x);
    (res2 == n2 + 1)? document.write("Not possible<br>") :
                    document.write(res2 + "<br>");
 
    let arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250];
    let n3 = arr3.length;
    x = 280;
    let res3 = smallestSubWithSum(arr3, n3, x);
    (res3 == n3 + 1)? document.write("Not possible<br>") :
                    document.write(res3 + "<br>");
 
// This code is contributed by Surbhi Tyagi.
</script>

PHP

<?php
// Returns length of smallest 
// subarray with sum greater 
// than x. If there is no 
// subarray with given sum, 
// then returns n+1
function smallestSubWithSum($arr, $n, $x)
{
    // Initialize length of 
    // smallest subarray as n+1
    $min_len = $n + 1;
 
    // Pick every element 
    // as starting point
    for ($start = 0; $start < $n; $start++)
    {
        // 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 current start
        for ($end= $start + 1; $end < $n; $end++)
        {
            // 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 && 
                   ($end - $start + 1) < $min_len)
                $min_len = ($end - $start + 1);
        }
    }
    return $min_len;
}
 
// Driver Code
$arr1 = array (1, 4, 45, 
               6, 10, 19);
$x = 51;
$n1 = sizeof($arr1);
$res1 = smallestSubWithSum($arr1, $n1, $x);
 
if (($res1 == $n1 + 1) == true)
    echo "Not possible\n" ;
else
    echo $res1 , "\n";
 
$arr2 = array(1, 10, 5, 2, 7);
$n2 = sizeof($arr2);
$x = 9;
$res2 = smallestSubWithSum($arr2, $n2, $x);
 
if (($res2 == $n2 + 1) == true) 
    echo "Not possible\n" ;
else
    echo $res2 , "\n";
 
$arr3 = array (1, 11, 100, 1, 0,
               200, 3, 2, 1, 250);
$n3 = sizeof($arr3);
$x = 280;
$res3 = smallestSubWithSum($arr3, $n3, $x);
if (($res3 == $n3 + 1) == true)
    echo "Not possible\n" ;
else
    echo $res3 , "\n";
 
// This code is contributed by ajit
?>

Output

3
1
4

Time Complexity: O(n²).
Auxiliary Space: O(1)

Efficient Solution: This problem can be solved in O(n) time using the idea used in this post.

C++14

// O(n) solution for finding smallest subarray with sum
// greater than x
#include <iostream>
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 < n) {
        // Keep adding array elements while current sum
        // is smaller than or equal to x
        while (curr_sum <= x && end < n)
            curr_sum += arr[end++];
 
        // If current sum becomes greater than x.
        while (curr_sum > x && start < n) {
            // Update minimum length if needed
            if (end - start < min_len)
                min_len = end - start;
 
            // remove starting elements
            curr_sum -= arr[start++];
        }
    }
    return min_len;
}
 
/* Driver program to test above function */
int main()
{
    int arr1[] = { 1, 4, 45, 6, 10, 19 };
    int x = 51;
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int res1 = smallestSubWithSum(arr1, n1, x);
    (res1 == n1 + 1) ? cout << "Not possible\n"
                     : cout << res1 << endl;
 
    int arr2[] = { 1, 10, 5, 2, 7 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    x = 9;
    int res2 = smallestSubWithSum(arr2, n2, x);
    (res2 == n2 + 1) ? cout << "Not possible\n"
                     : cout << res2 << endl;
 
    int arr3[] = { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    x = 280;
    int res3 = smallestSubWithSum(arr3, n3, x);
    (res3 == n3 + 1) ? cout << "Not possible\n"
                     : cout << res3 << endl;
 
    return 0;
}

Java

// O(n) solution for finding smallest subarray with sum
// greater than x
import java.io.*;
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 < n) {
            // Keep adding array elements while current sum
            // is smaller than or equal to x
            while (curr_sum <= x && end < n)
                curr_sum += arr[end++];
 
            // If current sum becomes greater than x.
            while (curr_sum > x && start < n) {
                // Update minimum length if needed
                if (end - start < min_len)
                    min_len = end - start;
 
                // remove starting elements
                curr_sum -= arr[start++];
            }
        }
        return min_len;
    }
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int arr1[] = { 1, 4, 45, 6, 10, 19 };
        int x = 51;
        int n1 = arr1.length;
        int res1 = smallestSubWithSum(arr1, n1, x);
        if (res1 == n1 + 1)
            System.out.println("Not Possible");
        else
            System.out.println(res1);
 
        int arr2[] = { 1, 10, 5, 2, 7 };
        int n2 = arr2.length;
        x = 9;
        int res2 = smallestSubWithSum(arr2, n2, x);
        if (res2 == n2 + 1)
            System.out.println("Not Possible");
        else
            System.out.println(res2);
 
        int arr3[]
            = { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
        int n3 = arr3.length;
        x = 280;
        int res3 = smallestSubWithSum(arr3, n3, x);
        if (res3 == n3 + 1)
            System.out.println("Not Possible");
        else
            System.out.println(res3);
    }
}
 
// This code has been contributed by Mayank Jaiswal

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 < n):
 
        # Keep adding array elements while current
        # sum is smaller than or equal to x
        while (curr_sum <= x and end < n):
            curr_sum += arr[end]
            end += 1
 
        # If current sum becomes greater than x.
        while (curr_sum > x and start < n):
 
            # Update minimum length if needed
            if (end - start < min_len):
                min_len = end - start
 
            # remove starting elements
            curr_sum -= arr[start]
            start += 1
 
    return min_len
 
 
# Driver program
arr1 = [1, 4, 45, 6, 10, 19]
x = 51
n1 = len(arr1)
res1 = smallestSubWithSum(arr1, n1, x)
print("Not possible") if (res1 == n1 + 1) else print(res1)
 
arr2 = [1, 10, 5, 2, 7]
n2 = len(arr2)
x = 9
res2 = smallestSubWithSum(arr2, n2, x)
print("Not possible") if (res2 == n2 + 1) else print(res2)
 
arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
n3 = len(arr3)
x = 280
res3 = smallestSubWithSum(arr3, n3, x)
print("Not possible") if (res3 == n3 + 1) else print(res3)
 
# This code is contributed by
# Smitha Dinesh Semwal

C#

// O(n) solution for finding
// smallest subarray with sum
// greater than x
using System;
 
class GFG {
 
    // 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 < n) {
            // Keep adding array elements
            // while current sum is smaller
            // than or equal to x
            while (curr_sum <= x && end < n)
                curr_sum += arr[end++];
 
            // If current sum becomes
            // greater than x.
            while (curr_sum > x && start < n) {
                // Update minimum
                // length if needed
                if (end - start < min_len)
                    min_len = end - start;
 
                // remove starting elements
                curr_sum -= arr[start++];
            }
        }
        return min_len;
    }
 
    // Driver Code
    static public void Main()
    {
        int[] arr1 = { 1, 4, 45, 6, 10, 19 };
        int x = 51;
        int n1 = arr1.Length;
        int res1 = smallestSubWithSum(arr1, n1, x);
        if (res1 == n1 + 1)
            Console.WriteLine("Not Possible");
        else
            Console.WriteLine(res1);
 
        int[] arr2 = { 1, 10, 5, 2, 7 };
        int n2 = arr2.Length;
        x = 9;
        int res2 = smallestSubWithSum(arr2, n2, x);
        if (res2 == n2 + 1)
            Console.WriteLine("Not Possible");
        else
            Console.WriteLine(res2);
 
        int[] arr3
            = { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
        int n3 = arr3.Length;
        x = 280;
        int res3 = smallestSubWithSum(arr3, n3, x);
        if (res3 == n3 + 1)
            Console.WriteLine("Not Possible");
        else
            Console.WriteLine(res3);
    }
}
 
// This code is contributed by akt_mit

Javascript

<script>
// 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
function smallestSubWithSum(arr, n, x)
{
    // Initialize current sum and minimum length
    let curr_sum = 0, min_len = n + 1;
 
    // Initialize starting and ending indexes
    let start = 0, end = 0;
    while (end < n) {
        // Keep adding array elements while current sum
        // is smaller than or equal to x
        while (curr_sum <= x && end < n)
            curr_sum += arr[end++];
 
        // If current sum becomes greater than x.
        while (curr_sum > x && start < n) {
            // Update minimum length if needed
            if (end - start < min_len)
                min_len = end - start;
 
            // remove starting elements
            curr_sum -= arr[start++];
        }
    }
    return min_len;
}
 
/* Driver program to test above function */
let arr1 = [ 1, 4, 45, 6, 10, 19 ];
let x = 51;
let n1 = arr1.length;
let res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1 + 1) ? document.write("Not possible<br>")
    : document.write(res1 + "<br>");
 
let arr2 = [ 1, 10, 5, 2, 7 ];
let n2 = arr2.length;
x = 9;
let res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2 + 1) ? document.write("Not possible<br>")
    : document.write(res2 + "<br>");
 
let arr3 = [ 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 ];
let n3 = arr3.length;
x = 280;
let res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3 + 1) ? document.write("Not possible<br>")
    : document.write(res3 + "<br>");
     
    // This code is contributed by subham348.
</script>

PHP

<?php
// 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
function 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 < $n)
    {
        // Keep adding array elements 
        // while current sum is smaller
        // than or equal to x
        while ($curr_sum <= $x && 
               $end < $n)
            $curr_sum += $arr[$end++];
 
        // If current sum becomes
        // greater than x.
        while ($curr_sum > $x &&
               $start < $n)
        {
            // Update minimum
            // length if needed
            if ($end - $start < $min_len)
                $min_len = $end - $start;
 
            // remove starting elements
            $curr_sum -= $arr[$start++];
        }
    }
    return $min_len;
}
 
// Driver Code
$arr1 = array(1, 4, 45, 
              6, 10, 19);
$x = 51;
$n1 = sizeof($arr1);
$res1 = smallestSubWithSum($arr1, 
  
                           $n1, $x);
if($res1 == $n1 + 1) 
echo "Not possible\n" ;
else
echo $res1 ,"\n";
 
$arr2 = array(1, 10, 5, 2, 7);
$n2 = sizeof($arr2);
$x = 9;
$res2 = smallestSubWithSum($arr2, 
                           $n2, $x);
if($res2 == $n2 + 1) 
echo "Not possible\n" ;
else
echo $res2,"\n";
 
$arr3 = array(1, 11, 100, 1, 0, 
              200, 3, 2, 1, 250);
$n3 = sizeof($arr3);
$x = 280;
$res3 = smallestSubWithSum($arr3, 
                           $n3, $x);
                            
if($res3 == $n3 + 1)
echo "Not possible\n" ;
else
echo $res3, "\n";
 
// This code is contributed by ajit
?>

Output

3
1
4

Time Complexity: O(n).
Auxiliary Space: O(1)

Another Approach: Binary Search

First calculates the cumulative sum of the vector elements and stores them in the sums vector.
Then iterates through the sums vector and finds the lower bound of the target sum for each possible subarray.
If the lower bound is found and it’s not equal to the target sum (i.e., the subarray sum is greater than the target),
Calculates the length of the subarray and updates the ans variable if the length is smaller than the current value.
Finally, returns the ans value or 0 if ans was not updated.

C++

// O(n log(n) solution for finding smallest subarray with
// sum greater than x
#include <bits/stdc++.h>
using namespace std;
 
int smallestSubArrayLen(int target, vector<int>& nums)
{
    // Get the length of the input vector
    int n = nums.size();
    // If the vector is empty, return 0
    if (n == 0)
        return 0;
    // Initialize the minimum subarray length to INT_MAX-1
    int ans = INT_MAX - 1;
    // Create a new vector "sums" with size n+1, initialized
    // to all zeros
    vector<int> sums(n + 1, 0);
    // Compute the running sum of nums and store it in
    // "sums"
    for (int i = 1; i <= n; i++)
        sums[i] = sums[i - 1] + nums[i - 1];
    // Iterate through each starting index i
    for (int i = 1; i <= n; i++) {
        // Calculate the target sum for the subarray
        // starting at index i
        int to_find = target + sums[i - 1];
        // Find the first element in "sums" that is >=
        // to_find
        auto bound = lower_bound(sums.begin(), sums.end(),
                                 to_find);
        // If such an element is found and it is not equal
        // to to_find itself
        if (bound != sums.end() && *bound != to_find) {
            // Compute the length of the subarray and update
            // ans if necessary
            int len = bound - (sums.begin() + i - 1);
            ans = min(ans, len);
        }
    }
    // Return ans if it was updated, otherwise return 0
    return (ans != INT_MAX - 1) ? ans : 0;
}
 
/* Driver program to test above function */
int main()
{
    vector<int> arr1 = { 1, 4, 45, 6, 10, 19 };
    int target1 = 51;
    cout << "Length of Smallest Subarray :"
         << smallestSubArrayLen(target1, arr1) << endl;
 
    vector<int> arr2 = { 1, 10, 5, 2, 7 };
    int target2 = 9;
    cout << "Length of Smallest Subarray :"
         << smallestSubArrayLen(target2, arr2) << endl;
 
    vector<int> arr3 = { 1, 1, 1, 1, 1, 1, 1, 1 };
    int target3 = 11;
    cout << "Length of Smallest Subarray :"
         << smallestSubArrayLen(target3, arr3) << endl;
 
    vector<int> arr4
        = { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
    int target4 = 280;
    cout << "Length of Smallest Subarray :"
         << smallestSubArrayLen(target4, arr4) << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class GFG {
    public static int smallestSubArrayLen(int target, int[] nums) {
        // Get the length of the input array
        int n = nums.length;
        // If the array is empty, return 0
        if (n == 0) {
            return 0;
        }
        // Initialize the minimum subarray length to a large value
        int ans = Integer.MAX_VALUE;
        // Create a new array "sums" with size n+1, initialized to all zeros
        int[] sums = new int[n + 1];
        // Compute the running sum of nums and store it in "sums"
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        // Iterate through each starting index i
        for (int i = 1; i <= n; i++) {
            // Calculate the target sum for the subarray starting at index i
            int toFind = target + sums[i - 1];
            // Find the first element in "sums" that is >= toFind
            int bound = Arrays.binarySearch(sums, toFind);
            if (bound < 0) {
                bound = -bound - 1;
            }
            // If such an element is found and it is not equal to toFind itself
            if (bound != sums.length && sums[bound] != toFind) {
                // Compute the length of the subarray and update ans if necessary
                int length = bound - (i - 1);
                ans = Math.min(ans, length);
            }
        }
        // Return ans if it was updated, otherwise return 0
        return (ans != Integer.MAX_VALUE) ? ans : 0;
    }
 
    public static void main(String[] args) {
        int[] arr1 = {1, 4, 45, 6, 10, 19};
        int target1 = 51;
        System.out.println("Length of Smallest Subarray: " + smallestSubArrayLen(target1, arr1));
 
        int[] arr2 = {1, 10, 5, 2, 7};
        int target2 = 9;
        System.out.println("Length of Smallest Subarray: " + smallestSubArrayLen(target2, arr2));
 
        int[] arr3 = {1, 1, 1, 1, 1, 1, 1, 1};
        int target3 = 11;
        System.out.println("Length of Smallest Subarray: " + smallestSubArrayLen(target3, arr3));
 
        int[] arr4 = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
        int target4 = 280;
        System.out.println("Length of Smallest Subarray: " + smallestSubArrayLen(target4, arr4));
    }
}

Python3

# O(n log(n) solution for finding smallest subarray with
# sum greater than 
from bisect import bisect_left
# Function to find the smallest subarray length with a 
# sum greater than a target value
def smallestSubArrayLen(target, nums):
    # Get the length of the input list
    n = len(nums)
    # If the list is empty, return 0
    if n == 0:
        return 0
    # Initialize the minimum subarray length to a large value
    ans = float('inf')
    # Create a new list "sums" with size n+1, initialized to all zeros
    sums = [0] * (n + 1)
    # Compute the running sum of nums and store it in "sums"
    for i in range(1, n + 1):
        sums[i] = sums[i - 1] + nums[i - 1]
    # Iterate through each starting index i
    for i in range(1, n + 1):
        # Calculate the target sum for the subarray starting at index i
        to_find = target + sums[i - 1]
        # Find the first element in "sums" that is >= to_find
        bound = bisect_left(sums, to_find)
        # If such an element is found and it is not equal to to_find itself
        if bound != len(sums) and sums[bound] != to_find:
            # Compute the length of the subarray and update ans if necessary
            length = bound - (i - 1)
            ans = min(ans, length)
    # Return ans if it was updated, otherwise return 0
    return ans if ans != float('inf') else 0
 
# Driver code to test the function
arr1 = [1, 4, 45, 6, 10, 19]
target1 = 51
print("Length of Smallest Subarray:", smallestSubArrayLen(target1, arr1))
 
arr2 = [1, 10, 5, 2, 7]
target2 = 9
print("Length of Smallest Subarray:", smallestSubArrayLen(target2, arr2))
 
arr3 = [1, 1, 1, 1, 1, 1, 1, 1]
target3 = 11
print("Length of Smallest Subarray:", smallestSubArrayLen(target3, arr3))
 
arr4 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
target4 = 280
print("Length of Smallest Subarray:", smallestSubArrayLen(target4, arr4))

C#

// Nikunj Sonigara
 
using System;
using System.Collections.Generic;
 
class Program
{
    // Function to find the length of the smallest subarray whose sum is greater than or equal to the target.
    static int SmallestSubArrayLen(int target, List<int> nums)
    {
        int n = nums.Count;
        if (n == 0)
            return 0;
 
        int ans = int.MaxValue - 1;
        List<int> sums = new List<int>(n + 1);
 
        sums.Add(0);
 
        // Calculate the cumulative sum of the elements in the 'nums' list.
        for (int i = 1; i <= n; i++)
            sums.Add(sums[i - 1] + nums[i - 1]);
 
        for (int i = 1; i <= n; i++)
        {
            int toFind = target + sums[i - 1];
 
            // Use binary search to find the index in 'sums' where 'toFind' would be located.
            int bound = BinarySearch(sums, toFind);
 
            if (bound != sums.Count && sums[bound] != toFind)
            {
                // Calculate the length of the subarray and update the 'ans' if it's smaller.
                int len = bound - (i - 1);
                ans = Math.Min(ans, len);
            }
        }
 
        // If no subarray was found, return 0. Otherwise, return the minimum length found.
        return (ans != int.MaxValue - 1) ? ans : 0;
    }
 
    // Binary search to find the index of the target sum in the 'sums' list.
    static int BinarySearch(List<int> sums, int target)
    {
        int left = 0;
        int right = sums.Count - 1;
 
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
 
            if (sums[mid] == target)
                return mid;
            else if (sums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
 
        return left;
    }
 
    static void Main()
    {
        List<int> arr1 = new List<int> { 1, 4, 45, 6, 10, 19 };
        int target1 = 51;
        Console.WriteLine("Length of Smallest Subarray: " + SmallestSubArrayLen(target1, arr1));
 
        List<int> arr2 = new List<int> { 1, 10, 5, 2, 7 };
        int target2 = 9;
        Console.WriteLine("Length of Smallest Subarray: " + SmallestSubArrayLen(target2, arr2));
 
        List<int> arr3 = new List<int> { 1, 1, 1, 1, 1, 1, 1, 1 };
        int target3 = 11;
        Console.WriteLine("Length of Smallest Subarray: " + SmallestSubArrayLen(target3, arr3));
 
        List<int> arr4 = new List<int> { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
        int target4 = 280;
        Console.WriteLine("Length of Smallest Subarray: " + SmallestSubArrayLen(target4, arr4));
    }
}

Javascript

// O(n log(n) solution for finding smallest subarray with
// sum greater than x
 
// Function to find the smallest subarray length with a 
// sum greater than a target value
function smallestSubArrayLen(target, nums) {
// Get the length of the input array
let n = nums.length;
// If the array is empty, return 0
if (n === 0)
return 0;
// Initialize the minimum subarray length to Infinity
let ans = Infinity;
// Create a new array "sums" with size n+1, initialized
// to all zeros
let sums = new Array(n + 1).fill(0);
// Compute the running sum of nums and store it in "sums"
for (let i = 1; i <= n; i++)
sums[i] = sums[i - 1] + nums[i - 1];
// Iterate through each starting index i
for (let i = 1; i <= n; i++) {
// Calculate the target sum for the subarray
// starting at index i
let to_find = target + sums[i - 1];
// Find the first element in "sums" that is >= to_find
let bound = sums.findIndex((element) => element >= to_find);
// If such an element is found and it is not equal to to_find itself
if (bound !== -1 && sums[bound] !== to_find) {
// Compute the length of the subarray and update ans if necessary
let len = bound - (i - 1);
ans = Math.min(ans, len);
}
}
// Return ans if it was updated, otherwise return 0
return (ans !== Infinity) ? ans : 0;
}
 
/* Driver program to test above function */
let arr1 = [1, 4, 45, 6, 10, 19];
let target1 = 51;
console.log("Length of Smallest Subarray: " + smallestSubArrayLen(target1, arr1));
 
let arr2 = [1, 10, 5, 2, 7];
let target2 = 9;
console.log("Length of Smallest Subarray: " + smallestSubArrayLen(target2, arr2));
 
let arr3 = [1, 1, 1, 1, 1, 1, 1, 1];
let target3 = 11;
console.log("Length of Smallest Subarray: " + smallestSubArrayLen(target3, arr3));
 
let arr4 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250];
let target4 = 280;
console.log("Length of Smallest Subarray: " + smallestSubArrayLen(target4, arr4));

Output

Length of Smallest Subarray :3
Length of Smallest Subarray :1
Length of Smallest Subarray :0
Length of Smallest Subarray :4

Time Complexity: O (n log(n)).
Auxiliary Space: O(n)
Thanks to Ankit and Nitin for suggesting this optimized solution.

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. We can use the solution discussed in Find subarray with given sum with negatives allowed in constant space

Asked in: Facebook

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Smallest subarray with sum greater than a given value

C++

Java

Python3

C#

Javascript

PHP

C++14

Java

Python3

C#

Javascript

PHP

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

Google wants to hear your thoughts on the Android 15 QPR2 Beta

Recent Comments

EDITOR PICKS

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

POPULAR POSTS

How to Secure Your Network-Attached Storage (NAS) in 2024 by Tyler Cross

8 Best Private Search Engines in 2024: Tested by Experts by Tyler Cross

The biggest comeback in tech history [Video]

POPULAR CATEGORY

ABOUT US

FOLLOW US