Leetcode 209 - Minimum Size Subarray Sum

Understanding the problem

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length of 2.

Plan your solution

One approach to solve this problem is to use a sliding window approach. We can use two pointers, one to represent the start of the window, and the other to represent the end of the window. We will maintain a variable to keep track of the current sum of the subarray and compare it with the given sum s.

We start by initializing the left pointer to 0, and the right pointer to 0. We also initialize the current sum to 0.

We then iterate through the array by incrementing the right pointer. For each iteration, we add the current element to the current sum, and check if the current sum is greater than or equal to s. If it is, we update the minimum length of the subarray. If it is not, we move the left pointer to the right and remove the element from the current sum.

We continue this process until the right pointer reaches the end of the array. We then return the minimum length of the subarray.

Implement your solution

Here is an example of a python code that implements this approach:

def minSubArrayLen(s: int, nums: List[int]) -> int:
    left = 0 # initialize left pointer to 0
    curr_sum = 0 # initialize current sum to 0
    min_len = float("inf") # initialize minimum length of subarray to positive infinity
    for right in range(len(nums)):
        curr_sum += nums[right]  # add current element to current sum
        while curr_sum >= s: # check if current sum is greater than or equal to s
            min_len = min(min_len, right - left + 1) # update minimum length of subarray
            curr_sum -= nums[left] # remove element from current sum
            left += 1 # move left pointer to the right
    return min_len if min_len != float("inf") else 0 # return minimum length of subarray or 0 if not found

In this approach, we are using two pointers, left and right, to represent the current window. We start by initializing the left pointer to 0 and the right pointer to 0. We also initialize the current sum to 0 and the minimum length of the subarray to positive infinity.

We then iterate through the array by incrementing the right pointer. For each iteration, we add the current element to the current sum and check if the current sum is greater than or equal to s. If it is, we update the minimum length of the subarray by taking the minimum of the current minimum length and the difference between the right and left pointer + 1 (length of the current subarray). If the current sum is not greater than or equal to s, we move the left pointer to the right and remove the element from the current sum.

We continue this process until the right pointer reaches the end of the array. We then return the minimum length of the subarray.

Test your solution

Let’s test our solution with the example inputs:

s = 7
nums = [2,3,1,2,4,3]
print(minSubArrayLen(s, nums))

Output: 2

As we can see, the output is correct and matches the expected output.

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 340 - Longest Substring with At Most K Distinct Characters
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• How do you all solve two pointer problems 😭
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together