Start learning free

LESSON 195 OF 347 · NESTED LOOPS & BRUTE FORCE

Remove Duplicates From Array in C#: O(n^2) with a List

Practice O(n2) 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 uniqueVals and push the unique values from nums there. We can traverse the array nums from left to right using an index i. We should push nums[i] into uniqueVals only if that value has not been seen before. How can we check this?

nums[i] has never been seen before if it doesn't occur in uniqueVals.
STEP 1 OF 4
    Ctrl + Enter to check

    C# · NESTED LOOPS & BRUTE FORCE

    Remove Duplicates From Array in C#, explained

    Problem overview

    The method RemoveDuplicates(int[] nums) takes an array of integers and returns a new int[] that holds each distinct value once. The result may be in any order. For {2, 3, 1, 1, 4, 3, -2, 1} the answer is {2, 3, 1, 4, -2}: the repeated 1s and the second 3 are dropped.

    The lesson allows O(n^2) time and O(n) extra space. It's the "no special tools" version of the problem, and later lessons replace the slow part with something faster.

    Approach: keep a list of what you have seen

    Walk through nums from left to right, and keep a growing collection of the distinct values met so far. For each value, ask whether the collection already contains it. If not, this is its first appearance, so add it. If yes, skip it. When the walk ends, the collection is the answer.

    That asks a question the collection must answer quickly: "have I seen this value?" A list can only answer by scanning its elements one by one, which costs up to O(n) per check. Doing that for each of the n values gives the O(n^2) bound. Because values are added in the order they are first seen, the output here also happens to keep the input's first-appearance order, which is a nice side effect. The problem doesn't require it.

    A hash set answers the membership question in constant time on average and would bring the whole method to O(n). This lesson stays with the list.

    Step by step

    1. Create the list. Declare a List<int> named uniqueValues with a new empty list. A list suits this because a C# array has a fixed size, and we don't know how many distinct values there will be.
    2. Loop over the values. The indices aren't needed, so a foreach loop with an int value reads each element of nums directly.
    3. Add only new values. Test !uniqueValues.Contains(value). Inside the if, call Add(value), so each value is stored only the first time it appears.
    4. Convert and return. The method must return an int[], so call ToArray() on the list after the loop.

    The solution in C#

    class Solution {
    public int[] RemoveDuplicates(int[] nums) {
        List<int> uniqueValues = new List<int>();
        foreach (int value in nums) {
            if (!uniqueValues.Contains(value)) {
                uniqueValues.Add(value);
            }
        }
        return uniqueValues.ToArray();
    }
}

    The C# details:

    • Arrays versus lists. An array's length is fixed when it is created. A List<T> grows as you call Add. The usual pattern is to collect into a list and convert to an array at the end.
    • Contains compares by value. For a List<int> it checks whether any element equals the given integer. It walks the list from the start, which is where the O(n) cost per call comes from.
    • ToArray() copies. It creates a new int[] with exactly as many elements as the list holds. The input array is never modified.
    • The loop variable is read-only. You can't assign to value inside a foreach. That's fine here because the loop only reads it.
    • Namespaces. List<T> lives in System.Collections.Generic. In a standalone program you need the matching using directive at the top of the file.

    Complexity

    Time: O(n^2). The loop runs n times. Each Contains call scans a list that holds at most n values, and in the worst case, when all values are distinct, the list grows to n. That makes about n(n - 1) / 2 comparisons in total. Add and ToArray cost O(1) amortised and O(n), so they don't change the bound.

    Space: O(n). The list holds up to n values, and ToArray() creates a second array of the same size.

    Edge cases and common mistakes

    • Empty array. The loop doesn't run, and the method returns an empty array.
    • All values equal. {5, 5, 5} gives {5}.
    • No duplicates. {1, 2, 3} comes back unchanged, as a new array.
    • Negative numbers. They need no special care. {-2, -2, 4} gives {-2, 4}.
    • Dropping the negation. Without !, the check only succeeds for values already in the list. The list starts empty, so nothing is ever added and the method returns an empty array.
    • Returning the list. The method's return type is int[], so returning uniqueValues directly doesn't compile. Convert with ToArray().
    • Checking the original array instead of the list. nums.Contains(value) is always true, because every value is in nums, so nothing would be added.

    Testing

    • {2, 3, 1, 1, 4, 3, -2, 1} gives {2, 3, 1, 4, -2}.
    • {5, 5, 5} gives {5}.
    • {1, 2, 3} gives {1, 2, 3}.
    • An empty array gives an empty array.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free