Start learning free

LESSON 223 OF 414 · BRUTE FORCE

Longest Subarray Without Repeating in Rust: O(n^3) Brute Force

Practice O(n3) Read the full explanation

Given an input array of integers, find the length of the longest subarray without repeating integers.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Note:

For this lesson, your algorithm should run in O(n^3) time and use O(1) extra space.
(There exist faster solutions which we will discuss in future lessons)


STEP 1 OF 6
    Ctrl + Enter to check

    RUST · BRUTE FORCE

    Longest Subarray Without Reapeating in Rust, explained

    Problem overview

    The function longest_subarray_without_reapeating receives a vector of integers, nums, and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, so [5, 6, 2] is a subarray of [2, 5, 6, 2, 3], while [2, 6] is not.

    For nums = [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. Both [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] have five different values, and no window of six elements avoids a repeat. An empty vector gives 0.

    The lesson accepts O(n^3) time and O(1) extra space. Faster solutions exist, but this lesson is about checking every candidate directly.

    Approach: try every start, extend until a repeat

    A subarray is fixed by where it starts and where it ends. The solution picks every start i, then grows the subarray one element at a time by moving the end j to the right.

    When the subarray grows to include nums[j], only that one value is new, so the only thing to check is whether it already appears in the part before it, nums[i..j]. If it does, every longer subarray from the same start contains that repeat too, so the inner loop can stop with break. If it doesn't, the subarray from i to j is valid, and its length j - i + 1 competes with the best length found so far.

    On the example, start i = 1 extends over 5, 6, 2, 3 and 1, reaching length 5. At j = 6 the value 5 is already in nums[1..6], so that start stops. Start i = 0 stops earlier: at j = 3 the second 2 repeats the first, leaving a best length of 3 from that start.

    Why does the lesson accept such a slow method? It is the easiest one to get right, and it shows exactly where the time goes: the same elements are re-scanned by contains every time the end moves one step. Faster approaches avoid that repeated scanning, so it helps to see the cost here first.

    Step by step

    1. Keep the best length so far in result, a mutable i32 that starts at 0. For an empty vector it is never updated, which is the right answer.
    2. Loop over the starting index i in 0..nums.len().
    3. Loop over the ending index j in i..nums.len(). Starting at i means the one-element subarray is checked first.
    4. Check for a repeat. Take the slice nums[i..j], the elements already in the subarray, and ask whether it contains nums[j]. On a repeat, leave the inner loop.
    5. Record the length. With no repeat, the subarray nums[i..=j] is valid and has j - i + 1 elements. Take the larger of that and result, converting the usize length to i32.
    6. Return result as the last expression.

    The solution in Rust

    impl Solution {
    fn longest_subarray_without_reapeating(nums: Vec<i32>) -> i32 {
        let mut result: i32 = 0;
        for i in 0..nums.len() {
            for j in i..nums.len() {
                if nums[i..j].contains(&nums[j]) {
                    break;
                }
                result = result.max((j - i + 1) as i32);
            }
        }
        result
    }
}

    The Rust details worth a closer look:

    • Slicing with a range. nums[i..j] borrows the elements from i up to but not including j. When j == i the slice is empty, so the first check at each start never finds a repeat. Slicing with i..j panics only if i > j or j is past the end, and neither can happen here.
    • contains takes a reference. A slice of i32 looks for an &i32, so the call is contains(&nums[j]). It scans the slice from the left, which is why it costs time proportional to the slice length.
    • result.max(...). max is a method on integers that returns the larger of two values. Both sides must have the same type, which is why the length is converted with as i32.
    • usize subtraction. j - i + 1 is safe because j >= i in the inner loop, so the subtraction never goes below zero.

    Complexity

    Time: O(n^3). There are about n^2 / 2 pairs (i, j), and for each one contains may scan up to j - i elements. When all values are different, no break ever fires and the total work grows with n^3. The break makes inputs with many repeats cheaper, but not the worst case.

    Space: O(1). Slices only borrow the vector, so the function stores a few integers.

    Edge cases and common mistakes

    • Empty vector. Neither loop runs and the function returns 0.
    • All values equal. For [4, 4, 4] each start has a valid subarray of length 1, and the second element repeats, so the answer is 1.
    • All values different. For [1, 2, 3, 4] no repeat is found, and the answer is the full length, 4.
    • Subarray versus subsequence. The elements must be neighbours. For [1, 2, 1, 2, 3] the answer is 3, from [1, 2, 3] at the end, and not a count of the distinct values that skips elements.
    • Checking nums[i..=j] for the repeat. That slice always contains nums[j], so every subarray would look like a repeat and the answer would be 0. The check must stop before j.
    • Using continue instead of break. After a repeat, longer subarrays from the same start are invalid too. With continue, the loop could count a later subarray that still contains the repeat.

    Testing

    • nums = [2, 5, 6, 2, 3, 1, 5, 6] gives 5.
    • nums = [] gives 0.
    • nums = [4, 4, 4] gives 1.
    • nums = [1, 2, 3, 4] gives 4.
    • nums = [1, 2, 1, 2, 3] gives 3.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free