Minimum Size Subarray Sum
Problem Description
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.
What is a Subarray ?
It's a sequence of elements taken from the original array that are next to each other, without skipping any elements.
For the array [1, 2, 3, 4], here are all possible subarrays:
Single element subarrays:
[1], [2], [3], [4]
Subarrays of length 2:
[1, 2], [2, 3], [3, 4]
Subarrays of length 3:
[1, 2, 3], [2, 3, 4]
Subarray of length 4:
[1, 2, 3, 4] (the entire array)
Note:- { 1, 3 ,4 } or { 2,4 } are not the subarrays of arr[ ] = { 1 , 2 , 3 , 4 }
Example
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: There are no subarrays of size 1 that are greater than or equal to the target. Moving forward with the subarray of size 2, the subarray [4,3] has a minimal length under the problem constraint.
Input: target = 4, nums = [1,4,4]
Output: 1
Explanation: The subarray [4] which is of size 1 has the minimal length under the problem constraint.
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Explanation: Since, the sum of all numbers of nums are less than target ,so we can conclude that there are no subarrays with the problem constraint.
Constraints:
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
The solution for the problem statement involves solving it through brute force method or two pointers/sliding window algorithm. Each of the methods have their own benefits according to the constraints provided. Let's find it one by one !!
Brute Force Approach
Intuition
Since, the problem statement asked us to find the the minimal length of a subarray whose sum is greater than or equal to target.
Why not generate every possible subarrays and then finalize which subarray has the minimum length with a sum is greater than or equal to target ?
How to generate Subarray of an Array ?
Pick a starting point (i): This can be any index from 0 to n-1 (where n is the length of the array).
Pick an ending point (j): This can be any index from the current starting point i to n-1.
Extract the subarray: Once you have both the starting (i) and ending (j) points, you can extract the subarray by slicing from index i to j (inclusive).
For arr = [1, 2, 3]:
Start at i = 0:
Subarray [1] (from i = 0 to j = 0)
Subarray [1, 2] (from i = 0 to j = 1)
Subarray [1, 2, 3] (from i = 0 to j = 2)
Start at i = 1:
Subarray [2] (from i = 1 to j = 1)
Subarray [2, 3] (from i = 1 to j = 2)
Start at i = 2:
Subarray [3] (from i = 2 to j = 2)
While we generate a subarray, we will update the length of the subarray if the sum is greater than or equal to target and if its length is less than the previous value.
Approach
- The outer loop iterates over each possible starting index i.
- For each starting index i, the inner loop iterates over j (the ending index of the subarray), calculating the cumulative sum.
- Once the sum is greater than or equal to the target, we update minLength with the current subarray length and break the inner loop for efficiency.
- If no valid subarray is found, minLength will remain Integer.MAX_VALUE, and we return 0.
Dry-Run
nums[] = { 4 , 2 , 3 , 6 , 1 , 2 , 7 }
target= 9
Answer:- 2
Explantion:- The subarray [2,7] or [3,6] has sum 9 of size 2.
Initial Values
minLength = Integer.MAX_VALUE
Outer Loop - Iterating over each starting index i
i = 0
Start from nums[0] = 4
Inner loop:
j = 0, sum = 4 (sum is less than target, continue)
j = 1, sum = 4 + 2 = 6 (sum is less than target, continue)
j = 2, sum = 6 + 3 = 9 (sum equals target)
Update minLength = min(Integer.MAX_VALUE, 2 - 0 + 1) = 3
Break inner loop for i = 0 since we met the target.
i = 1
Start from nums[1] = 2
Inner loop:
j = 1, sum = 2 (sum is less than target, continue)
j = 2, sum = 2 + 3 = 5 (sum is less than target, continue)
j = 3, sum = 5 + 6 = 11 (sum is greater than target)
Update minLength = min(3, 3 - 1 + 1) = 3 (no change as it's still 3)
Break inner loop for i = 1.
i = 2
Start from nums[2] = 3
Inner loop:
j = 2, sum = 3 (sum is less than target, continue)
j = 3, sum = 3 + 6 = 9 (sum equals target)
Update minLength = min(3, 3 - 2 + 1) = 2
Break inner loop for i = 2 since we met the target with a shorter subarray.
i = 3
Start from nums[3] = 6
Inner loop:
j = 3, sum = 6 (sum is less than target, continue)
j = 4, sum = 6 + 1 = 7 (sum is less than target, continue)
j = 5, sum = 7 + 2 = 9 (sum equals target)
Update minLength = min(2, 5 - 3 + 1) = 2 (no change as it's still 2)
Break inner loop for i = 3.
i = 4
Start from nums[4] = 1
Inner loop:
j = 4, sum = 1 (sum is less than target, continue)
j = 5, sum = 1 + 2 = 3 (sum is less than target, continue)
j = 6, sum = 3 + 7 = 10 (sum is greater than target)
Update minLength = min(2, 6 - 4 + 1) = 2 (no change as it's still 2)
Break inner loop for i = 4.
i = 5
Start from nums[5] = 2
Inner loop:
j = 5, sum = 2 (sum is less than target, continue)
j = 6, sum = 2 + 7 = 9 (sum equals target)
Update minLength = min(2, 6 - 5 + 1) = 2 (no change as it's still 2)
Break inner loop for i = 5.
i = 6
Start from nums[6] = 7
Inner loop:
j = 6, sum = 7 (sum is less than target, no further j values to check for i = 6)
Final Result
minLength = 2
The minimum length of a subarray with a sum of at least 9 is 2, which corresponds to the subarrays [6, 3] or [2, 7].
Brute Force in all Languages
1. C++ Try on Compiler
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int minLength = INT_MAX; // Initialize minimum length to a large value
// Iterate over each possible starting point of subarrays
for (int i = 0; i < nums.size(); i++) {
int sum = 0; // Initialize sum for the current subarray
// Iterate to find the minimal subarray length for starting index i
for (int j = i; j < nums.size(); j++) {
sum += nums[j]; // Add current element to the sum
// Check if the current sum is >= target
if (sum >= target) {
minLength = min(minLength, j - i + 1); // Update minimum length
break; // Break inner loop as we found a valid subarray for this start point
}
}
}
// Return the result, 0 if no valid subarray was found
return minLength == INT_MAX ? 0 : minLength;
}
};2. Java Try on Compiler
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE; // Initialize minimum length to a large value
// Iterate over each possible starting point of subarrays
for (int i = 0; i < nums.length; i++) {
int sum = 0; // Initialize sum for the current subarray
// Iterate to find the minimal subarray length for starting index i
for (int j = i; j < nums.length; j++) {
sum += nums[j]; // Add current element to the sum
// Check if the current sum is >= target
if (sum >= target) {
minLength = Math.min(minLength, j - i + 1); // Update minimum length
break; // Break inner loop as we found a valid subarray for this start point
}
}
}
// Return the result, 0 if no valid subarray was found
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}3. Python Try on Compiler
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf') # Initialize minimum length to a large value
# Iterate over each possible starting point of subarrays
for i in range(len(nums)):
sum = 0 # Initialize sum for the current subarray
# Iterate to find the minimal subarray length for starting index i
for j in range(i, len(nums)):
sum += nums[j] # Add current element to the sum
# Check if the current sum is >= target
if sum >= target:
min_length = min(min_length, j - i + 1) # Update minimum length
break # Break inner loop as we found a valid subarray for this start point
# Return the result, 0 if no valid subarray was found
return 0 if min_length == float('inf') else min_length4. JavaScript Try on Compiler
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(target, nums) {
let minLength = Infinity; // Initialize minimum length to a large value
// Iterate over each possible starting point of subarrays
for (let i = 0; i < nums.length; i++) {
let sum = 0; // Initialize sum for the current subarray
// Iterate to find the minimal subarray length for starting index i
for (let j = i; j < nums.length; j++) {
sum += nums[j]; // Add current element to the sum
// Check if the current sum is >= target
if (sum >= target) {
minLength = Math.min(minLength, j - i + 1); // Update minimum length
break; // Break inner loop as we found a valid subarray for this start point
}
}
}
// Return the result, 0 if no valid subarray was found
return minLength === Infinity ? 0 : minLength;
};Time Complexity: O(n^2)
The minSubArrayLen function iterates over all possible subarrays in a brute-force manner. Here's how the time complexity is determined:
Outer Loop (Index i): This loop runs from 0 to nums.length - 1, so it executes n times (where n is the length of nums).
Inner Loop (Index j): For each starting index i, the inner loop iterates from i to nums.length - 1, resulting in an increasing number of subarrays being checked as i moves from the beginning to the end of nums.
In the worst case, the number of iterations in the inner loop will be n - i for each i, where i goes from 0 to n - 1.
The overall Time Complexity is : O(n^2).
Space Complexity: O(n)
Auxiliary space complexity refers to the extra space used by the algorithm, excluding the input size.
In this code:
- Variables: Only a few constant-space variables are used (minLength, sum).
Thus, auxiliary space complexity: O(1).
Total Space Complexity
Total space complexity includes both the input space and the auxiliary space:
- Input Space: The input array nums takes up O(n) space.
- Auxiliary Space: As analysed, the auxiliary space complexity is O(1)
Therefore, the total space complexity is the sum of input space and auxiliary space: O(n)+O(1)=O(n)
This is extremely slow and not feasible within typical time limits (usually 1-2 seconds). Most programming environments allow around 10^8 operations per second, so 10^15 operations would take about 10 million seconds (over 115 days!), which is far too long.
The interviewer won’t be happy with your solution.
We have to optimize the Time Complexity to move further in the interview!
Optimized Approach
Intuition
The key observation is that we don’t need to recalculate the sum from scratch every time we add a new number. If we’ve already checked a sequence of numbers, we can reuse that information and just adjust it slightly as we go along.
In the brute-force method, we are recalculating sums for overlapping parts of the array. For example, if we are traversing an array [2,3,1,2,4] , when you move from subarray [2, 3, 1, 2] to [3, 1, 2, 4], you’re recalculating the sum from scratch, even though three of the elements (3, 1, and 2) are the same.
The repeated calculations become a big problem when the array gets longer because you’re recalculating a lot of values that haven’t changed.
This observation suggests that if we could somehow reuse the sum from previous calculations rather than starting from scratch each time, we could speed things up.
Confused on what was re-calculated ?
target = 7 and nums = [2, 3, 1, 2, 4, 3], you would start by looking at each subarray like this:
Check [2], sum = 2 (not enough)
Check [2, 3], sum = 5 (2 was re-calculated)
Check [2, 3, 1], sum = 6 (2,3 were re-calculated)
Check [2, 3, 1, 2], sum = 8 (2, 3, 1 were re-calculated)
And so on, until you’d exhaust all possible subarrays. This would eventually give you the answer, but it would involve a lot of repeated and unnecessary calculations.
Can we visualize a frame in which it contains a series of numbers?
This frame is dynamic which means it can shrink and expand accordingly.
We can use this frame to optimize the solution.
Let’s imagine a way to keep track of a "frame" of numbers instead of recalculating each time.
- The frame will have two ends, the left end and the right end. When the window expands, the right end moves right. When the window shrinks, the left end moves right.
- Expand the frame until the sum of the numbers in the frame reaches or exceeds the target.
- Once you hit the target, shrink the frame from the left to see if you can get a smaller valid frame.
- Continue adjusting the frame by moving its left and right as needed, and keep track of the smallest frame that meets the target.
Let's call this frame a "window" that shrinks and expands and since the window shrinks and expands or slides over the array we just call it as the sliding window.
Points to Remember
Whenever we are expanding the window, we will add the right of the rightmost element to the sum.
Whenever we are shrinking the window, we will subtract the leftmost element from the sum.
Confused on the Algorithm ?
target = 7 and nums = [2, 3, 1, 2, 4, 3].
Start with an empty window: Begin with both the left and right pointers at the start of the array. Keep a curr variable to store the sum of the current window.
Expand the window by moving right to the right, adding each element nums[right] to curr.
Right = 0: Add nums[0] = 2 to curr, so curr = 2.
Right = 1: Add nums[1] = 3 to curr, so curr = 5.
Right = 2: Add nums[2] = 1 to curr, so curr = 6.
Right = 3: Add nums[3] = 2 to curr, so curr = 8. (Now curr ≥ target)
Shrink the window:
We reached our target, so we check the length: it’s right - left + 1 = 4.
Now try to shrink the window from the left to see if we can get a smaller subarray that still meets the target.
Remove nums[0] = 2 from curr, making curr = 6. Move left to 1.
Since curr is now less than the target, we stop shrinking and go back to expanding by moving right.
Continue expanding and shrinking:
Move right to 4: Add nums[4] = 4, making curr = 10.
Check window length (it’s 4, so no improvement).
Shrink again by moving left: remove nums[1] = 3 to get curr = 7 with length 3. Update minLen to 3.
End: Repeat this until right reaches the end of the array. The smallest valid subarray length found during this process is the answer.
Approach
Initialize Variables:Set a variable to store the minimum length of the subarray that meets the condition. Initially, set this to a large value, representing that we haven’t found a valid subarray yet.Set a pointer to mark the beginning of the window.Set a variable to keep track of the current sum of the elements within the window.
Expand the Window:Iterate over the elements in the array with a pointer representing the end of the window.For each element, add its value to the current sum. This expands the window to include the new element.
Check and Shrink the Window:While the current sum meets or exceeds the required condition, check the length of the current window. If it’s smaller than the minimum length recorded, update the minimum length.Then, shrink the window from the left by subtracting the value of the element at the start of the window from the current sum and moving the start pointer to the right. This reduces the window size while still meeting the required condition (if possible).
Return the Result:After iterating through the array, if a valid subarray was found, return its length. If not, return 0, as no subarray met the condition.
Dry-Run
nums[] = { 4 , 2 , 3 , 6 , 1 , 2 , 7 }
target= 9
Answer:- 2
Explantion:- The subarray [2,7] or [3,6] has sum 9 of size 2.
Initialize Variables
minLen = Infinity (We want the smallest subarray length that meets the condition)
left = 0 (Starting index of the window)
sum= 0 (Current sum of the elements within the window)
Expand the Window
We’ll use a for loop with right as the end of the window.
Iteration 1: right = 0
Add nums[0] = 4 to sum: sum= 4.
sum < target, so we continue expanding.
Iteration 2: right = 1
Add nums[1] = 2 to sum: sum = 6.
sum< target, so we continue expanding.
Iteration 3: right = 2
Add nums[2] = 3 to sum: sum = 9.
Now sum >= target, so we check the window size:
Current window size = right - left + 1 = 2 - 0 + 1 = 3.
Update minLen to 3.
To try finding a smaller valid window, we shrink from the left:
Subtract nums[left] = 4 from sum: sum = 5.
Move left to 1.
Iteration 4: right = 3
Add nums[3] = 6 to sum: sum = 11.
sum >= target, so we check the window size:
Current window size = right - left + 1 = 3.
minLen remains 3.
Shrink from the left:
Subtract nums[left] = 2 from curr: curr = 9.
Move left to 2.
Check again since sum >= target:
Window size = right - left + 1 = 2.
Update minLen to 2.
Shrink from the left:
Subtract nums[left] = 3 from sum: sum = 6.
Move left to 3.
Iteration 5: right = 4
Add nums[4] = 1 to sum: sum = 7.
sum< target, so continue expanding.
Iteration 6: right = 5
Add nums[5] = 2 to sum: sum= 9.
sum >= target, so we check the window size:
Window size = right - left + 1 = 3.
minLen remains 2.
Shrink from the left:
Subtract nums[left] = 6 from sum: sum = 3.
Move left to 4.
Iteration 7: right = 6
Add nums[6] = 7 to sum: sum= 10.
sum>= target, so we check the window size:
Window size = right - left + 1 = 3.
minLen remains 2.
Shrink from the left:
Subtract nums[left] = 1 from sum: sum= 9.
Move left to 5.
Check again since sum>= target:
Window size = right - left + 1 = 2.
minLen remains 2.
Shrink from the left:
Subtract nums[left] = 2 from sum: sum = 7.
Move left to 6.
Result
After finishing all iterations, the smallest subarray length minLen that meets the condition is 2. The subarrays [3, 6] and [2, 7] both have a sum of 9, achieving the target.
Final Output: minLen = 2
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int minLength = INT_MAX;
// Left pointer to track the start of the window
int left = 0;
// Variable to hold the current sum within the window
int currentSum = 0;
// Loop through each element with the right pointer
for (int right = 0; right < nums.size(); right++) {
// Add the current element to the current sum
currentSum += nums[right];
// While current sum meets or exceeds the target
while (currentSum >= target) {
// Update minimum length to the smaller of current or previous minimum length
minLength = min(minLength, right - left + 1);
// Shrink the window from the left
currentSum -= nums[left];
left++;
}
}
// If no valid subarray was found, return 0
return minLength == INT_MAX ? 0 : minLength;
}
};2. Java Try on Compiler
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// Initialize minimum length to a large value
int minLength = Integer.MAX_VALUE;
// Left pointer to track the start of the window
int left = 0;
// Variable to hold the current sum within the window
int currentSum = 0;
// Right pointer to expand the window
for (int right = 0; right < nums.length; right++) {
// Add the current element to the current sum
currentSum += nums[right];
// While the current sum meets or exceeds the target
while (currentSum >= target) {
// Update minimum length if current window is smaller
minLength = Math.min(minLength, right - left + 1);
// Shrink the window from the left
currentSum -= nums[left];
left++;
}
}
// If no valid subarray was found, return 0
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}3. Python Try on Compiler
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# Initialize minimum length to a large value
min_length = float('inf')
# Left pointer to track the start of the window
left = 0
# Variable to hold the current sum within the window
current_sum = 0
# Loop through each element with the right pointer
for right in range(len(nums)):
# Add the current element to the current sum
current_sum += nums[right]
# While the current sum meets or exceeds the target
while current_sum >= target:
# Update minimum length to the smaller of current or previous minimum length
min_length = min(min_length, right - left + 1)
# Shrink the window from the left
current_sum -= nums[left]
left += 1
# If no valid subarray was found, return 0
return 0 if min_length == float('inf') else min_length4. JavaScript Try on Compiler
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(target, nums) {
let minLength = Infinity;
// Left pointer to track the start of the window
let left = 0;
// Variable to hold the current sum within the window
let currentSum = 0;
// Loop through each element with the right pointer
for (let right = 0; right < nums.length; right++) {
// Add the current element to the current sum
currentSum += nums[right];
// While the current sum meets or exceeds the target
while (currentSum >= target) {
// Update minimum length to the smaller of current or previous minimum length
minLength = Math.min(minLength, right - left + 1);
// Shrink the window from the left
currentSum -= nums[left];
left++;
}
}
// If no valid subarray was found, return 0
return minLength === Infinity ? 0 : minLength;
};Time Complexity: O(n)
Since, both the left pointer will traverse the array once in the worst case. So, it's time complexity becomes O(n).
The right pointer will traverse till the end of the array which will result in O(n) time.
Total Time Complexity: Combining the above time complexities, the overall time complexity becomes O(n) + O(n) = O(2n) = O(n).
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space complexity refers to the extra space or temporary space used by an algorithm, excluding the input data. In this solution:
- The auxiliary space is O(1) because it only uses a fixed number of variables (minLength, left, currentSum, etc.) regardless of the size of the input array nums.
- This means that as the input size grows, the space used by these variables remains constant and does not depend on n.
Total Space Complexity
Total space complexity includes both the space used for the input data and the auxiliary space.
- In this problem, the input array nums itself occupies O(n) space since it contains n elements.
- When we combine this with the O(1) auxiliary space, the total space complexity remains O(n) , as the input array's size dominates.
Given two strings s and t of lengths m and n respectively, return the minimum window
substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.