Start learning free

LESSON 240 OF 414 · PARTIAL SUMS #1

Longest Subarray With Sum At Most S in Rust: O(n²) Brute Force

Practice O(n2) Read the full explanation

Given an array of positive integers and a number S, find the longest contiguous subarray having the sum at most S.

Return the start and end indices denoting this subarray.

Example

Input: nums = [3, 2, 5, 2, 2, 1, 1, 3, 1 , 2], S = 11
Output: [3, 8]
Explanation:the subarray nums[3...8] of sum 10

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.


STEP 1 OF 10
    Ctrl + Enter to check

    RUST · PARTIAL SUMS #1

    Longest Subarray With Sum At Most S in Rust, explained

    Problem overview

    The function longest_subarray receives a vector of positive integers, nums, and a limit s. It must find the longest contiguous subarray whose sum is at most s and return its first and last index as a vector of two i32 values.

    In the example, nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and s = 11. The subarray at indices 3 to 8 is [2, 2, 1, 1, 3, 1], with sum 10. Extending it by one element on the right gives 12, which is over the limit, so the answer is [3, 8]. The statement allows O(n²) time and O(1) extra space.

    Approach: every start, growing end

    A subarray is fixed by its start and its end. Fix the start i and extend the end j one element at a time. The sum of nums[i..=j] then needs only one addition per step, because it is the previous sum plus nums[j]. Whenever that sum is within the limit and the subarray is longer than the best one so far, the answer is updated.

    Without the running sum, adding up every subarray from scratch would take O(n³) time. Reusing the sum as the end moves right brings it down to O(n²), the budget the statement sets.

    There is a tie in the example. The subarray at indices 4 to 9 also has length 6, and it sums to 2 + 1 + 1 + 3 + 1 + 2 = 10. The comparison max_len < ... is strict, so only a strictly longer subarray replaces the stored one, and the earlier [3, 8] stays.

    Step by step

    1. Create answer as vec![0i32, 0i32]. It will hold the start and end of the longest valid subarray found so far. If no element fits under s, the function returns [0, 0].
    2. Create max_len as 0i32. Any valid subarray is longer than 0, so the first valid one replaces it.
    3. Loop over the start i from 0 to n - 1, using the n the starting code provides.
    4. Declare sum as 0i32 inside that loop. It restarts at 0 for every new start.
    5. Loop over the end j from i to n - 1.
    6. Add nums[j] to sum. Now sum covers indices i to j.
    7. Test two conditions together: the sum is at most s, and the length j - i + 1 beats max_len. The length is a usize, so it is cast to i32 for the comparison.
    8. Record the new length in max_len.
    9. Record the indices in answer, each cast with as i32.
    10. Return answer after both loops, as the tail expression.

    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;
        for i in 0..n {
            let mut sum = 0i32;
            for j in i..n {
                sum += nums[j];
                if sum <= s && max_len < (j - i + 1) as i32 {
                    max_len = (j - i + 1) as i32;
                    answer = vec![i as i32, j as i32];
                }
            }
        }
        answer
    }
}

    The Rust details worth a closer look:

    • Two integer types. The indices i and j are usize, because they come from ranges over n and index the vector. The sums, the length counter and the result are i32. Rust never converts between them silently, so the length j - i + 1 must be cast with as i32 before it meets max_len.
    • The cast placement. The parentheses in (j - i + 1) as i32 make the cast apply to the whole length. Since j >= i, the subtraction never goes below zero.
    • Short-circuit &&. If sum <= s is false, the length comparison isn't evaluated.
    • vec![i as i32, j as i32]. The macro builds a new vector, and assigning it to answer drops the old one.
    • Tail expression. answer has no semicolon. With one, the function would return () and not compile.
    • Overflow. The running sum is an i32. In an optimized build, a sum past the i32 range wraps and could pass the sum <= s test by accident; a debug build panics instead.

    Complexity

    Time: O(n²). The outer loop runs n times and the inner loop up to n times, with constant work for each pair. That makes about n(n + 1) / 2 steps in total.

    Space: O(1). A few integers and the two-element answer.

    The inner loop could stop as soon as sum exceeds s. All the numbers are positive, so extending the subarray can only raise the sum. This lesson's version keeps scanning, which is correct, just wasteful. That monotonic property is also what lets a faster two-pointer method reach O(n).

    Edge cases and common mistakes

    • No element fits. [4, 5] with s = 3 returns [0, 0]. That is the starting value of answer, so the result looks like a valid one-element subarray even though nothing qualifies.
    • A single element qualifies. [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] with s = 1 returns [5, 5], the first 1. With s = 0 nothing fits and the result is [0, 0].
    • The whole vector fits. With s = 100 the example returns [0, 9].
    • Ties. The strict < keeps the earliest of several equally long subarrays. Using <= would keep the latest.
    • Forgetting to reset sum. Declaring it outside the outer loop would carry totals from one start into the next.
    • Comparing the sum, not the length. The best subarray is the longest one, not the one with the largest sum.

    Testing

    • [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] with s = 11 gives [3, 8].
    • The same vector with s = 1 gives [5, 5].
    • The same vector with s = 100 gives [0, 9].
    • [4, 1] with s = 3 gives [1, 1].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free