LeetCode 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

package jan24;

public class MinSizeSubArraySum {
    public static void main(String[] args) {
        // TC: O(1), SC: O(1)
        int[] arr = {1, 4, 2, 2, 1, 4};
        int target = 5;

        // TC: O(n), SC: O(1)
        System.out.println(solution(arr, target));
    }

    private static int solution(int[] arr, int target) {
        // TC: O(1), SC: O(1) – initialization
        int min_len = Integer.MAX_VALUE;
        int sum = 0;

        // Sliding window traversal
        // Outer loop runs O(n) times
        for (int sp = 0, ep = 0; ep < arr.length; ep++) {
            // TC: O(1) per step – accumulate sum
            sum += arr[ep];

            // Inner loop also runs O(n) in total across the array
            while (sum >= target) {
                // TC: O(1) – update minimum length
                min_len = Math.min(ep - sp + 1, min_len);
                sum = sum - arr[sp++]; // TC: O(1) – contract window from start
            }
        }

        // TC: O(1), SC: O(1)
        return min_len == Integer.MAX_VALUE ? 0 : min_len;
    }
}

✅ Time Complexity (TC): O(n)
The for loop runs n times (where n = arr.length).
The while loop also runs at most n times across all iterations (since each index is visited once when expanding and once when contracting).
So, total operations: O(2n) → simplified to O(n).



✅ Space Complexity (SC): O(1)
No extra space used except a few variables (min_len, sum, sp, ep).
Constant space regardless of input size.