DDSA Solutions

Smallest Subarray Sum Greater Than x

Problem Overview

All array values are non negative, so a contiguous window sum only grows when the right end moves forward and only shrinks when the left end moves forward.

Intuition

All array values are non negative, so a contiguous window sum only grows when the right end moves forward and only shrinks when the left end moves forward. That monotonicity lets one sliding window find every minimal length that beats x. Expand right to include the next value, then shrink left while the sum stays strictly greater than x, remembering the shortest window seen. If no window ever qualifies, the answer is 0.

Algorithm

  1. 1Initialize left at 0, running sum at 0, and minLen at a large sentinel.
  2. 2For each right index, add arr[right] into the running sum.
  3. 3While the sum is greater than x, update minLen with the current window length and remove arr[left] while advancing left.
  4. 4Return 0 when minLen never changed, otherwise return minLen.

Example Walkthrough

Input: arr = [1, 4, 45, 6, 0, 19], x = 51

  1. 1. The prefix 1, 4, 45 sums to 50 and is still not greater than 51.
  2. 2. Adding 6 makes the sum 56, so a valid window appears.
  3. 3. After shrinking from the left, the shortest window whose sum exceeds 51 is 4, 45, 6 with length 3.

Output: 3

Common Pitfalls

  • • The condition is strictly greater than x. Equality is not enough to stop shrinking.
  • • This two pointer method needs non negative values. Negatives can make the sum non monotonic.
  • • Return 0 when every prefix stays at most x. Do not return the sentinel length.
  • • Update the answer before removing the left element so the current valid window is recorded.
Smallest Subarray Sum Greater Than x.java
Java
// Approach: With positive elements the window sum grows when the right end
// advances and shrinks when the left end advances. Grow right, then shrink
// left while the sum stays strictly greater than x, tracking the shortest
// valid window. One pass is enough.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    public int smallestSubWithSum(int[] arr, int x) {
        int n = arr.length;
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            sum += arr[right];

            while (sum > x) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= arr[left++];
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
Was this solution helpful?