Problem overview
The function longest_subarray receives a vector of integers, nums, and a number k. A subarray is a run of neighbouring elements. The function returns the length of the longest subarray that contains at most k different values.
In the example, nums = [1, 2, 1, 2, 3] and k = 2. The first four elements, [1, 2, 1, 2], hold only the values 1 and 2, so that subarray is valid and has length 4. Adding the 3 would make three distinct values, so the answer is 4.
Duplicates don't count twice. [1, 2, 1, 2] has four elements but only two distinct values, and the limit applies to the distinct values.
Approach: a window that grows and shrinks
The brute-force idea is to try every start and every end, and count the distinct values in each subarray. That is slow, and the statement allows O(n^2) time. A sliding window does better, in O(n) time.
Keep a window [first, last] that always holds at most k distinct values. For each position last, taken as the right end:
- Add
nums[last]to the window. - If the window now has too many distinct values, move
firstto the right until it is valid again. - The window is now the longest valid subarray that ends at
last. Compare its length with the best so far.
Shrinking only from the left is enough, and it never needs to go back. Suppose the window ending at last - 1 was valid. Any window that ends at last and starts before first contains that window's elements plus one more, so it can't have fewer distinct values. Moving first back would only bring in more.
To know how many distinct values the window holds, the code keeps a HashMap from each value to how many times it occurs in the window. Its len() is the number of distinct values. A value must be removed from the map when its count reaches zero, otherwise the length would still count a value that has left the window.
Step by step
- Create the map
freq, from value to count, for the current window. - Create the answer and the left edge.
answerstarts at 0 and is ani32, like the return value.firststarts at 0 and is ausize, because it indexes the vector. - Loop over every possible right end,
last, from 0 to the end of the vector. - Count the new element. The entry API finds the slot for
nums[last], creates it with 0 if it is missing, and the+= 1through the returned reference bumps it. One line covers both a new value and one already present. - Shrink while invalid. A
whileloop runs as long as the window has more thankdistinct values.len()is ausizeandkis ani32, and Rust won't compare different integer types, so the length is cast withas i32. - Take the leftmost element out.
get_mutreturns anOptionholding a mutable reference to its count. The key is always present, sounwrapis safe. Decrease the count through the reference. - Remove the key at zero. If the count reached 0, delete the key from the map.
- Advance
firstby one, inside thewhileloop. - Record the window. After the loop the window is valid, and its length is
last - first + 1, converted toi32. Keep the larger of that andanswer. - Return
answeras the final expression, with no semicolon.
The solution in Rust
impl Solution {
fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
let mut freq: HashMap<i32, i32> = HashMap::new();
let mut answer = 0i32;
let mut first = 0usize;
for last in 0..nums.len() {
*freq.entry(nums[last]).or_insert(0) += 1;
while freq.len() as i32 > k {
let cnt = freq.get_mut(&nums[first]).unwrap();
*cnt -= 1;
if *cnt == 0 {
freq.remove(&nums[first]);
}
first += 1;
}
answer = answer.max((last - first + 1) as i32);
}
answer
}
}
The code uses HashMap by its short name, so the file needs use std::collections::HashMap; above the impl. The Rust details worth a closer look:
- The entry API.
freq.entry(key)returns an entry for the slot, andor_insert(0)gives back a&mut i32, creating the slot first when it is missing. The*dereferences that reference so+= 1changes the number stored in the map. get_mutand the borrow.cntis a mutable borrow of the map. It is last used in the comparison*cnt == 0, and the compiler ends the borrow there. That is whyfreq.removeis allowed inside theif. Ifcntwere used after theremove, the code would not compile.- References as keys.
get_mutandremovetake a reference to the key, which is why the code writes&nums[first]. - Index types. Indices are
usize, while the result isi32. The twoas i32casts convert between them. last - first + 1can't underflow.firstnever gets pastlast + 1, because the loop stops when the map is empty, and withk = 0that is the most it can do. So the subtraction stays at zero or above.answer.max(...).maxis a method on integers that returns the larger of two values.
Complexity
Time: O(n). last moves from 0 to n - 1 once. first only moves right, so across the whole run the while loop executes at most n times in total, not n times per element. Each map operation takes O(1) on average, so the total is linear. This is better than the O(n^2) the statement allows.
Space: O(n). The map holds at most min(n, k + 1) entries, which is O(n) in the worst case.
Edge cases and common mistakes
- Empty vector. The loop never runs and the function returns 0.
kis 0. No window may hold any value, so the answer is 0. The window shrinks to empty after every element.kis at least the number of distinct values. The whole vector is valid.[1, 2, 1, 2, 3]withk = 3returns 5.- Forgetting to remove a key at zero. The map would keep entries with count 0,
len()would overcount, and the window would shrink too much. - Counting elements instead of distinct values. The limit is on the number of different values, not the window length.
[4, 4, 4]withk = 1returns 3. - Comparing
usizewithi32.freq.len() > kdoesn't compile, because the types differ. The cast goes on the length.
Testing
nums = [1, 2, 1, 2, 3],k = 2gives4.nums = [1, 2, 1, 2, 3],k = 1gives1.nums = [1, 2, 1, 2, 3],k = 3gives5.nums = [1, 2, 3, 4],k = 2gives2.nums = [4, 4, 4],k = 1gives3.nums = [],k = 2gives0.
