Mastering Minimum Subarray Sum with Sliding Window Technique

The Minimum Subarray Sum problem (also known as "Minimum Size Subarray Sum") is an excellent introduction to the sliding window technique. This problem demonstrates how we can optimize from a brute force O(n³) solution to an elegant O(n) solution.

Problem Statement

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

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

Solution Evolution

Let's explore how we can evolve from a brute force approach to an optimal solution:

Brute Force O(n³)

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;

        // Try all possible subarrays
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int sum = 0;
                // Calculate sum of subarray [i, j]
                for (int k = i; k <= j; k++) {
                    sum += nums[k];
                }

                if (sum >= target) {
                    minLength = Math.min(minLength, j - i + 1);
                    break; // No need to extend this subarray further
                }
            }
        }

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

Time Complexity: O(n³) Space Complexity: O(1)

Optimized Brute Force O(n²)

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j]; // Add current element to running sum

                if (sum >= target) {
                    minLength = Math.min(minLength, j - i + 1);
                    break; // Found minimum for this starting position
                }
            }
        }

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

Time Complexity: O(n²) Space Complexity: O(1)

Sliding Window O(n)

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

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

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

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

Time Complexity: O(n) Space Complexity: O(1)

Sliding Window Pattern Deep Dive

Key Insight

The sliding window technique works here because:

1. Monotonic Property: If a subarray sum ≥ target, removing elements from the left maintains this property
2. Greedy Choice: We can safely shrink from left to find the minimum length
3. Two Pointers: Left and right pointers move in the same direction, each element is visited at most twice

Algorithm Walkthrough

Let's trace through the optimal solution with target = 7 and nums = [2,3,1,2,4,3]:

// Visual representation of the sliding window
Initial: left=0, right=0, sum=0, minLength=∞
Step 1:  [2] 3  1  2  4  3    sum=2, minLength=∞
Step 2:  [2  3] 1  2  4  3    sum=5, minLength=∞
Step 3:  [2  3  1] 2  4  3    sum=6, minLength=∞
Step 4:  [2  3  1  2] 4  3    sum=8 ≥ 7, minLength=4
         Contract:
          2 [3  1  2] 4  3    sum=6, left++
Step 5:  [3  1  2  4] 3      sum=10 ≥ 7, minLength=4
         Contract:
          3 [1  2  4] 3       sum=7 ≥ 7, minLength=3
          3  1 [2  4] 3       sum=6, left++
Step 6:  [2  4  3]           sum=9 ≥ 7, minLength=3
         Contract:
          2 [4  3]            sum=7 ≥ 7, minLength=2 ✓

Alternative Approaches

Binary Search + Prefix Sum

For advanced scenarios, you might consider a binary search approach:

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];

        // Build prefix sum array
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int minLength = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            int toFind = target + prefixSum[i - 1];
            int bound = Arrays.binarySearch(prefixSum, toFind);

            if (bound < 0) {
                bound = -bound - 1;
            }

            if (bound <= n) {
                minLength = Math.min(minLength, bound - (i - 1));
            }
        }

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

Time Complexity: O(n log n) Space Complexity: O(n)

When to Use Each Approach

Approach	When to Use	Pros	Cons
Sliding Window	Arrays with positive numbers	O(n) time, intuitive	Only works with positive arrays
Binary Search	Mixed positive/negative numbers	More general	O(n log n) time, extra space
Brute Force	Small arrays or learning	Simple to understand	Poor time complexity

Common Pitfalls

1. Infinite Loop: Forgetting to move the left pointer in the while loop
2. Edge Cases: Not handling empty arrays or impossible targets
3. Off-by-One: Incorrect window size calculation (right - left + 1)

Related Problems

• Sliding Window Maximum: Similar technique, different objective
• Longest Substring Without Repeating Characters: Variable window size
• Maximum Sum Subarray: Kadane's algorithm variation

Conclusion

The Minimum Subarray Sum problem beautifully demonstrates the power of the sliding window technique. By maintaining two pointers and leveraging the monotonic property of cumulative sums, we achieve an optimal O(n) solution that's both elegant and efficient.

The key insight is recognizing when a problem has the properties that make sliding window applicable: a sequential data structure and some form of monotonic relationship that allows us to safely shrink the window.

Practice Tip

Master this pattern by practicing on similar problems and always ask yourself: "Can I use two pointers to avoid nested loops?"