Start learning free

LESSON 239 OF 414 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Rust: Sliding Window in O(n)

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find the contiguous subarray of length exactly k with the maximum sum, and return its first and last indices.

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: [4, 6]
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 7
    Ctrl + Enter to check

    RUST · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Rust, explained

    Problem overview

    The function max_sum receives a vector of integers, nums, and a positive integer k. Among all contiguous subarrays of length exactly k, it finds the one with the largest sum and returns its first and last index as a vector of two i32 values.

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the window at indices 4 to 6 holds 6, 6 and 4, with sum 16. That is the largest, so the function returns [4, 6].

    Approach: slide the window instead of re-adding it

    The straightforward method sums every window from scratch, which costs k additions for each of the n - k + 1 windows, or O(n * k) in all. But two neighbouring windows share k - 1 elements. The window starting at i is the previous window with one element removed on the left, nums[i - 1], and one added on the right, nums[i + k - 1].

    So the sum needs only one subtraction and one addition to move one step. Compute the first window's sum once, then update it as the window slides across the vector. Every window gets its sum in constant time, and the whole scan is O(n).

    On the example, the first window [5, 6, 1] sums to 12. Moving right removes 5 and adds 2, giving 9. Then it removes 6 and adds 6, giving 9. Next it removes 1 and adds 6 for 14, then removes 2 and adds 4 for 16, and finally removes 6 and adds 3 for 13. The best, 16, was reached when the window started at index 4.

    The same trick works whenever a window has a fixed size and its value can be updated by removing one element and adding another: sums, counts and similar totals. It doesn't depend on the values being positive, so negative numbers need no special handling.

    Step by step

    1. Sum the first window. The slice nums[..k] holds the first k elements, and iter().sum() adds them. The variable sum is an annotated i32 and is declared mut, because it will change as the window moves.
    2. Set best to sum. The first window is the best one seen so far. No sentinel value is needed.
    3. Set answer to the first window's bounds, 0 and k - 1, as i32 values. If no later window beats it, this is the result.
    4. Loop over the remaining starts, with i from 1 to n - k inclusive.
    5. Slide the window. Subtract the element that just left, nums[i - 1], and add the one that just entered, nums[i + k - 1].
    6. Compare. If sum is greater than best, update both best and answer. The strict comparison keeps the earliest window when two have equal sums.
    7. Return answer as the tail expression.

    The solution in Rust

    impl Solution {
    fn max_sum(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = nums.len();
        let mut sum: i32 = nums[..k].iter().sum();
        let mut best = sum;
        let mut answer = vec![0i32, k as i32 - 1];
        for i in 1..=(n - k) {
            sum = sum - nums[i - 1] + nums[i + k - 1];
            if sum > best {
                best = sum;
                answer = vec![i as i32, (i + k - 1) as i32];
            }
        }
        answer
    }
}

    The Rust details worth a closer look:

    • Shadowing. let k = k as usize; creates a new k of type usize that hides the i32 parameter, so it can be used in slices and index arithmetic.
    • Open-ended slice. nums[..k] is shorthand for nums[0..k]. It excludes index k, so it has exactly k elements.
    • Why sum is annotated. iter().sum() can produce several numeric types, so the compiler needs : i32 to know which one to build.
    • The empty range. When k equals n, the loop range 1..=0 is empty and the body never runs, so the answer is the first window.
    • Cast precedence. k as i32 - 1 means (k as i32) - 1. The index arithmetic i + k - 1 is done in usize and cast afterwards.
    • A k larger than the vector. The slice nums[..k] panics with an out-of-range message. The lesson assumes k is at most the length of nums.
    • Overflow. The running sum is an i32. In the optimized build, a window total beyond the i32 range wraps silently; a debug build panics.

    Complexity

    Time: O(n). The first window costs k additions and each of the other n - k windows costs two operations. Each element enters the window once and leaves it once.

    Space: O(1). The slice is a borrowed view, and only a few integers and the two-element answer are stored.

    Edge cases and common mistakes

    • k equals the length. There is a single window, and the example with k = 8 returns [0, 7].
    • k = 1. Each element is a window. The example returns [1, 1], the first 6.
    • Ties. For [1, 3, 2, 2, 3, 1] with k = 2, the windows at 1 and 3 both sum to 5, and the answer is [1, 2]. A >= comparison would move it to the later window, [3, 4].
    • Negative values. [-5, -2, -7, -1] with k = 2 gives [0, 1], a sum of -7. Because best starts from the first window rather than 0, negative sums work.
    • Wrong entering index. The element that enters is nums[i + k - 1], the last element of the new window. Using nums[i + k] reads one element too far and panics on the final window.
    • Forgetting to subtract. Adding the new element without removing the old one turns the window into a growing prefix.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3] with k = 3 gives [4, 6].
    • The same vector with k = 8 gives [0, 7].
    • The same vector with k = 1 gives [1, 1].
    • [1, 3, 2, 2, 3, 1] with k = 2 gives [1, 2].
    • [-5, -2, -7, -1] with k = 2 gives [0, 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