Go Leetcode: Array & Hash Table

tags: leetcode go

Contains Duplicate

#1

func containsDuplicate(nums []int) bool {
    // hash table
    // key -> value
    // if value > 1 return true
    idmap := make(map[int]int)
    
    // iterate through the given slice
    for i:=0; i < len(nums); i++ {
        idmap[nums[i]]++
        if idmap[nums[i]] > 1 {return true}
    }
    return false
}

#2 less memory

func containsDuplicate(nums []int) bool {
    // struct comsumes less memory than integer and bool
    idmap := make(map[int]struct{})
    
    // iterate through the given slice
    for _, v := range nums {
        if _, ok := idmap[v]; ok {
            return true
        } else {
            idmap[v] = struct{}{} // weird syntax
        }
    }
    return false
}

Note

• what is slice
• how to iterate through slice
• how to declare map
• how to assign empty struct
• consider what type to use

Valid Anagram

#1

func isAnagram(s string, t string) bool {
    
    if len(s) != len(t) {return false}
    
    hst := make(map[rune]int)
    for _, r := range s {
        hst[r]++ // init
    }
    for _, r := range t {
        if _, ok := hst[r]; ok {
            hst[r]--
            if hst[r] < 0 {return false}
        } else {
            return false
        }
    }
    return true
}

Note

• what is rune
• how to iterate through string

Two Sum

#1

func twoSum(nums []int, target int) []int {
    hst := make(map[int]int)
    
    for i, v := range nums {
        to_find := target - v
        // find if the other piece in hash table
        if j, ok := hst[to_find]; ok {
            return []int{i, j}
        } else {
            // add self to hash table
            hst[v] = i
        }
    }
    return []int{0, 0}
}

Group Anagrams

#1

import (
    "sort"
    "fmt"
)

func groupAnagrams(strs []string) [][]string {
    // hash each word
    hst := make(map[string][]string)
    
    for _, str := range strs {
        bytes := []byte(str)
        sort.SliceStable(bytes, func(i int, j int) bool{
            return bytes[i] < bytes[j]
        })
        key := string(bytes)
        hst[key] = append(hst[key], str)
    } 
    
    res := make([][]string, 0, len(hst))
    for _, v := range hst {
        res = append(res, v)
    }
    return res
}

Top K Frequent Elements

#1

func topKFrequent(nums []int, k int) []int {
    // hash table
    // key: num
    // value: counter
    hst := make(map[int]int)
    for _, n := range nums {
        hst[n]++
    }

    // get the indexes of k max value
    // get the index of maximum value k times
    q := []int{}
    for i:=0; i<k; i++ {
        max_idx := 0
        is_init := true
        for key, val := range hst {
            if is_init || hst[max_idx] < val {
                max_idx = key
            }
            is_init = false
        }
        // append
        q = append(q, max_idx)
        // remove from hst
        delete(hst, max_idx)
    }
    return q
}

#2 custom map struct

faster but takes more mrmory

import "sort"

type Pair struct {
    Key int
    Value int
}

type PairList []Pair

func (p PairList) Len() int { return len(p) }
func (p PairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p PairList) Less(i, j int) bool { return p[i].Value > p[j].Value } // sort desc

func topKFrequent(nums []int, k int) []int {
    // hash table
    // key: num
    // value: counter
    hst := make(map[int]int)
    for _, n := range nums {
        hst[n]++
    }
    
    plist := make(PairList, len(hst))
    i := 0
    for k, v := range hst {
        plist[i].Key = k
        plist[i].Value = v
        i++
    }
    sort.Sort(plist)

    // get the indexes of k max value
    // get the index of maximum value k times
    q := []int{}
    for i:=0; i<k; i++ {
        // append
        q = append(q, plist[i].Key)
    }
    return q
}

#3 faster than #2

// ...
q := []int{}
for _, item := range plist[:k] {
    // append
    q = append(q, item.Key)
}
return q

#4 cleaner way to sort

func topKFrequent(nums []int, k int) []int {
    // key : value -> num : amount
    hst := make(map[int]int)
    for _, n := range nums {
        hst[n]++
    }
    
    // collect keys
    keys := []int{}
    for num, _ := range hst {
        keys = append(keys, num)
    }

    // sort keys by values in hash table
    sort.Slice(keys, func(i, j int) bool {
        return hst[keys[i]] > hst[keys[j]] // desc
    })
    
    return keys[:k]
}

#5 use slice of slice as bucket

use slice of slice as bucket to collect nums

func topKFrequent(nums []int, k int) []int {
    // special case
    if len(nums) == k { return nums }
    
    // frequency map
    freqs := map[int]int{}
    for _, num := range nums {
        freqs[num]++
    }
    
    // frequency as index
    // collect numbers with same frequency
    nums_len := len(nums)
    bucket := make([][]int, nums_len+1) // index: 0, 1 ... len(nums)
    for num, freq := range freqs {
        bucket[freq] = append(bucket[freq], num)
    }
    
    res := []int{}
    for i:=nums_len; i>0; i-- {
        if len(bucket[i]) > 0 {
            res = append(res, bucket[i]...)
            if len(res) >= k { return res }
        }
    }
    return res
}

#6 manual quick sort (most complicated)

func topKFrequent(nums []int, k int) []int {
    // special case
    if len(nums) == k { return nums }
    
    // frequency map
    freqs := map[int]int{}
    for _, num := range nums {
        freqs[num]++
    }
    
    keys := []int{}
    for key, _ := range freqs {
        keys = append(keys, key)
    }
    
    // quick sort
    kQuickSort(keys, freqs, k)
    
    return keys[len(keys)-k:]
}

func kQuickSort(slice []int, m map[int]int, k int) {
    if len(slice) <= 1 { return }
    
    kQuickSortRecr(slice, m , 0, len(slice)-1, k)
}

func kQuickSortRecr(slice []int, m map[int]int, start_i, end_i, k int) {
    // end condition
    if start_i >= end_i { return }
    
    // main logic
    piv_i := getPiv(start_i, end_i)
    piv_final := sort(slice, m, start_i, end_i, piv_i)
    
    // divide - DFS right first
    kQuickSortRecr(slice, m, piv_final+1, end_i, k) // right
    if len(slice) - 1 == piv_final + k { return }
    kQuickSortRecr(slice, m, start_i, piv_final-1, k) // left
}

func getPiv(l, r int) int {
    return l + (r - l) / 2
}

func sort(slice []int, m map[int]int, start_i, end_i, piv_i int) int {
    swap(slice, piv_i, end_i)
    curr_piv_i := end_i
    for true {
        for true {
            if start_i == end_i { break }
            if m[slice[start_i]] > m[slice[curr_piv_i]] {
                break
            }
            start_i++
        }
        
        for true {
            if start_i == end_i { break }
            if m[slice[end_i]] < m[slice[curr_piv_i]] {
                break
            }
            end_i--
        }
        
        if start_i == end_i { break }
        swap(slice, end_i, start_i)
    }
    if m[slice[start_i]] >= m[slice[curr_piv_i]] {
        swap(slice, start_i, curr_piv_i)
        curr_piv_i = start_i
    }
    return curr_piv_i
}

func swap(slice []int, i, j int) {
    slice[i], slice[j] = slice[j], slice[i]
}

Note

• how to use sort
• sorting of map by key or value

Product of Array Except Self

solution: https://www.cnblogs.com/grandyang/p/4650187.html

func productExceptSelf(nums []int) []int {
    length := len(nums)
    res := make([]int, length)
    
    // forward
    res[0] = 1
    for i:=1; i < len(nums); i++ {
        res[i] = res[i-1] * nums[i-1]
    }
    // backward
    right := nums[length-1]
    for i:=length-2; i >= 0; i-- {
        res[i] *= right
        right *= nums[i]
    }

    return res
}

Encode & Decode Strings

solution: https://www.youtube.com/watch?v=B1k_sxOSgv8

package main

import (
	"fmt"
	"strconv"
)

const SEP string = ":"

func main() {
	list := []string{"#set", "666", "rat"}
	enco := encode(list)
	fmt.Println(enco)
	fmt.Println(decode(enco))
}

func encode(list []string) string {
	str := ""
	for _, w := range list {
		str += fmt.Sprintf("%d%s%s", len(w), SEP, w)
	}
	return str
}

func decode(str string) []string {
	list, i := []string{}, 0

	for i < len(str) {
		sep_i := i
		// find seperator
		for ; sep_i < len(str); sep_i++ {
			if str[sep_i] == SEP[0] {
				break
			}
		}
		// get word length
		length_str := str[i:sep_i]
		length, err := strconv.Atoi(length_str)
		if err != nil {
			panic("err")
		}

		list = append(list, str[sep_i+1:sep_i+1+length])
		i = sep_i + 1 + length
	}

	return list
}

Note

• efficient details of string append

Longest Consecutive

find start and end of sequences

func longestConsecutive(nums []int) int {
    set := make(map[int]struct{})
    for _, n := range nums {
        if _, ok := set[n]; !ok {
            set[n] = struct{}{}
        }
    }
    res := 0
    for _, n := range nums {
        // if not start number, continue
        if _, ok := set[n-1]; ok {
            continue
        }
        // else n is a start number
        end := n
        for {
            // no next, means end
            if _, ok := set[end+1]; !ok {
                break
            }
            end++
        }
        res = max(res, end-n+1)
    }
    return res
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

Union Find

type UnionFind struct {
    Roots map[int]int
    Lengths map[int]int
}

func (this *UnionFind) Union (a, b int) {
    root_a := this.FindRoot(a)
    root_b := this.FindRoot(b)
    if root_a != root_b {
        this.Roots[root_a] = root_b
        this.Lengths[root_b] += this.Lengths[root_a]
    }
}

func (this *UnionFind) FindRoot (a int) int {
    root := this.Roots[a]
    if root == a { return a }
    this.Roots[a] = this.FindRoot(root)
    return this.Roots[a]
}

func createUnionFind(nums []int) *UnionFind {
    roots, lengths := make(map[int]int), make(map[int]int)
    for _, n := range nums {
        roots[n] = n
        lengths[n] = 1
    }
    return &UnionFind{roots, lengths}
}

func longestConsecutive(nums []int) int {
    uf := createUnionFind(nums)
    longest := 0
    for _, n := range nums {
        if _, ok := uf.Roots[n-1]; ok {
            uf.Union(n, n-1)
        }
        if _, ok := uf.Roots[n+1]; ok {
            uf.Union(n, n+1)
        }
        // length := uf.Lengths[uf.FindRoot(n)]
        longest = max(longest, uf.Lengths[uf.FindRoot(n)])
    }
    return longest
}

func max(a, b int) int {
    if a>b { return a }
    return b
}

Simliar to unionfind but faster!

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    max := 0
    bk := make(map[int]int)
    for _, num := range nums {
        if _, ok := bk[num]; ok {
            continue
        }
        left, right := 0, 0
        if val, ok := bk[num-1]; ok {
            left = val
        }
        if val, ok := bk[num+1]; ok {
            right = val
        }
        bk[num] = left + right + 1
        
        if max < bk[num] {
            max = bk[num]
        }
        
        bk[num-left] = bk[num]
        bk[num+right] = bk[num]
    }
    return max
}

Valid Sudoku

#1

func isValidSudoku(board [][]byte) bool {

    for i:=0; i<9; i++ {
        // validate rows
        if !validSlice(board[i]) {
            return false
        }
        
        // validate cols
        buk := make([]byte, 9)
        for j:=0; j<9; j++ {
            buk[j] = board[j][i]
        }
        if !validSlice(buk) {
            return false
        }
    }
    // validate square
    r_i, c_i := 0, 0
    for r_i < 9 {
        buk := []byte{}

        for _, row := range board[r_i:r_i+3] {   
            for _, num := range row[c_i:c_i+3] {
                buk = append(buk, num)
            }
        }

        if !validSlice(buk) { return false }
        if c_i == 6 {
            c_i = 0
            r_i += 3
        } else {
            c_i += 3
        }
    }
    
    return true
}

func validSlice(s []byte) bool {
    hst := make(map[byte]struct{})
    for _, num := range s {
        if string(num) == "." { continue }
        if _, ok := hst[num]; ok {
            return false
        } else {
            hst[num] = struct{}{}
        }
    }
    return true
}