Find Smallest Subarray with Sum Greater than X

Title: Find Smallest Subarray with Sum Greater than X

In this guide, you’ll learn how to find the length of the smallest contiguous subarray whose sum is strictly greater than a given value x. This is a classic array problem that shows up often in coding interviews, and it’s a great way to practice the sliding window technique.

We’ll walk through why a brute force scan is too slow, then build up to an efficient O(n) solution using two pointers. By the end, you’ll be able to trace through the algorithm by hand and explain why it works.

Understanding the Problem

Given an array of positive integers arr and an integer x, you need to find the length of the smallest subarray whose sum is greater than x. A subarray is a contiguous block of elements, not just any subset. If no such subarray exists, the program should report that clearly instead of returning a misleading number.

The naive approach checks every possible subarray, computes its sum, and keeps track of the shortest one that qualifies. That works, but it costs O(n^2) time because there are O(n^2) subarrays and summing each one takes additional work. Since all elements are positive, there is a much faster way: a sliding window that expands and shrinks in a single pass.

Approach

1. Initialize two pointers, start and end, both at index 0, along with currSum = 0 and minLen set to arr.length + 1, a sentinel meaning ‘not found yet’.
2. Expand the window by moving end forward and adding arr[end] to currSum, as long as currSum is still less than or equal to x and end has not run past the array.
3. Once currSum exceeds x, shrink the window from the left: compare the current window length end - start to minLen and update minLen when it is smaller.
4. Subtract arr[start] from currSum and move start forward, then repeat the shrink check for as long as currSum is still greater than x.
5. Alternate between expanding and shrinking until end reaches the end of the array and no further shrinking is possible.
6. After the loop, if minLen is still arr.length + 1, no subarray satisfies the condition. Otherwise minLen is the answer.

Java Program

public class SmallestSubarrayWithSumGreaterThanX {

    public static int smallestSubWithSum(int[] arr, int x) {
        int n = arr.length;
        int minLen = n + 1;
        int currSum = 0;
        int start = 0;
        int end = 0;

        while (end < n) {
            while (currSum <= x && end < n) {
                currSum += arr[end];
                end++;
            }

            while (currSum > x && start < n) {
                if (end - start < minLen) {
                    minLen = end - start;
                }
                currSum -= arr[start];
                start++;
            }
        }

        return minLen;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 45, 6, 0, 19};
        int x = 51;

        int result = smallestSubWithSum(arr, x);

        if (result > arr.length) {
            System.out.println("No subarray found");
        } else {
            System.out.println("Length of smallest subarray: " + result);
        }
    }
}

Explanation of the Program

The method smallestSubWithSum keeps a running total in currSum for the window between start and end. The outer while (end < n) loop drives the whole scan, and inside it, two inner loops take turns expanding and shrinking the window.

The first inner loop grows the window by moving end forward and adding each new element to currSum, stopping as soon as the sum becomes greater than x or the array runs out.

The second inner loop shrinks the window from the left. Every time it removes an element, it first checks whether the current window length is the smallest one seen so far and updates minLen if so. The check happens before the subtraction, because the window is still valid, meaning its sum is greater than x, at that exact moment.

Because end only ever moves forward and start only ever moves forward, each index is visited by at most one pointer in each role. That bounded movement is what gives the algorithm its O(n) running time.

Step-by-Step Trace

Let's trace smallestSubWithSum on arr = [2, 3, 1, 2, 4, 3] with x = 7. The final answer is 3, coming from the window [1, 2, 4].

Round 2 is worth a second look: the window shrinks by one position, but the resulting length is not smaller than the best seen so far, so minLen stays unchanged. At the end of every round, minLen holds the length of the shortest window found so far whose sum is greater than x, and currSum is back at or below x so the next expansion starts from a clean, valid state.

Examples

Example 1: A Qualifying Subarray Exists

Input: arr = [1, 4, 45, 6, 0, 19], x = 51. The qualifying window is [4, 45, 6], with sum 55 and length 3.

int[] arr = {1, 4, 45, 6, 0, 19};
int x = 51;
System.out.println(smallestSubWithSum(arr, x));
// Output: 3

Example 2: No Subarray Satisfies the Condition

Input: arr = [1, 1, 1], x = 10. No contiguous subarray sums to more than 10, so the method returns the sentinel value arr.length + 1, which the caller should treat as 'not found'.

int[] arr = {1, 1, 1};
int x = 10;
int result = smallestSubWithSum(arr, x);
System.out.println(result > arr.length ? "No subarray found" : String.valueOf(result));
// Output: No subarray found

Example 3: A Single Element Satisfies the Condition

Input: arr = [10, 2, 3], x = 5. The very first element already exceeds x, so the smallest qualifying subarray has length 1.

int[] arr = {10, 2, 3};
int x = 5;
System.out.println(smallestSubWithSum(arr, x));
// Output: 1

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this sliding window on their own.

• Initializing minLen to 0 - returning 0 as a default makes it look like a zero-length subarray qualifies, when really no subarray has been found yet. Initialize minLen to arr.length + 1 so an unfound answer can never be confused with a real one.
• Using >= instead of > - the problem asks for a sum strictly greater than x, so comparing with currSum >= x accepts windows that merely equal x and returns a length that is too short.
• Shrinking with if instead of while - a single if only removes one element from the left, so if the window is still too large after that, a smaller valid window is never found. Use while (currSum > x && start < n) so the window shrinks as far as it can.
• Subtracting arr[start] after incrementing start - swapping the order silently removes the wrong element from currSum, producing a window sum that no longer matches the actual window. Always subtract arr[start] first, then increment start.
• Assuming the array can contain negative numbers - the sliding window relies on currSum growing every time end moves forward and shrinking every time start moves forward. With negative values present, a larger window can have a smaller sum, so the two-pointer shrink logic silently gives the wrong answer.

Edge Cases to Test

Walk through these inputs before calling the solution done.

• Empty array
• Single-element array
• No subarray with sum greater than x
• Every element individually greater than x
• Sum of the entire array still not greater than x
• x equal to zero or negative
• Array containing duplicate or zero-valued elements

Additional Considerations

The time complexity is O(n). Although there are two nested while loops inside the outer loop, end only ever moves forward across the full scan and start only ever moves forward too, so together they visit at most 2n positions no matter how the expand and shrink phases interleave.

The space complexity is O(1) beyond the input array, since the algorithm only tracks a handful of integers: start, end, currSum, and minLen.

Compared to the brute force O(n^2) approach of summing every subarray, the sliding window is a significant improvement, but it depends entirely on every element being positive. If negative numbers are allowed, currSum is no longer guaranteed to increase as the window grows, so shrinking from the left can skip over the actual smallest window. A prefix-sum approach combined with a sorted structure would be needed instead.

Interview Follow-up Questions

Once you've nailed the base solution, expect an interviewer to push further with questions like these.

• What if the array can contain negative numbers? - the sliding window breaks because currSum is no longer monotonic with window size, so compute prefix sums and binary search over them with a sorted auxiliary structure, giving roughly O(n log n).
• What if you need the actual subarray, not just its length? - keep track of the start and end indices whenever minLen is updated, instead of only storing the length.
• What if the array arrives as a stream and x is known in advance? - the same two-pointer window works incrementally: each new element only triggers one expand step and zero or more shrink steps, so the algorithm is already online with O(1) amortized work per arrival.
• What if you must answer this for many different values of x on the same array? - precompute prefix sums once, then binary search the monotonic prefix sums for each query, turning repeated O(n) scans into O(n + q log n) overall.
• What if the array is too large to fit in memory? - read it as a stream from disk and maintain the same start, end, currSum, and minLen state. Since the window never needs random access to elements outside its bounds, it adapts naturally to a single forward pass over disk-backed data.

Conclusion

Finding the smallest subarray with a sum greater than x is a great showcase for the sliding window technique. By letting end and start each move only forward, you turn an O(n^2) brute force scan into a single O(n) pass. The key insight to remember is that this only works because every element is positive, which guarantees currSum moves predictably as the window expands or shrinks.

Try adapting the code to return the actual subarray instead of just its length, or to handle multiple queries efficiently, as described in the interview follow-up questions above.

You can learn more about Array techniques: Arrays.