Why iterating over slice may be slower than over map in Go?

Question

I was doing the famous Longest Consecutive Sequence problem on leetcode and came up with two working solutions. They differ in one line only so this code is for both:

type void struct{}

func longestConsecutive(nums []int) int {
    max_seq := 0
    numSet := make(map[int]void, len(nums))

    for _, n := range nums {
        numSet[n] = void{}
    }

    for n := range numSet {  << the Map version
    for _, n := range nums { << the Slice version

        if _, prev_exists := numSet[n-1]; !prev_exists {
            for i := 1; ; i++ {
                if _, next_exists := numSet[n+i]; !next_exists {
                    max_seq = max(max_seq, i)
                    break
                }
            }
        }
    }
    return max_seq
}

Both solutions work and take about 11-12 MB of memory, but drastically differ in speed:

1832 ms for the Slice version
84 ms for the Map one

I ran both several times, first thinking it is due to the lags on the server side, but nothing changed, iterating over slice was about 20 times slower every time. This is counterintuitive to me, because slice is based on array which should make the loop very fast for its simple internal structure comparing to the map which is hash. I must be getting something wrong here and want to understand. Please help!

Answer 1

The issue is duplicate values, which nothing in the problem description rules out:

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

Your code with the slice has O(n) time complexity on the size of the input when there are no duplicates, but with unrestricted duplicates, the worst case time complexity is O(n^2) (consider a list where half the entries are 1 and the other half is 2, 3, 4, …, n/2).

Maps can’t have duplicate keys, so by iterating over the map, you’re deduplicating, restoring worst-case O(n).

import "slices"

type void struct{}

func longestConsecutive(nums []int) int {
    max_seq := 0
    numSet := make(map[int]void, len(nums))

    for _, n := range nums {
        numSet[n] = void{}
    }

    slices.Sort(nums)

    for _, n := range nums {
        if _, prev_exists := numSet[n-1]; !prev_exists {
            for i := 1; ; i++ {
                if _, next_exists := numSet[n+i]; !next_exists {
                    max_seq = max(max_seq, i)
                    break
                }
            }
        }
    }
    return max_seq
}

1792 ms

import "slices"

type void struct{}

func longestConsecutive(nums []int) int {
    max_seq := 0
    numSet := make(map[int]void, len(nums))

    for _, n := range nums {
        numSet[n] = void{}
    }

    slices.Sort(nums)

    for i, n := range nums {
        if i > 0 && nums[i - 1] == n {
            continue
        }

        if _, prev_exists := numSet[n-1]; !prev_exists {
            for i := 1; ; i++ {
                if _, next_exists := numSet[n+i]; !next_exists {
                    max_seq = max(max_seq, i)
                    break
                }
            }
        }
    }
    return max_seq
}

82 ms