Problem

Given an array of integers and a target integer x, find the length of the smallest subarray whose sum is greater than x. If no such subarray exists, return 0.

Examples

Example 1:

1
2
3

Input: arr = [1, 4, 45, 6, 0, 19], x = 51
Output: 3
Explanation: The smallest subarray with sum greater than 51 is [4, 45, 6] with length 3.

Example 2:

1
2
3

Input: arr = [1, 10, 5, 2, 7], x = 9
Output: 1
Explanation: The smallest subarray with sum greater than 9 is [10] with length 1.

Example 3:

1
2
3

Input: arr = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250], x = 280
Output: 4
Explanation: The smallest subarray with sum greater than 280 is [100, 1, 0, 200] with length 4.

Example 4:

1
2
3

Input: arr = [1, 2, 4], x = 8
Output: 0
Explanation: Even the sum of all elements is not greater than 8.

Solution

Method 1 - Naive approach

Generate all the subarrays using 2 loops, and find the smallest subarray with sum larger than x. Time Complexity – O(n^2).

Method 2 - Sliding Window Technique

To solve this problem efficiently, we can use the sliding window technique. The sliding window technique involves expanding and contracting a window over the array to find the smallest subarray with a sum greater than the given integer x.

Here are the steps:

  1. Initialize two pointers (start and end) and a variable to keep track of the current sum.
  2. Use a loop to expand the window by moving the end pointer and adding the current element to the sum.
  3. Whenever the current sum exceeds x, increment the start pointer to reduce the size of the window and update the minimum length whenever a smaller subarray is found.
  4. Return the minimum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int x) {
        int n = arr.length;
        int minLen = n + 1;
        int start = 0;
        int end = 0;
        int currentSum = 0;

        while (end < n) {
            // Keep adding array elements while currentSum is less than or equal
            // to x
            while (currentSum <= x && end < n) {
                currentSum += arr[end];
                end++;
            }

            // If currentSum becomes greater than x, update the minLen
            while (currentSum > x && start < n) {
                if (end - start < minLen) {
                    minLen = end - start;
                }
                currentSum -= arr[start];
                start++;
            }
        }

        return minLen <= n ? minLen : 0;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr1 = {1, 4, 45, 6, 0, 19};
        int x1 = 51;
        System.out.println(
            solution.smallestSubarrayWithSum(arr1, x1)); // Output: 3

        int[] arr2 = {1, 10, 5, 2, 7};
        int x2 = 9;
        System.out.println(
            solution.smallestSubarrayWithSum(arr2, x2)); // Output: 1

        int[] arr3 = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
        int x3 = 280;
        System.out.println(
            solution.smallestSubarrayWithSum(arr3, x3)); // Output: 4

        int[] arr4 = {1, 2, 4};
        int x4 = 8;
        System.out.println(
            solution.smallestSubarrayWithSum(arr4, x4)); // Output: 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def smallest_subarray_with_sum(arr, x):
    n = len(arr)
    min_len = n + 1
    start = 0
    end = 0
    current_sum = 0

    while end < n:
        # Keep adding array elements while current_sum is less than or equal to x
        while current_sum <= x and end < n:
            current_sum += arr[end]
            end += 1

        # If current_sum becomes greater than x, update the min_len
        while current_sum > x and start < n:
            if end - start < min_len:
                min_len = end - start
            current_sum -= arr[start]
            start += 1

    return min_len if min_len <= n else 0


# Example usage:
arr1 = [1, 4, 45, 6, 0, 19]
x1 = 51
print(smallest_subarray_with_sum(arr1, x1))  # Output: 3

arr2 = [1, 10, 5, 2, 7]
x2 = 9
print(smallest_subarray_with_sum(arr2, x2))  # Output: 1

arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
x3 = 280
print(smallest_subarray_with_sum(arr3, x3))  # Output: 4

arr4 = [1, 2, 4]
x4 = 8
print(smallest_subarray_with_sum(arr4, x4))  # Output: 0

Complexity

  • ⏰ Time complexity: O(n), because each element is processed at most twice.
  • 🧺 Space complexity: O(1), because we use only a constant amount of extra space.