Arrays & Hashing
An array is a numbered row of boxes. A hash map is a labelled drawer cabinet: give it a key and it hands back the value instantly. Almost every interview problem starts here, because the trick "remember what I have already seen" turns a slow double loop into one fast pass.
After this topic: You can spot when a nested loop can be replaced by one pass plus a map or set, and you can count, group and look things up in O(1).
Step 1 · Read the lesson
Trade memory for speed: look things up in O(1) instead of scanning again.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Contains DuplicateEasy
While scanning, what question do you keep asking about the current number?
Keep a set of numbers seen so far. If the current number is already in the set, return true; otherwise add it.
Target: O(n) time, O(n) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func containsDuplicate(nums []int) boolWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// ContainsDuplicate: does any value appear at least twice? // A map used as a set: struct{} stores nothing but membership. func ContainsDuplicate(nums []int) bool { seen := map[int]struct{}{} for _, v := range nums { if _, ok := seen[v]; ok { return true } seen[v] = struct{}{} } return false } - 2.Valid AnagramEasy
Two words are anagrams when every letter appears the same number of times.
Count letters of the first word, subtract for the second, and check that every count is zero (or compare two count arrays of size 26).
Target: O(n) time, O(1) space for lowercase letters
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func isAnagram(s string, t string) boolWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// IsAnagram: same letters, same counts. Count up for s, down for t. func IsAnagram(s, t string) bool { if len(s) != len(t) { return false } var count [26]int for i := 0; i < len(s); i++ { count[s[i]-'a']++ count[t[i]-'a']-- } for _, c := range count { if c != 0 { return false } } return true } - 3.Two SumEasy
For each number x, which exact value would complete the pair? Can you find it without scanning again?
Walk the array; for each x look up target−x in a map of value→index; if missing, store x with its index.
Target: O(n) time, O(n) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func twoSum(nums []int, target int) []intWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// TwoSum: indices of the two numbers that add up to target. // Remember each value's index; the complement is what we look up. func TwoSum(nums []int, target int) []int { seen := map[int]int{} for i, v := range nums { if j, ok := seen[target-v]; ok { return []int{j, i} } seen[v] = i } return nil } - 4.Group AnagramsMedium
You need a label that is identical for all words that are anagrams of each other.
Build a key per word (its letters sorted, or its 26 letter counts) and append the word to a map from key to list.
Target: O(n·k) time with count keys (k = word length)
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func groupAnagrams(strs []string) [][]stringWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// GroupAnagrams: words with the same letter counts share a key. func GroupAnagrams(words []string) [][]string { groups := map[[26]int][]string{} // arrays are comparable, so they can be keys for _, w := range words { var key [26]int for i := 0; i < len(w); i++ { key[w[i]-'a']++ } groups[key] = append(groups[key], w) } out := make([][]string, 0, len(groups)) for _, g := range groups { out = append(out, g) } return out } - 5.Top K Frequent ElementsMedium
First count, then think about how to pick the biggest counts without a full sort.
Count with a map, then bucket numbers by frequency (index = count) and read buckets from the highest frequency down until you have k.
Target: O(n) time, O(n) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func topKFrequent(nums []int, k int) []intWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// TopKFrequent: count first, then pick the k most frequent values. func TopKFrequent(nums []int, k int) []int { freq := map[int]int{} for _, v := range nums { freq[v]++ } keys := make([]int, 0, len(freq)) for v := range freq { keys = append(keys, v) } sort.Slice(keys, func(a, b int) bool { if freq[keys[a]] != freq[keys[b]] { return freq[keys[a]] > freq[keys[b]] } return keys[a] < keys[b] }) if k > len(keys) { k = len(keys) } return keys[:k] } - 6.Encode and Decode StringsMedium
Any separator character could also appear inside a word. How can the decoder know where a word ends?
Prefix each word with its length and a delimiter, like "5#hello". When decoding, read the number, skip the delimiter, then take exactly that many characters.
Target: O(total characters) time and space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
type Codec struct{} func (c *Codec) Encode(strs []string) string func (c *Codec) Decode(s string) []stringWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare.
// Encode writes each word as "<length>#<word>". The length tells the decoder exactly where the word ends, // so the word itself may contain any character, including "#" and digits. func Encode(strs []string) string { var sb strings.Builder for _, s := range strs { sb.WriteString(strconv.Itoa(len(s))) sb.WriteByte('#') sb.WriteString(s) } return sb.String() } func Decode(s string) []string { out := []string{} for i := 0; i < len(s); { j := i for s[j] != '#' { j++ // read the length digits up to the first '#' } n, _ := strconv.Atoi(s[i:j]) out = append(out, s[j+1:j+1+n]) i = j + 1 + n } return out } - 7.Product of Array Except SelfMedium
Division is not allowed. The product of everything else = (everything to the left) × (everything to the right).
Pass 1 left→right stores the running product of the left side in the result; pass 2 right→left multiplies in a running product of the right side.
Target: O(n) time, O(1) extra space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func productExceptSelf(nums []int) []intWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare. It is explained step by step on the Arrays & Hash Map lesson page.
// ProductExceptSelf: out[i] = product of every element except nums[i], no division. // A prefix PRODUCT from the left, then a suffix product from the right. func ProductExceptSelf(nums []int) []int { out := make([]int, len(nums)) run := 1 for i := range nums { out[i] = run // product of everything left of i run *= nums[i] } run = 1 for i := len(nums) - 1; i >= 0; i-- { out[i] *= run // multiply by everything right of i run *= nums[i] } return out } - 8.Valid SudokuMedium
Which three "places" must each digit be unique in? How do you name the 3×3 box a cell belongs to?
Keep sets for every row, column and box. The box id of (r,c) is (r/3, c/3). If a digit is already in any of its three sets, the board is invalid.
Target: O(81) = O(1) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func isValidSudoku(board [][]byte) boolWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare.
// IsValidSudoku: a digit may appear once per row, once per column and once per 3x3 box. func IsValidSudoku(board [][]byte) bool { var rows, cols, boxes [9][9]bool for r := 0; r < 9; r++ { for c := 0; c < 9; c++ { if board[r][c] == '.' { continue } d := board[r][c] - '1' b := (r/3)*3 + c/3 // box number 0..8 if rows[r][d] || cols[c][d] || boxes[b][d] { return false } rows[r][d], cols[c][d], boxes[b][d] = true, true, true } } return true } - 9.Longest Consecutive SequenceMedium
Sorting costs O(n log n). Which numbers are the only ones worth starting a run from?
Put all numbers in a set. Only start counting at a number whose predecessor (x−1) is NOT in the set, then walk x+1, x+2… while present.
Target: O(n) time, O(n) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func longestConsecutive(nums []int) intWrite Go. Common packages like
fmtandsortare imported for you. Keep the function name and inputs the same.Tested with go test. Try it yourself first, then compare.
// LongestConsecutive: only start counting at the beginning of a run (x-1 is absent), so every number is // visited a constant number of times and the whole thing is O(n). func LongestConsecutive(nums []int) int { set := make(map[int]bool, len(nums)) for _, n := range nums { set[n] = true } best := 0 for n := range set { if set[n-1] { continue // not the start of a run } length := 1 for set[n+length] { length++ } best = max(best, length) } return best }