Arrays and Hashing
This article will run through various LeetCode questions where arrays and hashing can provide an optimal solution.
Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
type void struct{}
func containsDuplicate(nums []int) bool {
if len(nums) <= 1 {
return false
}
duplicates := make(map[int]void)
for _, i := range nums {
if _, ok := duplicates[i]; ok {
return true
}
duplicates[i] = void{}
}
return false
}
Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
func isAnagram(s string, t string) bool {
// ensure lengths are the same
if len(s) != len(t){
return false
}
// determine the frequency of letters, (char - 'a') where a is of type rune will
// output the offset from the unicode character a which will fall in [0, 25]
freq := [26]int{}
for , char := range s {
freq[char - 'a']++
freq[char - 'a']--
}
// if any value in the array is not 0, we can determine that the two strings are not an anagram
for _, val := range freq {
if val != 0 {
return false
}
}
return true
}
Things to note:
-
As the problem only states lowercase English letters as input, we can define the array with a length of 26 letters in the alphabet.
-
A string in go is a read-only slice of bytes. This means that if we would like to modify the string, we would have to either convert it as a byte slice and then update or use string indexing:
-
// 1) greeting := "hallo" // greeting[1] = 'e' is not allowed byteSlice := []byte(greeting) byteSlice[1] = 'e' modifiedGreeting := string(byteSlice) // 2) greeting := "hallo" modifiedGreeting := greeting[:1] + "e" + greeting[2:] ```
-
-
The distinctions between
rune
andbyte
:-
s := "abc" for idx, char := range s { fmt.Println(reflect.TypeOf(char), reflect.TypeOf(s[idx])) } // char: int32 (rune) - Represents a Unicode code point // s[idx]: uint8 - Represents a byte in the UTF-8 encoded string
-
Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for idx, num := range nums {
if val, found := m[target - num]; found {
return []int{val, idx}
}
m[num] = idx
}
return nil
}
Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
func groupAnagrams(strs []string) [][]string {
frequencies := map[[26]int][]string{}
// generate frequencies for all anagrams
for _, str := range strs {
frequency := [26]int{}
for _, char := range str {
frequency[char - 'a']++
}
frequencies[frequency] = append(frequencies[frequency], str)
}
res := make([][]string, len(frequencies))
idx := 0
for _, anagrams := range frequencies {
res[idx] = anagrams
idx++
}
return res
}
Things to note:
- In golang, the only keys that cannot be used in a map are functions, maps, and slices. So we can use a frequency array list as the key to the map and values will be a slice of strings that map to that frequency.
Top K Frequent Elements
func topKFrequent(nums []int, k int) (res []int) {
// map[1:3 2:2 3:1]
frequency := map[int]int{}
for _, num := range nums {
frequency[num]++
}
// map[1:[3] 2:[2] 3:[1]]
buckets := map[int][]int{}
for key, val := range frequency {
buckets[val] = append(buckets[val], key)
}
// [1,2]
for i := len(nums); i >= 1; i-- {
for _, elem := range buckets[i] {
res = append(res, elem)
if len(res) == k {
return res
}
}
}
return res
}
Things to note:
- Here is the general strategy:
- Create a frequency map, containing the occurences of each value. We now need a way to determine the k most occurences.
- Bucket the occurences. So 1 occured 3 times would translate to
3:[1]
with the resulting map being:map[1:[3] 2:[2] 3:[1]]
- We know that in the most extreme case, for a given input array of length 5 all with the same value, the resulting bucket would like
map[5:[val]]
meaning that the largest possible bucket key is the length of the input array. - With the above point in mind, we can iterate top down starting from the length of the input array. We append to res, and if the length of res matches k, we return.
Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
func productExceptSelf(nums []int) []int {
result := make([]int, len(nums))
prefix := 1
for idx, num := range nums {
result[idx] = prefix
prefix *= num
}
postfix := 1
for idx := len(nums) - 1; idx >= 0; idx-- {
result[idx] *= postfix
postfix *= nums[idx]
}
return result
}
Solution:
For a given array [1,2,3,4], the easiest way to determine the product except itself is to calculate the product to the left of its index multiplied by the product to the right.
For instance with index 2, value 3: [1,2,3,4] the result for this index would be (1*2)*(4) = 8
.
- As we iterate through the array, we can calculate the product on the left side. So for input [1,2,3,4], the result array would be [1,1,2,6].
- We can then do the same for the left side. So the starting result array [1,1,2,6] would result in [24,12,8,6] Things to note:
Things to note:
- The easiest approach would be to iterate over the array, calculating the total product of the array. We would then divide by each index to solve the problem, but we cannot use the division operator.
Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
func isValidSudoku(board [][]byte) bool {
vals := map[string]bool{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if string(board[i][j]) == "." {
continue
}
digit := board[i][j]
row := fmt.Sprintf("row:%d:%c", i, digit)
col := fmt.Sprintf("col:%d:%c", j, digit)
grid := fmt.Sprintf("grid:%d/%d:%c", i/3, j/3, digit)
if vals[row] || vals[col] || vals[grid] {
return false
}
vals[row], vals[col], vals[grid] = true, true, true
}
}
return true
}
Things to note:
- A map is extremely useful for this question. As we iterate over the sudoku board, we need to keep track of 3 things:
- Is this a unique digit in this row / cell / grid?
- We can define unique keys for each of these constraints. If any key already exists, we know its an invalid board, otherwise set the key.
Encode and Decode Strings
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
package main
import (
"fmt"
"strconv"
"strings"
)
type Encoder struct {
builder strings.Builder
delimitter rune
}
func NewEncoder() *Encoder {
return &Encoder{
builder: strings.Builder{},
delimitter: '$',
}
}
func (e *Encoder) Encode(input []string) string {
defer e.builder.Reset()
for _, word := range input {
fmt.Fprintf(&e.builder, "%d%c%s", len(word), e.delimitter, word)
}
return e.builder.String()
}
type Decoder struct {
delimitter rune
}
func NewDecoder() *Decoder {
return &Decoder{
delimitter: '$',
}
}
func (d *Decoder) Decode(input string) []string {
res := []string{}
start, current := 0, 0
for current < len(input) {
if rune(input[current]) == d.delimitter {
wordLength, err := strconv.Atoi(input[start:current])
if err != nil {
panic(err)
}
word := input[current+1 : current+1+wordLength]
res = append(res, word)
current += wordLength + 1
start += current
}
current++
}
return res
}
func encode(input []string) string {
encoder := NewEncoder()
return encoder.Encode(input)
}
func decode(input string) []string {
decoder := NewDecoder()
return decoder.Decode(input)
}
func main() {
fmt.Println(encode([]string{"hello", "world"}))
fmt.Println(decode("5$hello5$world"))
}
Things to note:
- Encode leverages strings.Builder from the golang standard library to write the length of each string, a delimitter, and the string itself for each word as the result.
- Decode parses through the string, reaching the delimitter each time to determine the length of the word to write to the result slice.
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
func longestConsecutive(nums []int) int {
res := 0
// create a set of all values
elems := map[int]bool{}
for _, num := range nums {
elems[num] = true
}
// Check if num is the start of the sequence and update sequence count if next value exists
for num, _ := range elems {
exists := elems[num - 1]
if exists {
continue
}
count := 1
for elems[num] {
res = max(res, count)
count++
num++
}
}
return res
}
Things to note:
- When given an input array
[100,4,200,1,3,2]
, its best to bucket each sequence to understand how to go about this problem. There is[1,2,3,4]
,[100]
,[200]
- The trick here is that for each bucket, we can understand that there is no value before the first number. So by creating the set of all values, we can then iterate over them to determine if there a value that exists before it. If there isn't, then we know its the start of the sequence and we can increment until we reach the end of the sequence.
Here's a complete rundown of some LC questions in golang where using Arrays and Hashing can provide an optimal solution.
Hope this helps! :)