Python – Find the Smallest Subarray with Sum Greater Than a Given Value

This tutorial explains how to find the smallest contiguous subarray in a given array whose sum is greater than a specified value. This problem is a common interview question in data structures and algorithms (DSA) and can be efficiently solved using the sliding window technique.

Problem Statement

Given an array of positive integers arr and a target sum S, determine the minimum length of a contiguous subarray for which the sum of its elements is greater than S. If no such subarray exists, return an appropriate indicator (such as 0).

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [2, 3, 1, 2, 4, 3], S = 7
Output: 3
Explanation: The subarray [4, 3] has a sum of 7 and is the smallest subarray with sum > 7.

Example 2:

</>
Copy
Input: arr = [1, 10, 5, 2, 7], S = 9
Output: 1
Explanation: The element [10] itself is greater than 9, making it the smallest subarray.

Solution Approach

We can solve this problem using the sliding window technique with the following steps:

  1. Initialize variables: Set start = 0, current_sum = 0, and min_length = infinity (or a very large number) to keep track of the smallest subarray length.
  2. Expand the window: Iterate over the array with an index end, adding each element to current_sum.
  3. Contract the window: When current_sum > S, try to shrink the window from the left by subtracting the element at start and incrementing start. Update min_length whenever a smaller valid window is found.
  4. Return the result: After processing the array, if min_length is updated, return its value; otherwise, return 0 (or an appropriate value) if no valid subarray exists.

Python Program

</>
Copy
def smallest_subarray_with_sum(arr, S):
    n = len(arr)
    min_length = float("inf")
    current_sum = 0
    start = 0

    for end in range(n):
        current_sum += arr[end]
        
        # Contract the window as long as the current sum is greater than S
        while current_sum > S:
            min_length = min(min_length, end - start + 1)
            current_sum -= arr[start]
            start += 1

    # Return the smallest length if found; otherwise, return 0 indicating no valid subarray exists
    return min_length if min_length != float("inf") else 0

# Example 1
arr1 = [2, 3, 1, 2, 4, 3]
S1 = 7
print("Smallest subarray length:", smallest_subarray_with_sum(arr1, S1))

# Example 2
arr2 = [1, 10, 5, 2, 7]
S2 = 9
print("Smallest subarray length:", smallest_subarray_with_sum(arr2, S2))

Conclusion

The sliding window technique provides an efficient solution with a time complexity of O(n) for finding the smallest subarray with a sum greater than a given value.