Hot100 (Go): Three Hash Table Problems

A note on the approaches and Go implementations for three hash-table problems in LeetCode Hot100. The original screenshots are kept as a study record; the grouping tests below already include order normalization; for a standalone input/output version, see the ACM version.

Hashing

1. Two Sum

When the iteration reaches the current number, first look for its complement, target-num, in the map, and return if it is found. The current number must be added to the map after the lookup, to avoid using the same index twice. For example, with [3, 3], the second 3 can find the earlier 3, and the result is [0, 1].

Counting on average O(1) map lookups, this takes O(n) time and O(n) extra space. The original problem guarantees one answer; the code below returns nil when no answer is found.

Solution

package main

import (
	"fmt"
	"reflect"
)

func twoSum(nums []int, target int) (ans []int) {
	mp := map[int]int{}

	for idx, num := range nums {
		if i, ok := mp[target-num]; ok {
			return []int{i, idx}
		}
		mp[num] = idx
	}

	return ans
}

func main() {
	testCases := []struct {
		nums   []int
		target int
		ans    []int
	}{
		{nums: []int{2, 7, 11, 15}, target: 9, ans: []int{0, 1}},
		{nums: []int{3, 2, 4}, target: 6, ans: []int{1, 2}},
		{nums: []int{3, 3}, target: 6, ans: []int{0, 1}},
	}

	for _, t := range testCases {
		fmt.Println(reflect.DeepEqual(twoSum(t.nums, t.target), t.ans))
	}
}

49. Group Anagrams

Sort the bytes of each word: words made up of the same letters then get the same key, and are grouped by that key. This follows the original problem’s scope of lowercase English letters, so sorting bytes is sufficient; this handling cannot be taken directly as a rule for arbitrary Unicode words.

With L as the maximum word length, grouping takes O(nL log L) time on average, and the extra space holds the grouping results. Go does not guarantee map iteration order, and the problem allows the groups in any order, so before comparing, sort each group and the outer list of groups separately; a direct DeepEqual may mark a correct result as false.

Solution

package main

import (
	"fmt"
	"reflect"
	"slices"
)

func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}

	for _, str := range strs {
		s := []byte(str)
		slices.Sort(s)
		mp[string(s)] = append(mp[string(s)], str)
	}

	ans := make([][]string, 0, len(mp))

	for i := range mp {
		ans = append(ans, mp[i])
	}

	return ans
}

func main() {
	testCases := []struct {
		strs []string
		ans  [][]string
	}{
		{
			[]string{"eat", "tea", "tan", "ate", "nat", "bat"},
			[][]string{
				{"eat", "tea", "ate"},
				{"tan", "nat"},
				{"bat"},
			},
		},
		{
			[]string{""},
			[][]string{
				{""},
			},
		},
		{
			[]string{"a"},
			[][]string{
				{"a"},
			},
		},
	}

	for _, t := range testCases {
		got := groupAnagrams(t.strs)
		for _, group := range got {
			slices.Sort(group)
		}
		for _, group := range t.ans {
			slices.Sort(group)
		}
		less := func(a, b []string) int { return slices.Compare(a, b) }
		slices.SortFunc(got, less)
		slices.SortFunc(t.ans, less)
		fmt.Println(reflect.DeepEqual(got, t.ans))
	}
}

128. Longest Consecutive Sequence

First use a set to remove duplicate elements. Only when x-1 does not exist do we take x as the start of a consecutive run and count forward. Otherwise every number would rescan a run, which easily becomes duplicated work.

Each run is expanded only from its start, taking O(n) time on average and O(n) extra space. An empty array returns 0; duplicates cannot increase the length, and negative numbers can also form consecutive runs.

Solution

package main

import "fmt"

func longestConsecutive(nums []int) int {
	ans := 0
	mp := map[int]bool{}

	for _, num := range nums {
		mp[num] = true
	}

	for i := range mp {
		if mp[i-1] == true {
			continue
		}
		cnt := 1

		for mp[i+1] == true {
			i += 1
			cnt += 1
		}

		ans = max(ans, cnt)
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		ans  int
	}{
		{[]int{100, 4, 200, 1, 3, 2}, 4},
		{[]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}, 9},
		{[]int{1, 0, 1, 2}, 3},
	}

	for _, t := range testCases {
		fmt.Println(longestConsecutive(t.nums) == t.ans)
	}
}

References

Original problems and input ranges: Two Sum, Group Anagrams, Longest Consecutive Sequence. For map iteration rules, see the Go language specification.