medium Minimum Size Subarray Sum

Problem Statement

Given a nums array containing positive integers and a positive integer target, return the minimum length of a subarray having the sum of elements greater than or equal to target. If there is no such subarray, return 0 instead.

Examples

Example 1:

• Input: target = 15, nums = [1, 2, 3, 4, 5, 6, 7, 8]
• Expected Output: 2
• Justification: The subarray [7, 8] has a sum of 15, which is equal to target and is the smallest possible subarray.

Example 2:

• Input: target = 11, nums = [2, 1, 5, 2, 8]
• Expected Output: 3
• Justification: The subarray [5, 2, 8] has a sum of 15, which meets the target and is the smallest possible subarray.

Example 3:

• Input: target = 8, nums = [2, 1, 5, 2, 3]
• Expected Output: 3
• Justification: The subarray [5, 2, 3] has a sum of 10, which meets the target and is the smallest possible subarray.

Constraints:

• 1 <= target <= 10⁹
• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁴

Solution

To solve this problem, we use a sliding window approach. This method involves maintaining a window that expands and contracts while checking the sum of its elements. By adjusting the window's size dynamically, we can efficiently find the minimum length subarray that meets or exceeds the target sum. This approach works because it avoids re-evaluating sums from scratch, reducing unnecessary calculations.

This method is effective because it allows us to traverse the array in linear time. We expand the window by moving the right end until the sum is sufficient, then contract by moving the left end to find the smallest subarray. This two-pointer technique ensures we cover all possibilities without redundant checks, optimizing performance.

Step-by-Step Algorithm

1. Initialize Variables:

   • Set start to 0 to denote the start of the sliding window.
   • Set min_length to a large number (e.g., infinity) to keep track of the minimum subarray length found.
   • Set current_sum to 0 to keep track of the sum of the current window.

2. Iterate Through Array:

   • Use a for loop with end ranging from 0 to n-1 (where n is the length of nums).

3. Expand the Window:

   • For each end index, add nums[end] to current_sum.

4. Contract the Window:

   • Use a while loop to check if current_sum is greater than or equal to target.
   • If it is, update min_length to the smaller of min_length and the length of the current window (end - start + 1).
   • Subtract nums[start] from current_sum to reduce the window size.
   • Move the start pointer to the right by incrementing start.

5. Finalize Result:

   • After the loop, check if min_length is still a large number.
   • If it is, return 0 (meaning no valid subarray was found).
   • Otherwise, return min_length.

Algorithm Walkthrough

Using Example 1:

Input: target = 15, nums = [1, 2, 3, 4, 5, 6, 7, 8]

1. Initialize Variables:

   • start = 0
   • min_length = infinity
   • current_sum = 0

2. Iterate Through Array:

   • end = 0: Add nums[0] to current_sum → current_sum = 1

     • current_sum (1) is less than target (15), so do nothing.

   • end = 1: Add nums[1] to current_sum → current_sum = 3

     • current_sum (3) is less than target (15), so do nothing.

   • end = 2: Add nums[2] to current_sum → current_sum = 6

     • current_sum (6) is less than target (15), so do nothing.

   • end = 3: Add nums[3] to current_sum → current_sum = 10

     • current_sum (10) is less than target (15), so do nothing.

   • end = 4: Add nums[4] to current_sum → current_sum = 15

     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(infinity, 4 - 0 + 1) = 5
       • Subtract nums[start] (1) from current_sum → current_sum = 14
       • Increment start → start = 1

   • end = 5: Add nums[5] to current_sum → current_sum = 20

     • current_sum (20) is greater than target (15), so:
       • Update min_length → min_length = min(5, 5 - 1 + 1) = 5
       • Subtract nums[start] (2) from current_sum → current_sum = 18
       • Increment start → start = 2
     • current_sum (18) is still greater than target (15), so:
       • Update min_length → min_length = min(5, 5 - 2 + 1) = 4
       • Subtract nums[start] (3) from current_sum → current_sum = 15
       • Increment start → start = 3
     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(4, 5 - 3 + 1) = 3
       • Subtract nums[start] (4) from current_sum → current_sum = 11
       • Increment start → start = 4

   • end = 6: Add nums[6] to current_sum → current_sum = 18

     • current_sum (18) is greater than target (15), so:
       • Update min_length → min_length = min(3, 6 - 4 + 1) = 3
       • Subtract nums[start] (5) from current_sum → current_sum = 13
       • Increment start → start = 5

   • end = 7: Add nums[7] to current_sum → current_sum = 21

     • current_sum (21) is greater than target (15), so:
       • Update min_length → min_length = min(3, 7 - 5 + 1) = 3
       • Subtract nums[start] (6) from current_sum → current_sum = 15
       • Increment start → start = 6
     • current_sum (15) is equal to target (15), so:
       • Update min_length → min_length = min(3, 7 - 6 + 1) = 2
       • Subtract nums[start] (7) from current_sum → current_sum = 8
       • Increment start → start = 7

3. Finalize Result:

   • min_length is 2, which is not infinity.
   • Return min_length, which is 2.

This is the smallest subarray whose sum is at least 15, and it is [7, 8].

Code

class Solution {

  public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int minLength = Integer.MAX_VALUE; // Initialize minLength to a large number
    int currentSum = 0; // To keep track of the current sum
    int start = 0; // Starting index of the sliding window

    for (int end = 0; end < n; end++) {
      currentSum += nums[end]; // Add the current element to currentSum
      while (currentSum >= target) { // While the current sum is greater than or equal to target
        minLength = Math.min(minLength, end - start + 1); // Update minLength
        currentSum -= nums[start]; // Remove the starting element from currentSum
        start++; // Move the starting index to the right
      }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength; // Return 0 if no subarray was found
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] nums1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int[] nums2 = { 2, 1, 5, 2, 8 };
    int[] nums3 = { 2, 1, 5, 2, 3 };
    System.out.println(sol.minSubArrayLen(15, nums1)); // Output: 2
    System.out.println(sol.minSubArrayLen(11, nums2)); // Output: 3
    System.out.println(sol.minSubArrayLen(8, nums3)); // Output: 3
  }
}

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is , where n is the length of the array. This is because each element is processed at most twice, once by the end pointer and once by the start pointer.
• Space Complexity: The space complexity of this algorithm is because we are using a constant amount of extra space regardless of the input size.