209. Minimum Size Subarray Sum
Minimum Size Subarray Sum (LeetCode 209) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Minimum Size Subarray Sum
Minimum Size Subarray Sum is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Think about using a sliding window approach to efficiently find subarrays meeting the sum condition.
- Try maintaining two pointers representing the current window's start and end, and adjust them to explore different subarray sizes.
- As you move the end pointer forward, accumulate the sum of the window; if the sum reaches or exceeds the target, try shrinking the window from the start to find the minimal length.
The reference solution runs in O(n) time and O(1) space.
The Minimum Size Subarray Sum solution and editorial walks through the full approach with reference code.
Problem statement
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)).
Topics and companies
Topics: Array, Binary Search, Sliding Window, Prefix Sum.
Reported in interviews at Goldman Sachs, Amazon, Bloomberg, Facebook, Microsoft, ByteDance.
How to practise Minimum Size Subarray Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Minimum Size Subarray Sum in the code editor, or read the Minimum Size Subarray Sum editorial for a worked solution with its approach and complexity analysis.
Where Minimum Size Subarray Sum sits in the DSA pattern sheet
Problems related to Minimum Size Subarray Sum
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Minimum Size Subarray Sum FAQ
What is the LeetCode number of Minimum Size Subarray Sum?
Minimum Size Subarray Sum is LeetCode problem 209, rated Medium.
What pattern is used to solve Minimum Size Subarray Sum?
Minimum Size Subarray Sum is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Minimum Size Subarray Sum?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Minimum Size Subarray Sum?
Minimum Size Subarray Sum has been reported in interviews at Goldman Sachs, Amazon, Bloomberg, Facebook, Microsoft, ByteDance.