Minimum Size Subarray Sum - Java Solution

1. Introduction

This blog post addresses the "Minimum Size Subarray Sum" problem, a common challenge in the realm of array processing and sliding window algorithms. The problem focuses on finding the smallest contiguous subarray whose sum is at least as large as a given target number.

Problem

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

2. Solution Steps

1. Initialize two pointers to implement the sliding window technique.

2. Incrementally expand the window until its sum meets or exceeds the target.

3. Once the target is met, contract the window from the left to minimize its size.

4. Record the size of the smallest window that meets the target sum.

5. Repeat steps 2-4 for the entire array.

6. Return the size of the smallest such subarray found.

3. Code Program

public class MinimumSizeSubarraySum {
    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3})); // Example 1
        System.out.println(minSubArrayLen(4, new int[]{1, 4, 4}));         // Example 2
        System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1})); // Example 3
    }

    // Function to find the minimum size of a subarray with sum at least 'target'
    public static int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int left = 0;
        int sum = 0;

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

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1); // Update minimum length
                sum -= nums[left]; // Contract the window from the left
                left++;
            }
        }

        return minLength != Integer.MAX_VALUE ? minLength : 0; // Check for no valid subarray
    }
}

Output:

2
1
0

Explanation:

1. minSubArrayLen: This function uses a sliding window approach. It initializes a sum variable and two pointers, left and right.

2. The right pointer expands the window by adding elements to sum until it meets or exceeds the target.

3. Once the sum is equal to or greater than the target, the window is contracted from the left to find the minimum size.

4. minLength is updated every time a smaller valid window is found.

5. The function continues this process until the end of the array is reached.

6. If a valid subarray is found, the function returns its minimum length; otherwise, it returns 0.