Problem 18 - Minimum Size Subarray Sum

Explore our archive for previous posts.

Question

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 instead.

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

Constraints:

• 1 <= target <= 109

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 104

Approach

The given solution uses a sliding window approach to solve the problem. It maintains two pointers, left and right, to define the window and calculates the sum of elements within the window (windowSum). The algorithm iterates through the array, incrementing the right pointer, and adjusts the left pointer as necessary. When the windowSum becomes greater than or equal to the target, it updates the minimum length (minLength) by comparing it with the current window size.

Solution

Solve it here

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int windowSum = 0;
        int left = 0;
        
        // Iterate through the array with the right pointer
        for (int right = 0; right < n; right++) {
            windowSum += nums[right]; // Add the current element to the window sum
            
            // Shrink the window by moving the left pointer as long as the sum is greater than or equal to the target
            while (windowSum >= target) {
                minLength = Math.min(minLength, right - left + 1); // Update the minimum length
                
                windowSum -= nums[left]; // Subtract the element at the left pointer from the window sum
                left++; // Move the left pointer forward
            }
        }
        
        return (minLength != Integer.MAX_VALUE) ? minLength : 0; // Return the minimum length, or 0 if no subarray is found
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(n), where n is the length of the input array nums. The algorithm performs a single pass through the array using the two pointers, left and right. In each iteration, the right pointer moves forward, and the left pointer also moves forward (if necessary) to shrink the window. Since both pointers traverse the array once, the time complexity is linear in terms of the input size.

Space Complexity: The space complexity of the solution is O(1) because it uses a constant amount of extra space. The additional space used by the algorithm is independent of the input size. It only requires a few extra variables (minLength, windowSum, left, right) to track the window and the minimum length, and the space occupied by these variables does not grow with the size of the input array.