Minimum Size Subarray Sum - Java Solution

1. Introduction

This blog post addresses a common problem in array processing using the sliding window technique: finding the length of the smallest contiguous subarray whose sum is greater than or equal to a given number K.

Problem

Given an array of positive integers a and a positive number K, find the length of the smallest contiguous subarray whose sum is greater than or equal to K. Return 0 if no such subarray exists.

2. Solution Steps

1. Use a sliding window approach to find the smallest subarray with the required sum.

2. Maintain a running sum of the elements in the current window.

3. Expand the window until the sum is greater than or equal to K.

4. Once the sum is sufficient, contract the window from the left and update the minimum length.

5. Return the minimum length found; if no such length is found, return 0.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a1 = {2, 1, 4, 3, 2, 5};
        System.out.println("Smallest subarray length: " + findMinSubArray(a1, 7));

        int[] a2 = {3, 4, 1, 1, 6};
        System.out.println("Smallest subarray length: " + findMinSubArray(a2, 8));

        int[] a3 = {1, 3, 2, 1, 5};
        System.out.println("Smallest subarray length: " + findMinSubArray(a3, 15));
    }

    // Method to find the smallest subarray with a sum greater than or equal to K
    public static int findMinSubArray(int[] a, int K) {
        int windowSum = 0, minLength = Integer.MAX_VALUE;
        int windowStart = 0;

        for (int windowEnd = 0; windowEnd < a.length; windowEnd++) {
            windowSum += a[windowEnd]; // Add the next element

            // Shrink the window as small as possible until the window's sum is smaller than K
            while (windowSum >= K) {
                minLength = Math.min(minLength, windowEnd - windowStart + 1);
                windowSum -= a[windowStart]; // Subtract the element going out
                windowStart++; // Slide the window ahead
            }
        }

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

Output:

Smallest subarray length: 2
Smallest subarray length: 3
Smallest subarray length: 0

Explanation:

The findMinSubArray method applies the sliding window technique to find the smallest subarray whose sum is greater than or equal to K. 

For the input array [2, 1, 4, 3, 2, 5] and K = 7, it calculates the smallest subarray length as 2 ([4, 3]). 

For the second input [3, 4, 1, 1, 6] and K = 8, the smallest subarrays are [3, 4, 1] or [1, 1, 6], both of length 3. In the third example, there is no subarray with a sum greater than or equal to 15, hence the output is 0.