Smallest Subarray with sum greater than a given value

Problem Statement

Given an array of positive integers and a value x, find the length of the smallest contiguous subarray whose sum is greater than or equal to x. Return 0 if no such subarray exists.

Example:

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

Approach 1: Brute Force

Intuition

Try all possible subarrays and find the smallest one with sum ≥ x.

Algorithm

1. For each starting index i
2. Expand to all ending indices j
3. Calculate sum and check if ≥ x
4. Track minimum length

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int x) {
        int n = arr.length;
        int minLen = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                
                if (currentSum >= x) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;  // No need to extend further
                }
            }
        }
        
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Nested loops over all subarrays
• Space Complexity: O(1) - Only constant extra space

Approach 2: Optimal - Sliding Window

Intuition

Use two pointers to maintain a sliding window. Expand the window to increase sum, shrink from left when sum exceeds x to find minimum length.

Algorithm

1. Initialize start = 0, currentSum = 0, minLen = infinity
2. For each end from 0 to n-1:
   • Add arr[end] to currentSum
   • While currentSum >= x:
     • Update minLen
     • Remove arr[start] and increment start
3. Return minLen if found, else 0

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int x) {
        int n = arr.length;
        int minLen = Integer.MAX_VALUE;
        int currentSum = 0;
        int start = 0;
        
        for (int end = 0; end < n; end++) {
            currentSum += arr[end];
            
            // Shrink window while sum >= x
            while (currentSum >= x) {
                minLen = Math.min(minLen, end - start + 1);
                currentSum -= arr[start];
                start++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each element is added and removed at most once
• Space Complexity: O(1) - Only constant extra space

Approach 3: Binary Search on Prefix Sums (For Non-Negative Arrays)

Intuition

Build prefix sum array. For each index, binary search for the smallest index where prefix sum difference is ≥ x.

Algorithm

1. Build prefix sum array
2. For each index i, binary search for smallest j where prefix[j] - prefix[i] >= x
3. Track minimum length

import java.util.Arrays;

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int x) {
        int n = arr.length;
        
        // Build prefix sum array
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        
        int minLen = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            // Binary search for smallest j where prefix[j] - prefix[i] >= x
            long target = prefix[i] + x;
            int j = lowerBound(prefix, i + 1, n + 1, target);
            
            if (j <= n) {
                minLen = Math.min(minLen, j - i);
            }
        }
        
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
    
    private int lowerBound(long[] arr, int start, int end, long target) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - n binary searches, each O(log n)
• Space Complexity: O(n) - Prefix sum array

Variation: With Negative Numbers (Deque Approach)

Intuition

For arrays with negative numbers, sliding window doesn't work directly. Use a deque to maintain indices of increasing prefix sums.

Complexity Analysis

• Time Complexity: O(n) - Each index added and removed at most once
• Space Complexity: O(n) - Deque and prefix array

Key Takeaways

1. Sliding window for positive arrays - O(n) solution when all elements are positive
2. Two pointers technique - Expand right to increase sum, shrink left to find minimum
3. Binary search on prefix sums - Alternative O(n log n) approach
4. Negative numbers require different approach - Deque-based solution handles negative values
5. Similar problems - Maximum subarray sum, minimum window substring