0% completed
Problem Statement
Given a nums
array containing positive integers and a positive integer target
, return the minimum length of a
subarray
having the sum of elements greater
than or equal
to target
. If there is no such subarray, return 0 instead.
Examples
Example 1:
- Input:
target = 15
,nums = [1, 2, 3, 4, 5, 6, 7, 8]
- Expected Output:
2
- Justification: The subarray
[7, 8]
has a sum of15
, which is equal totarget
and is the smallest possible subarray.
Example 2:
- Input:
target = 11
,nums = [2, 1, 5, 2, 8]
- Expected Output:
3
- Justification: The subarray
[5, 2, 8]
has a sum of15
, which meets thetarget
and is the smallest possible subarray.
Example 3:
- Input:
target = 8
,nums = [2, 1, 5, 2, 3]
- Expected Output:
3
- Justification: The subarray
[5, 2, 3]
has a sum of10
, which meets thetarget
and is the smallest possible subarray.
Constraints:
- 1 <= target <= 10<sup>9</sup>
- 1 <= nums.length <= 10<sup>5</sup>
- 1 <= nums[i] <= 10<sup>4</sup>
Solution
To solve this problem, we use a sliding window approach. This method involves maintaining a window that expands and contracts while checking the sum of its elements. By adjusting the window's size dynamically, we can efficiently find the minimum length subarray that meets or exceeds the target
sum. This approach works because it avoids re-evaluating sums from scratch, reducing unnecessary calculations.
This method is effective because it allows us to traverse the array in linear time. We expand the window by moving the right end until the sum is sufficient, then contract by moving the left end to find the smallest subarray. This two-pointer technique ensures we cover all possibilities without redundant checks, optimizing performance.
Step-by-Step Algorithm
-
Initialize Variables:
- Set
start
to0
to denote the start of the sliding window. - Set
min_length
to a large number (e.g., infinity) to keep track of the minimum subarray length found. - Set
current_sum
to0
to keep track of the sum of the current window.
- Set
-
Iterate Through Array:
- Use a
for
loop withend
ranging from0
ton-1
(wheren
is the length ofnums
).
- Use a
-
Expand the Window:
- For each
end
index, addnums[end]
tocurrent_sum
.
- For each
-
Contract the Window:
- Use a
while
loop to check ifcurrent_sum
is greater than or equal totarget
. - If it is, update
min_length
to the smaller ofmin_length
and the length of the current window (end - start + 1
). - Subtract
nums[start]
fromcurrent_sum
to reduce the window size. - Move the
start
pointer to the right by incrementingstart
.
- Use a
-
Finalize Result:
- After the loop, check if
min_length
is still a large number. - If it is, return
0
(meaning no valid subarray was found). - Otherwise, return
min_length
.
- After the loop, check if
Algorithm Walkthrough
Using Example 1:
Input: target = 15
, nums = [1, 2, 3, 4, 5, 6, 7, 8]
-
Initialize Variables:
start = 0
min_length = infinity
current_sum = 0
-
Iterate Through Array:
-
end = 0
: Addnums[0]
tocurrent_sum
→current_sum = 1
current_sum
(1) is less thantarget
(15), so do nothing.
-
end = 1
: Addnums[1]
tocurrent_sum
→current_sum = 3
current_sum
(3) is less thantarget
(15), so do nothing.
-
end = 2
: Addnums[2]
tocurrent_sum
→current_sum = 6
current_sum
(6) is less thantarget
(15), so do nothing.
-
end = 3
: Addnums[3]
tocurrent_sum
→current_sum = 10
current_sum
(10) is less thantarget
(15), so do nothing.
-
end = 4
: Addnums[4]
tocurrent_sum
→current_sum = 15
current_sum
(15) is equal totarget
(15), so:- Update
min_length
→min_length = min(infinity, 4 - 0 + 1) = 5
- Subtract
nums[start]
(1) fromcurrent_sum
→current_sum = 14
- Increment
start
→start = 1
- Update
-
end = 5
: Addnums[5]
tocurrent_sum
→current_sum = 20
current_sum
(20) is greater thantarget
(15), so:- Update
min_length
→min_length = min(5, 5 - 1 + 1) = 5
- Subtract
nums[start]
(2) fromcurrent_sum
→current_sum = 18
- Increment
start
→start = 2
- Update
current_sum
(18) is still greater thantarget
(15), so:- Update
min_length
→min_length = min(5, 5 - 2 + 1) = 4
- Subtract
nums[start]
(3) fromcurrent_sum
→current_sum = 15
- Increment
start
→start = 3
- Update
current_sum
(15) is equal totarget
(15), so:- Update
min_length
→min_length = min(4, 5 - 3 + 1) = 3
- Subtract
nums[start]
(4) fromcurrent_sum
→current_sum = 11
- Increment
start
→start = 4
- Update
-
end = 6
: Addnums[6]
tocurrent_sum
→current_sum = 18
current_sum
(18) is greater thantarget
(15), so:- Update
min_length
→min_length = min(3, 6 - 4 + 1) = 3
- Subtract
nums[start]
(5) fromcurrent_sum
→current_sum = 13
- Increment
start
→start = 5
- Update
-
end = 7
: Addnums[7]
tocurrent_sum
→current_sum = 21
current_sum
(21) is greater thantarget
(15), so:- Update
min_length
→min_length = min(3, 7 - 5 + 1) = 3
- Subtract
nums[start]
(6) fromcurrent_sum
→current_sum = 15
- Increment
start
→start = 6
- Update
current_sum
(15) is equal totarget
(15), so:- Update
min_length
→min_length = min(3, 7 - 6 + 1) = 2
- Subtract
nums[start]
(7) fromcurrent_sum
→current_sum = 8
- Increment
start
→start = 7
- Update
-
-
Finalize Result:
min_length
is 2, which is not infinity.- Return
min_length
, which is2
.
This is the smallest subarray whose sum is at least 15, and it is [7, 8]
.
Code
Complexity Analysis
- Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the array. This is because each element is processed at most twice, once by the
end
pointer and once by thestart
pointer. - Space Complexity: The space complexity of this algorithm is O(1) because we are using a constant amount of extra space regardless of the input size.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible