LESSON 222 OF 414 · BRUTE FORCE

Remove Duplicates From Array in Rust: O(n^2) with contains

Practice O(n²) Read the full explanation

Given an array of integers, return a new array containing only the unique values.

The resulting array can be in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, -2, 1]
Output: [2, 3, 1, 4, -2]

Note:

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

Hints:

Let's use an extra array uniqueValues and add the unique values from nums there. We can traverse the array nums from left to right. We should add the current element into uniqueValues only if that value has not been seen before. How can we check this?

The current element has never been seen before if it doesn't occur in uniqueValues.

STEP 1 OF 4

Guided

Ctrl + Enter to check

RUST · BRUTE FORCE

Remove Duplicates From Array in Rust, explained

Problem overview

The function remove_duplicates receives a vector of integers, nums, and returns a new vector holding each distinct value once. The result can be in any order.

For nums = [2, 3, 1, 1, 4, 3, -2, 1] the answer is [2, 3, 1, 4, -2]. The values 1 and 3 appear several times in the input, and each is kept only at its first appearance. This solution keeps the order of first appearance.

The lesson accepts O(n^2) time and O(n) extra space, and notes that faster solutions come later.

Approach: build a list of values seen so far

Walk through nums from left to right and keep a second vector, unique_values. For each value, ask: is it already in unique_values? If not, this is its first appearance, so push it. If it is, skip it. When the walk ends, unique_values holds every distinct value once, in the order each first appeared.

The membership question is answered by contains, which scans the vector from the start until it finds the value or reaches the end. For an input of n values, the scan can look at up to n elements, and it runs once per element. That is where the O(n^2) comes from. It is the simplest correct approach, and it shows what the later solutions improve: a sorted vector lets you compare neighbours, and a hash set answers membership in constant time on average.

On the example, the loop starts with an empty unique_values. The values 2, 3 and 1 are pushed. The next 1 is found and skipped. Then 4 is pushed, the second 3 is skipped, -2 is pushed, and the last 1 is skipped. The result is [2, 3, 1, 4, -2].

Step by step

Create the result vector. Declare unique_values as a mutable Vec<i32> with Vec::new(). It is mut because the loop pushes into it.
Loop over the values. The indices aren't needed, so loop over &nums with the pattern &value. Iterating over a reference to the vector yields references, and the pattern copies each number out, so value is a plain i32.
Check and push. If !unique_values.contains(&value), push value. Each value is stored only the first time it appears.
Return unique_values as the last expression, with no semicolon.

The solution in Rust

impl Solution {
    fn remove_duplicates(nums: Vec<i32>) -> Vec<i32> {
        let mut unique_values: Vec<i32> = Vec::new();
        for &value in &nums {
            if !unique_values.contains(&value) {
                unique_values.push(value);
            }
        }
        unique_values
    }
}

The Rust details worth a closer look:

for &value in &nums. The expression &nums borrows the vector, and the loop yields &i32 items. The pattern &value on the left destructures the reference and copies the number out. This is allowed because i32 is Copy. Without the & in the pattern, value would be an &i32.
contains takes a reference. The method looks for an item of the vector's element type behind a reference, so the call is contains(&value). Passing value alone is a type error.
! negates the check. The block runs when the value is not yet in unique_values.
Explicit type. Vec::new() alone gives no hint about the element type, so the annotation Vec<i32> states it. It would also be inferred from the later push and the return type.
Borrowing. Looping over &nums doesn't consume nums, and unique_values is a separate vector, so reading from one and pushing into the other never conflict.
The last expression. A function body's final expression, written without a semicolon, is its return value.

Complexity

Time: O(n^2). Each of the n iterations calls contains, which compares against at most the current length of unique_values. When all values are different, that length grows from 0 to n - 1, giving about n^2 / 2 comparisons in total. With many duplicates, unique_values stays short and the loop runs faster, but the worst case remains O(n^2).

Space: O(n). In the worst case, when no value repeats, unique_values holds as many elements as nums.

Edge cases and common mistakes

Empty vector. The loop doesn't run and the function returns an empty vector.
No duplicates. The result is a copy of the input, in the same order.
All values equal. For [5, 5, 5] only the first 5 is pushed, and the result is [5].
Negative numbers. They are compared like any other value, so -2 in the example is kept once.
Leaving out the & in contains. unique_values.contains(value) doesn't compile, because the method expects a reference.
Forgetting mut. Pushing into a vector declared without mut is a compile error.
Ending with a semicolon. Writing unique_values; turns the last line into a statement, and the function then returns () instead of a vector, which doesn't match the return type.

Testing

nums = [2, 3, 1, 1, 4, 3, -2, 1] gives [2, 3, 1, 4, -2].
nums = [] gives [].
nums = [5, 5, 5] gives [5].
nums = [1, 2, 3] gives [1, 2, 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