LESSON 237 OF 338 · HASH TABLE

Number of Distinct Values in Go: O(n) with a Set

Given an array of integers, count how many distinct values exist in the array.

Example:

Input: [1, 5, -3, 1, -4, 2, -4, 7, 7]
Output: 6
Explanation: the distinct values in the array are [1, 5, -3, -4, 2, 7]

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Distinct Values in Go, explained

Problem overview

The function distinctValues receives a slice of integers, nums, and returns how many different values it contains. For [1, 5, -3, 1, -4, 2, -4, 7, 7] the distinct values are 1, 5, -3, -4, 2 and 7, so the answer is 6. The statement asks for O(n) time and O(n) extra space.

Approach: remember what you have seen

One way to count distinct values is to sort the slice and count the places where a value differs from its neighbour. That costs O(n log n) for the sort. To reach O(n), trade memory for speed: keep a set of the values met so far. For each number, a set lookup takes O(1) on average. If the number is new, add it and count it; if it is already there, ignore it. Each distinct value is counted exactly once, on its first appearance.

Go has no set type, so a map stands in for one: map[int]struct{}. Only the keys matter. The empty struct struct{} has no fields and takes no memory, which makes it the conventional "no value" marker.

On the example, the first 1, 5, -3, -4, 2 and 7 are new and bump the counter. The second 1, the second -4 and the second 7 are found in the set and skipped. The counter ends at 6.

The sorting variant needs no extra memory beyond the sort itself, but it reorders the input and is slower for large slices. The set variant leaves nums untouched and finishes in a single pass, at the cost of up to n stored keys. That trade of space for time is the central idea of the hash table chapter.

Step by step

Create the set values with make(map[int]struct{}).
Start the counter answer at 0.
Loop over nums with range, naming each element value and discarding the index with _. The order does not matter for counting.
Test membership with the comma-ok lookup in the if header and check !exists. Only a first-time value passes.
Record it and count it: store struct{}{} under the key and increment answer.
Return answer.

The solution in Go

func distinctValues(nums []int) int {
    values := make(map[int]struct{})
    answer := 0
    for _, value := range nums {
        if _, exists := values[value]; !exists {
            values[value] = struct{}{}
            answer++
        }
    }
    return answer
}

The Go details:

struct{}{}. The first struct{} is the type, the second pair of braces creates a value of it.
Comma-ok. Reading a missing key gives the zero value, and for a struct with no fields that tells you nothing. The second result, exists, is what reports presence. It is scoped to the if.
The counter and the map. The answer could also be read as len(values) after the loop. The explicit counter makes the "first time seen" logic visible.

Complexity

Time: O(n). One pass, with one lookup and at most one insertion per element, each O(1) on average.

Space: O(n). In the worst case, every value is distinct and the map holds n keys.

Edge cases and common mistakes

Empty or nil slice. The loop does not run and the result is 0.
All equal values. [4, 4, 4] gives 1.
Zero as a value. [0] gives 1. With a plain read such as values[0] a stored zero and a missing key would look alike, which is why the code uses comma-ok.
Counting every element. Incrementing outside the if would just return len(nums).
Writing to a nil map. Declaring var values map[int]struct{} without make would panic on the first insertion.

Testing

[1, 5, -3, 1, -4, 2, -4, 7, 7] gives 6.
[] gives 0.
[4, 4, 4] gives 1.
[0] gives 1.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free