Problem overview
The function longest_subarray receives a vector nums of positive integers and a limit s. It must find the longest contiguous subarray whose sum is at most s and return its first and last indices as a Vec<i32>.
For nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and s = 11 the answer is [3, 8]. The subarray nums[3..=8] is [2, 2, 1, 1, 3, 1], with sum 10 and length 6. Adding the next element, 2, would make 12, which is over the limit. The statement asks for O(n) time and O(1) extra space.
Approach: a window that never moves backward
The first lesson on this problem tries every start and extends each one to the right, which is O(n²). This lesson avoids the repeated work. All numbers are positive, so two facts hold:
- If the window from
firsttolastfits unders, then any window inside it fits too. - If the window from
firstcannot be extended to includelast + 1, then no window that starts atfirstor earlier can reach that far. A later start is the only way to include more.
So the right end last never needs to go back. For each start first, keep extending the window to the right while it still fits. Then move first one step: the element at first leaves the window, the sum drops, and the old right end is a good place to continue. Each element is added once and removed once, so the total work is linear.
In this lesson the window is described as the elements from first up to last - 1. The index last is the next element to try.
Step by step
- Create
answerasvec![0i32, 0i32]. It is a placeholder for the start and end indices, replaced as soon as a valid subarray is found. The suffixes make the elementsi32, matching the return type. - Create three more variables, each with
let mut:max_lenas0i32(the longest length so far),sumas0i32(the window's sum) andlastas0usize(the next element to try).lastis ausizebecause it indexesnums. - Loop over each start:
for first in 0..n. The variablelastis declared outside this loop on purpose. It keeps its value whenfirstmoves, which is what makes the scan linear. - Grow the window with
while last < n && sum + nums[last] <= s. The bound check comes first, sonums[last]is never read past the end. - Add the element:
sum += nums[last]. - Record the length. The window now covers
firstthroughlast, so its length islast - first + 1. If that is more thanmax_len, update bothmax_lenandanswer. The indices areusizeandmax_lenisi32, so each is converted withas i32. Using<rather than<=keeps the leftmost window when two have the same length. - Move on:
last += 1. Rust has no++operator. - Slide the start. After the
whileloop,sum -= nums[first]: the element atfirstleaves the window beforefirstadvances. - Return
answerafter the loop, with no semicolon.
The solution in Rust
impl Solution {
fn longest_subarray(nums: Vec<i32>, s: i32) -> Vec<i32> {
let n = nums.len();
let mut answer = vec![0i32, 0i32];
let mut max_len = 0i32;
let mut sum = 0i32;
let mut last = 0usize;
for first in 0..n {
while last < n && sum + nums[last] <= s {
sum += nums[last];
if max_len < (last - first + 1) as i32 {
max_len = (last - first + 1) as i32;
answer = vec![first as i32, last as i32];
}
last += 1;
}
sum -= nums[first];
}
answer
}
}
Rust details worth knowing:
- No implicit conversions. Rust never mixes integer types silently.
last - first + 1is ausize, so comparing it with thei32max_lenneedsas i32. The cast is safe here because lengths are small. &&short-circuits. Iflast < nis false, the right side is not evaluated, sonums[last]never runs withlast == n. Indexing out of bounds would panic.- The final expression.
answerwithout a semicolon is the function's value. With a semicolon the body would evaluate to()and not compile. - Subtraction on
usize. The lessons build with optimizations, whereusizesubtraction that goes below zero wraps silently. In a debug build, the same overflow panics. This matters in one situation, described below.
Complexity
Time: O(n). The index last only increases, and it can increase at most n times over the whole run. The outer loop runs n times. The inner while loop, summed over all outer passes, runs at most n times, so the two together are linear.
Space: O(1). The code keeps a few integers and the two-element answer.
Edge cases and common mistakes
- Everything fits.
[1, 2, 3]withs = 100returns[0, 2], the whole vector. - Ties.
[1, 1, 1]withs = 2returns[0, 1], because the strict comparison keeps the first window of that length. - A single element over the limit. In
[5, 1, 1, 9, 2]withs = 3, the 5 and the 9 can never be part of a window, and the answer is[1, 2]. When the window is empty at somefirst,laststill equalsfirst, and the code subtracts an element that was never added. The sum goes negative, and the next pass re-adds the same element throughlast, which restores balance. In an optimized build this gives correct answers. In a debug build, the length computationlast - first + 1at that moment underflows and panics. - Nothing qualifies. If every element exceeds
s, as in[9]withs = 3, no subarray is valid, but the function returns the placeholder[0, 0]. The lesson does not define another result for this case. - Negative numbers. The window idea depends on positive values. With negatives, dropping an element can raise the sum, so the pointer logic breaks.
- Resetting
lastinside the loop. Iflastis set back tofirston each pass, the algorithm becomes quadratic again. - Forgetting to subtract
nums[first]. The sum then keeps elements that are no longer in the window, and later windows come out too short.
Testing
[3, 2, 5, 2, 2, 1, 1, 3, 1, 2]withs = 11gives[3, 8].[1, 2, 3]withs = 100gives[0, 2].[1, 1, 1]withs = 2gives[0, 1].[5, 1, 1, 9, 2]withs = 3gives[1, 2].[5, 5, 5, 1, 1]withs = 3gives[3, 4].
