LESSON 242 OF 338 · HASH TABLE

Longest Consecutive Sequence in Go: O(n) with a Map as a Set

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Example 2:

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even tho values 0, 1 and 2 appear 2 times each in nums

Note:

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

STEP 1 OF 8

Guided

Ctrl + Enter to check

GO · HASH TABLE

Longest Consecutive Sequence in Go, explained

Problem overview

The function longestConsecutive receives an unsorted slice of integers, nums, and returns the length of the longest run of consecutive integers that can be formed from its values. The run doesn't have to appear in order inside the slice: only the values matter.

For [100, 4, 200, 1, 3, 2] the values 1, 2, 3 and 4 form a run of length 4, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the answer is also 4, from 0, 1, 2 and 3. Duplicates are counted once.

The statement asks for O(n) time and O(n) extra space, which rules out sorting (O(n log n)).

Approach: start counting only at the beginning of a run

Put all the values in a set, so that "is this number present?" takes constant time. Then, for each number, ask whether it could be the first number of a run. It is the first exactly when value - 1 is not in the set.

From such a starting number, walk upward, checking value + 1, value + 2 and so on until a number is missing. The number of steps is the length of the run.

The check for the start is what keeps the algorithm linear. In [1, 2, 3, 4], only 1 passes the check, so the walk happens once and visits four numbers. If every number started its own walk, a long run would be walked again from each of its members, which is O(n²). With the check, each number belongs to exactly one run and is visited by exactly one walk, plus a constant number of lookups.

Trace on [100, 4, 200, 1, 3, 2]. The set is {100, 4, 200, 1, 3, 2}. The number 100 has no 99, so it starts a run of length 1 (101 is missing). The number 200 gives 1 as well. The number 1 has no 0, so it starts a walk: 2, 3 and 4 are present and 5 is not, so the length is 4. The numbers 2, 3 and 4 each have a predecessor in the set and are skipped. The result is 4.

Step by step

Start result at 0. It stays 0 for an empty slice, which is the correct answer.
Build the set. Make a map[int]struct{} called values and store struct{}{} under each number of nums. The keys are the distinct numbers.
Loop over the keys of values, not over nums. That skips duplicates automatically.
Test for a run start. Look up value-1 with the two-result form. The check passes when the key is not there.
Begin counting at 1, since the run already contains value.
Walk upward. Loop forever; if value+sequenceLength is missing, break; otherwise increase sequenceLength.
Keep the maximum of result and sequenceLength.
Return result after the loop.

The solution in Go

func longestConsecutive(nums []int) int {
    result := 0
    values := make(map[int]struct{})
    for _, value := range nums {
        values[value] = struct{}{}
    }
    for value := range values {
        if _, exists := values[value-1]; !exists {
            sequenceLength := 1
            for {
                if _, exists := values[value+sequenceLength]; !exists {
                    break
                }
                sequenceLength++
            }
            result = max(result, sequenceLength)
        }
    }
    return result
}

Go details in this code

The comma-ok lookup. _, exists := values[value-1] reads the map and reports whether the key is present. A plain values[value-1] on a missing key returns the zero value, which for struct{} looks the same as a present one, so the second result is the only reliable test.
Scoped variables. The exists declared in the if header lives only in that if. The one declared in the walk's if is a new variable that shadows it inside that statement, so there is no clash.
for range over a map. With a single variable you get the keys. Go randomises the iteration order on purpose, so the order in which runs are examined changes between executions. The result doesn't depend on it, because each run is measured completely.
for { ... } is Go's endless loop; it is the way to write a loop that ends with break, since Go has no while.
Built-in max is available from Go 1.21.

Complexity

Time: O(n) on average. Building the set takes n insertions. In the main loop each distinct number costs one lookup for the predecessor. The walk runs only from run starts, and the runs don't overlap, so all walks together visit each number at most once, plus one failed lookup per run. Map operations are constant time on average.

Space: O(n). The map holds each distinct value once.

Edge cases and common mistakes

Empty or nil slice. Nothing is inserted, the loop doesn't run, and the result is 0.
Duplicates. [0, 2, 0, 1, 2, 3, 1] gives 4. Each value is counted once, even though 0, 1 and 2 appear twice.
Negative numbers. [-2, -1, 0] gives 3. The method uses only addition and lookups, so the sign doesn't matter.
Skipping the start check. The code still returns correct answers, but a slice like 1, 2, ..., n then costs O(n²).
Sorting first. It works but takes O(n log n), which is over this lesson's budget.
Treating the slice as adjacent elements. The run is about values, not positions: in [100, 4, 200, 1, 3, 2] the run 1 to 4 is scattered.

Testing

[100, 4, 200, 1, 3, 2] gives 4.
[0, 2, 0, 1, 2, 3, 1] gives 4.
[] gives 0.
[-2, -1, 0] gives 3.

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

Start learning free