Crack the Backend

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

All elements in nums are positive, so a longer window has a larger sum and a shorter window has a smaller sum.
A subarray is contiguous (consecutive indices); you cannot skip elements.
If the entire array sum is still less than target, return 0.

Key Observations

Because all numbers are positive, expanding the window (moving right) always increases the sum, and shrinking the window (moving left) always decreases it. So for each right, we can shrink left until the sum is just below target; the window [left, right] at that point is the smallest window ending at right that satisfies sum >= target (we had a valid window before shrinking).
For each right, after we have a valid window, we update the minimum length; then we shrink from left to get the smallest valid window ending at right, and move to right+1.
This is a classic variable-size sliding window on a positive array.

Approach

High-level: Maintain a window [left, right] and its sum. Expand with right; when the sum is >= target, update the minimum length and then shrink left until the sum is less than target (so the next expansion can be considered).

Steps:

Initialize left = 0, sum = 0, minLen = infinity.
For each right: add nums[right] to sum. While sum >= target, update minLen = min(minLen, right - left + 1), subtract nums[left] from sum, and left++.
Return minLen (or 0 if it was never updated).

Implementation

Java

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, minLen = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];

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

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Test Cases

Example 1

Input

target = 7, nums = [2,3,1,2,4,3]

Expected

2

Explanation

The subarray [4,3] has sum 7 and length 2; no shorter subarray has sum >= 7.

Complexity Analysis

Time: O(n). Each element is added and removed from the window at most once.
Space: O(1).

Follow-ups

At most k negatives: If the array can contain negative numbers, the window sum is no longer monotonic when we shrink; consider prefix sums + data structure (e.g. monotonic deque or binary search on prefix sums).