Facebook Pixel

Minimum Size Subarray Sum

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

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Solution

We want to use a sliding window to find the minimum subarray (window). Because the size of the window is unknown, we must use a flexible sliding window that searchs through all the valid windows that meet the requirement. We will apply the flexible sliding window template on this question. Our search starts on interval (0,0) and extends rightwards before the total reaches target. When the total succeeds the target we have found a valid subarray. Then, we start shrinking this subarray from the left finding a smaller subarray until the window is no longer valid. Afterwards, we continue this process until we iterate through the entire array to find the minimum size subarray that has sum >= target.

Implementation

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    size = len(nums)+1
    total, l = 0, 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= target:       # valid
            size = min(size, r-l+1)
            total -= nums[l]
            l += 1      
    return size if size != len(nums)+1 else 0

The above solution using a flexible sliding window uses O(n) time complexity. As a follow up, is there an algorithm that solves this question in O(n log(n))? Yes! Consider using the n elements in nums as a starting point of a subarray, and then use O(log(n)) time complexity to find the endpoint of that subarray. This is can be done via a for loop and a binary search on a prefix sum array.

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    prefix_sum = [0]
    for n in nums:
        prefix_sum.append(prefix_sum[-1] + n)
    
    size = len(nums)+1
    for start in range(len(nums)):
        total = 0
        l, r, end = 0, len(nums)-1, -1
        while l <= r:
            mid = (l+r)//2
            if prefix_sum[mid+1] - prefix_sum[start] >= target:
                end, r = mid, mid - 1
            else: l = mid + 1
        if end != -1: size = min(size, end-start+1) 
    return size if size != len(nums)+1 else 0

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More