algoadvance

Leetcode 209. Minimum Size Subarray Sum

Problem Statement

You are given an array of positive integers nums and a positive integer target. Return the minimal length of a contiguous subarray [nums[l], nums[l+1], ..., nums[r-1], nums[r]] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example

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

Clarifying Questions

• Q: Are all elements in the array positive integers?
  • A: Yes, all elements in nums are positive integers.
• Q: Can nums contain zero elements?
  • A: Yes, nums can be empty, in which case the answer should be 0.
• Q: Is there a guaranteed solution to the problem with the given constraints?
  • A: No, it’s possible that no subarray meets the target sum, in which case you should return 0.

Strategy

1. Sliding Window Technique:
   • Use two pointers (left and right) to represent the current window.
   • Expand the window by moving the right pointer to include more elements and calculate the running sum.
   • Once the sum is equal to or greater than target, record the length of the subarray.
   • Move the left pointer to see if we can find a smaller subarray that still meets the sum requirement.
   • Track the minimum length encountered.

Algorithm

1. Initialize minLength to a large value to store the minimum subarray length found.
2. Use left pointer starting at 0, and iterate with right pointer through the array.
3. Add nums[right] to the running sum.
4. While the running sum is greater than or equal to target:
   • Update minLength with the smaller value between minLength and the current window size (right - left + 1).
   • Subtract nums[left] from the running sum and increment left pointer.
5. If minLength is unchanged (meaning no valid subarray was found), return 0.
6. Return minLength.

Code Implementation

#include <vector>
#include <algorithm>
#include <climits>

int minSubArrayLen(int target, std::vector<int>& nums) {
    int n = nums.size();
    int minLength = INT_MAX;
    int left = 0, sum = 0;

    for (int right = 0; right < n; ++right) {
        sum += nums[right];
        while (sum >= target) {
            minLength = std::min(minLength, right - left + 1);
            sum -= nums[left++];
        }
    }

    return (minLength == INT_MAX) ? 0 : minLength;
}

Time Complexity

• The time complexity of this solution is O(n), where n is the number of elements in the input array nums.
• Both left and right pointers traverse the array at most once, resulting in a linear pass through the array.

Space Complexity

• The space complexity of this solution is O(1), as it uses only a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?