Start learning free

LESSON 240 OF 671 · SETS

Remove Repeats in Go: Keep First Copies with a Set

Practice Read the full explanation

You get a slice of integers nums. Some values may appear more than once.

Return a new slice that has each value only once.

Keep the first copy of each value and drop the later ones. The values stay in the order they first appear in nums.

 

Example 1:

Input: nums = [3, 1, 3, 2, 1]
Output: [3, 1, 2]
Explanation: The second 3 and the second 1 are repeats.
They are dropped, and 3, 1 and 2 stay in their order.

Example 2:

Input: nums = [6, 6, 6, 6]
Output: [6]
Explanation: Only the first 6 stays.

Example 3:

Input: nums = [4, 9, 2]
Output: [4, 9, 2]
Explanation: No value repeats, so every number stays.

 

Constraints:

  • nums has at least one number.
  • Every number is between -109 and 109.
STEP 1 OF 7
    Ctrl + Enter to check

    GO · SETS

    Remove Repeats in Go, explained

    Problem overview

    removeRepeats receives a slice of integers nums and returns a new slice with each value once. The first copy of each value is kept, later copies are dropped, and the values stay in the order they first appear.

    For [3, 1, 3, 2, 1] the answer is [3 1 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] it is [6], and for [4, 9, 2], with no repeats, nothing changes.

    Approach

    Read the numbers from left to right and remember which ones have appeared. A number that isn't remembered yet is a first copy, so it goes into the result. One that is remembered is a repeat and is skipped. Reading in order is what keeps the first copies and preserves their order.

    Go has no set type, so a map[int]bool plays that role. A key that isn't in the map reads as false, which makes !seen[num] true exactly for a new value.

    Step by step

    1. Create the map seen := map[int]bool{}.
    2. Create result := []int{}. It starts empty and append grows it.
    3. Loop over nums with for _, num := range nums.
    4. If !seen[num], append num to result (assigning the longer slice back) and set seen[num] = true.
    5. Return result after the loop.

    The solution in Go

    func removeRepeats(nums []int) []int {
    seen := map[int]bool{}
    result := []int{}
    for _, num := range nums {
        if !seen[num] {
            result = append(result, num)
            seen[num] = true
        }
    }
    return result
}

    append may allocate a bigger backing array and returns the slice to use, so its result must be assigned back to result. Calling append(result, num) on its own line would discard the new element.

    Here is what the loop does with [3, 1, 3, 2, 1], showing each number and the result after it:

    3 new -> [3]
1 new -> [3 1]
3 repeat -> [3 1]
2 new -> [3 1 2]
1 repeat -> [3 1 2]

    Each number is checked against seen before it is recorded, so the first 3 passes and the second 3 does not. Since the slice is built in reading order, the surviving numbers keep their relative order.

    The set makes each check cost about one step, so the whole function reads the input once. Without a set you would search the result slice for every number, which gets slower as the slice grows.

    Testing

    [3 1 3 2 1]  ->  [3 1 2]
[6 6 6 6]    ->  [6]
[4 9 2]      ->  [4 9 2]

    Another way to remove repeats is to scan the result slice before each append. That also gives the right answer, but each scan grows with the result, so large inputs get slow. The set keeps the check at one lookup, and the memory cost is one map entry per different value. The result slice is also never nil here: it starts as []int{}, so the function returns an empty but valid slice when given one.

    Common mistakes

    • Looping over the map to build the result. Map order is random in Go, so the output order would not match the order in nums. Build the result from the slice and use the map only for lookups.
    • Returning inside the loop. That returns after the first number. The return goes after the loop.
    • Forgetting to mark the number as seen. Without seen[num] = true every number looks new and nothing is removed.
    • Not assigning the result of append. The slice stays empty.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free