Start learning free

LESSON 196 OF 338 · NESTED LOOPS & BRUTE FORCE

Remove Duplicates From Array in Go: O(n^2) with a Slice

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

    GO · NESTED LOOPS & BRUTE FORCE

    Remove Duplicates From Array in Go, explained

    Problem overview

    The function removeDuplicates(nums []int) []int receives a slice of integers and must return a new slice that holds each distinct value once. The order of the result does not matter to the problem. For [2, 3, 1, 1, 4, 3, -2, 1] the answer holds 2, 3, 1, 4, -2.

    The lesson asks for O(n^2) time and O(n) extra space. Faster solutions based on a hash set come in later lessons.

    Approach: keep a list of what has been seen

    Walk through nums from left to right and build a second slice, uniqueValues. For each value, ask whether it is already in uniqueValues. If not, this is its first occurrence, so append it. If so, skip it.

    The membership test scans uniqueValues element by element. In the worst case, when all n values are different, the list grows to length n and the k-th test scans k elements, so the total work is about n^2 / 2, which is O(n^2). The result slice can hold up to n values, so the extra space is O(n).

    A side effect of this approach is that the values come out in the order of their first appearance. The input above gives [2 3 1 4 -2].

    Step by step

    1. Declare uniqueValues with := as []int{}, an empty slice. It will hold each value the first time it is met, and it is the answer at the end.
    2. Loop with range. Only the values matter, so write for _, value := range nums. range gives an index and a value on each pass, and _ discards the index. Go rejects unused variables, so naming the index without using it would not compile.
    3. Test and append. The environment provides a helper, containsInt(uniqueValues, value), that returns true when the value is in the slice. If it returns false, append: uniqueValues = append(uniqueValues, value). The result of append must be assigned back, because append may allocate a new, larger backing array and return a slice that points to it.
    4. Return uniqueValues after the loop.

    The solution in Go

    func removeDuplicates(nums []int) []int {
    uniqueValues := []int{}
    for _, value := range nums {
        if !containsInt(uniqueValues, value) {
            uniqueValues = append(uniqueValues, value)
        }
    }
    return uniqueValues
}

    Go details:

    • containsInt is not part of the standard library; the lesson supplies it. It is a linear search, equivalent to a loop that returns true on the first equal element. Since Go 1.21 the standard slices.Contains does the same job. Either way each call costs time proportional to the length of the slice, which is where the O(n^2) comes from.
    • Empty versus nil. []int{} is an empty, non-nil slice. For an empty input the function returns it, with length 0. A var uniqueValues []int would work equally well with append, but would be nil for an empty input, which prints the same.
    • range copies the value. value is a copy of each element, which is fine for integers.
    • Input untouched. The function builds a new slice, so nums is not modified.
    • ! negates a boolean. Go has no not keyword.

    Complexity

    Time: O(n^2). The loop runs n times, and each iteration scans uniqueValues, which can hold up to n values. Appending is amortized constant time.

    Space: O(n). uniqueValues can hold every input value if none repeat.

    Edge cases and common mistakes

    • Empty input. The loop does not run and the function returns an empty slice.
    • All values equal. [5, 5, 5] gives [5].
    • Forgetting to assign the result of append. Writing append(uniqueValues, value) as a statement is a compile error, because the new slice would be thrown away. Always write uniqueValues = append(...).
    • Checking against nums instead of uniqueValues. Every value is in nums, so nothing would ever be appended.
    • Negative numbers and zero. They are ordinary values, and -2 in the example is kept once.
    • Using a map without knowing the order. A map-based version is faster, but ranging over a map gives random order, so the output order would vary. That is allowed here, since order is free, but it would differ from this version's first-appearance order.

    Testing

    • [2, 3, 1, 1, 4, 3, -2, 1] gives [2 3 1 4 -2].
    • [5, 5, 5] gives [5].
    • An empty slice gives an empty slice.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free