Start learning free

LESSON 271 OF 414 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Rust: O(n²)

Practice O(n2) Read the full explanation

Given an array of integers, find the longest subarray that contains at most K distinct integers and return its length.

Example

Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 4
Explanation: the subarray nums[0...3] contains 2 distinct values: [1, 2] and is the longest subarray

Note:

Your algorithm should run in at most O(n2) time and use O(n) extra space.


STEP 1 OF 8
    Ctrl + Enter to check

    RUST · HASH TABLE

    Longest Subarray With At Most K Distinct Integers in Rust, explained

    Problem overview

    The function longest_subarray receives a vector of integers, nums, and an integer k. It returns the length of the longest subarray, a run of neighbouring elements, that contains at most k different values. Repeats of the same value count only once.

    For nums = [1, 2, 1, 2, 3] and k = 2 the answer is 4. The first four elements, [1, 2, 1, 2], hold only the values 1 and 2. Adding the 3 would make three distinct values, which is too many.

    The lesson asks for O(n²) time and O(n) extra space.

    Approach: extend from every start until the set gets too big

    A subarray is determined by its first index i and its last index j. The plan is to try each i as the start, and extend j to the right one element at a time, keeping the values of the subarray in a hash set. The set ignores repeats, so its length is the number of distinct values.

    The key observation is that extending a subarray can never reduce the number of distinct values. Once the set holds more than k values, every longer subarray from the same start is invalid too. The inner loop can stop there and the next start can begin.

    While the set size is still at most k, the subarray from i to j is valid, and j - i + 1 is a candidate for the answer.

    On [1, 2, 3, 1] with k = 2: from i = 0, the values 1 and 2 are accepted (length 2), then the 3 makes the set size 3 and the loop breaks. From i = 1, 2 and 3 are accepted (length 2), then the 1 breaks it. From i = 2, 3 and 1 give length 2. The answer is 2.

    The quadratic cost comes from rebuilding the set from scratch for every start. Faster solutions avoid that by moving both ends of the window forward without starting over, but this lesson keeps the plain version so the idea is easy to see.

    Step by step

    1. Keep the best length in answer, declared mut as 0i32. The suffix gives it the type the function returns.
    2. Loop over the start index i in 0..nums.len().
    3. Create a fresh set distinct, a mut HashSet<i32>, inside that loop so each start begins empty.
    4. Loop over the end index j in i..nums.len(). The subarray grows by one element each time.
    5. Insert nums[j] into distinct. If the value is already there, nothing changes.
    6. Stop when there are too many values. If the set's length is greater than k, break. len() is a usize and k an i32, and Rust compares only equal types, so the length is converted with as i32.
    7. Update the answer. The subarray has j - i + 1 elements. Convert it with as i32 and keep the larger of it and answer.
    8. Return answer on its own line after the loops, with no semicolon.

    The solution in Rust

    use std::collections::HashSet;

impl Solution {
    fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
        let mut answer = 0i32;
        for i in 0..nums.len() {
            let mut distinct: HashSet<i32> = HashSet::new();
            for j in i..nums.len() {
                distinct.insert(nums[j]);
                if distinct.len() as i32 > k {
                    break;
                }
                answer = answer.max((j - i + 1) as i32);
            }
        }
        answer
    }
}

    Rust details:

    • Precedence of as. In distinct.len() as i32 > k, the cast is applied to distinct.len() first and the comparison then happens between two i32 values. A cast followed by < can confuse the parser, but a cast followed by > is fine.
    • No implicit conversions. Comparing a usize with an i32 is a compile error. Every mix of integer types needs an explicit as.
    • Ranges. 0..nums.len() excludes its end, so i is always a valid index. For an empty vector the range is empty and the loop body doesn't run.
    • Copying into the set. insert(nums[j]) copies an i32, so the vector is untouched.
    • break exits only the inner loop, so the next start still runs.

    Complexity

    Time: O(n²). There are n starts, and each inner loop runs up to n steps with O(1) average work per insertion. When k is large enough that nothing breaks early, the total is about n²/2 steps.

    Space: O(n). The set holds up to k + 1 values, at most n, and a new set replaces it for each start.

    Edge cases and common mistakes

    • Empty vector. Returns 0.
    • k is 0. The very first insert makes the set size 1, which is more than 0, so nothing is ever accepted. [1, 2, 3] with k = 0 returns 0. A negative k behaves the same way.
    • k at least as large as the number of distinct values. The whole vector is valid: [1, 2, 3] with k = 5 returns 3.
    • Counting elements instead of distinct values. The limit applies to different values, not to the subarray's length. [5, 5, 5] with k = 1 returns 3.
    • Updating the answer before the check. The length must be recorded only after the set is known to be within the limit, or invalid subarrays would be counted.
    • Reusing one set across starts. Values from earlier subarrays would make the counts too high. Create the set inside the outer loop.

    Testing

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