{"title":"Go Crash Course for DSA","description":null,"content":"This chapter is a focused crash course on the Go features that come up repeatedly in DSA and coding interview preparation. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.\n\n---\n\n# Common Imports\n\nOn LeetCode, your `package main` is set up for you and most standard library packages are available. You only need to import what your solution uses. Here are the packages that cover almost every DSA problem:\n\n\n```go\nimport (\n \"fmt\" // Formatted I/O (rarely needed on LeetCode)\n \"sort\" // sort.Ints, sort.Slice, sort.Search\n \"strings\" // Builder, Split, Join, Contains, Index\n \"strconv\" // Atoi, Itoa, ParseInt\n \"math\" // MaxInt, MinInt, Abs, Pow, Sqrt\n \"math/bits\" // OnesCount, LeadingZeros, TrailingZeros\n \"container/heap\" // Heap interface for priority queues\n \"container/list\" // Doubly linked list (rarely needed)\n)\n```\n\n\nMost DSA solutions need only three or four packages. Unused imports are compile errors in Go, so remove anything you do not use. Goimports and gofmt handle this automatically in a real editor, but on LeetCode you have to manage it by hand.\n\n---\n\n# Variables, Types, and the Overflow Trap\n\nGo is a statically typed language with type inference using `:=`. For DSA, a small set of types covers most problems.\n\n\n| Type | Size | Range | DSA Use Case |\n|------|------|-------|--------------|\n| `int` | platform-dependent (almost always 8 bytes on 64-bit) | -9.2 x 10^18 to 9.2 x 10^18 | Default integer for everything |\n| `int32` | 4 bytes | -2.1B to 2.1B | When you need exactly 32 bits |\n| `int64` | 8 bytes | -9.2 x 10^18 to 9.2 x 10^18 | Explicit 64-bit math |\n| `byte` (alias for `uint8`) | 1 byte | 0 to 255 | ASCII characters, raw bytes |\n| `rune` (alias for `int32`) | 4 bytes | -2.1B to 2.1B | Unicode code points |\n| `bool` | 1 byte | `true` / `false` | Visited arrays, flags |\n| `float64` | 8 bytes | ±1.7 x 10^308 | Rarely used, some geometry problems |\n\n\nGo's `int` is platform-dependent, but on every machine that runs LeetCode it is 64-bit. This makes overflow far less common than in many other languages because most DSA problems stay well under 2^63 - 1. Even so, two cases still need care:\n\n1. **Explicit 32-bit math** when a problem specifies a 32-bit result (e.g., LeetCode's \"Reverse Integer\" returns an `int32` value).\n2. **Multiplication that could exceed 2^63** (e.g., two large `int64` values multiplied without modulo).\n\n\n```go\n// Standard variable declarations\nvar n int = 10\nvar name string = \"alice\"\n\n// Short declaration with type inference (most common in function bodies)\nn := 10\nname := \"alice\"\n\n// Multiple assignment\na, b := 1, 2\na, b = b, a // Swap without a temp variable\n\n// Zero values (no need to initialize)\nvar count int // 0\nvar visited bool // false\nvar s string // \"\"\nvar ptr *int // nil\n```\n\n\nThe short declaration `:=` only works inside functions. Package-level variables must use `var`.\n\n**Constants and **`iota` are useful for direction arrays and enum-like values:\n\n\n```go\nconst MOD = 1_000_000_007 // Underscores for readability\n\nconst (\n UP = iota // 0\n RIGHT // 1\n DOWN // 2\n LEFT // 3\n)\n```\n\n\n**Min and Max.** Go 1.21 added built-in `min` and `max` functions that work on any ordered type. For older Go versions or when you want explicit float handling, use `math.Min` and `math.Max` (which only work on `float64`).\n\n\n```go\n// Go 1.21+: built-in generic min/max\nx := min(a, b) // Works on int, float64, string, etc.\ny := max(a, b, c, d) // Variadic\n\n// math package (float64 only)\nm := math.Max(1.5, 2.5)\n```\n\n\n**The **`math`** package** also gives you sentinel constants for \"infinity\" patterns:\n\n\n```go\nmath.MaxInt // Largest int value\nmath.MinInt // Smallest int value\nmath.MaxInt32 // 2^31 - 1\nmath.MaxInt64 // 2^63 - 1\nmath.Inf(1) // +Inf (float64)\nmath.Inf(-1) // -Inf (float64)\n```\n\n\nGo has no ternary operator. The idiomatic replacement is an `if-else` block, or `min`/`max` for the common \"pick the bigger one\" case.\n\n---\n\n# Operators and Control Flow\n\nMost operators in Go work as you would expect, but a few deserve special attention for DSA.\n\n**Modular arithmetic** with `%` appears in hashing, cyclic array problems, and math-heavy questions. Go's `%` can return negative values for negative operands: `-7 % 3` gives `-1`, not `2`. To get a non-negative result, use `((n % m) + m) % m`.\n\nMany problems ask you to return the result \"modulo 10^9 + 7\" to prevent overflow in the output:\n\n\n```go\nconst MOD = 1_000_000_007\n\nresult := (a + b) % MOD\nresult = (a * b) % MOD // Safe on 64-bit int as long as a, b < ~3e9\n```\n\n\n**Integer division** in Go truncates toward zero, not toward negative infinity. This differs from some other languages, so be careful with negative numerators:\n\n\n```go\n7 / 2 // 3\n-7 / 2 // -3 (truncates toward zero)\n7 / -2 // -3\n```\n\n\n**Bitwise operators** appear in subset enumeration, bitmask DP, and bit-tricks problems:\n\n\n| Operator | Meaning | Example |\n|----------|---------|---------|\n| `&` | AND | `n & 1` checks if `n` is odd |\n| `\\|` | OR | `mask \\| (1 << i)` sets bit `i` |\n| `^` | XOR | `a ^ b` flips differing bits |\n| `&^` | AND NOT (bit clear) | `mask &^ (1 << i)` clears bit `i` |\n| `<<` | Left shift | `1 << k` equals `2^k` |\n| `>>` | Right shift | `n >> 1` divides by 2 |\n\n\nKey bitwise operators:\n\n\n```go\n// Set bit i\nmask |= 1 << i\n\n// Clear bit i (Go's &^ operator is unique to Go)\nmask &^= 1 << i\n\n// Toggle bit i\nmask ^= 1 << i\n\n// Check bit i\nif mask&(1<\n\nThe `&^` (AND NOT) operator is specific to Go. `a &^ b` is equivalent to `a & (^b)`, which clears the bits in `a` that are set in `b`. It is convenient for bit clearing.\n\n**Short-circuit evaluation** with `&&` and `||` matters for bounds checking. The right side of the operator is not evaluated if the left side determines the result:\n\n\n```go\n// Safe: bounds check before array access\nif i >= 0 && i < len(arr) && arr[i] == target {\n // ...\n}\n\n// Common pattern in 2D grid traversal\nif r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1 {\n // ...\n}\n```\n\n\n### Control Flow\n\nGo has only one loop keyword: `for`. It serves as while, do-while, and traditional for:\n\n\n```go\n// Classic three-part for\nfor i := 0; i < n; i++ {\n // ...\n}\n\n// While loop\nfor left < right {\n // ...\n}\n\n// Infinite loop (use break to exit)\nfor {\n if done { break }\n // ...\n}\n\n// Range over a slice\nfor i, v := range nums {\n // i is index, v is a copy of the value\n}\n\n// Range over a slice, index only\nfor i := range nums {\n // ...\n}\n\n// Range over a slice, value only (use _ to discard the index)\nfor _, v := range nums {\n // ...\n}\n\n// Range over a map (iteration order is randomized!)\nfor k, v := range m {\n // ...\n}\n\n// Range over a string yields rune values, not bytes\nfor i, r := range s {\n // i is byte index, r is the rune at that position\n}\n```\n\n\nThe `for-range` form copies the value. For large structs this can be expensive. For DSA on primitives like `int` it is fine.\n\n**Map iteration is randomized.** Each pass over a map visits keys in a different order. If you need deterministic iteration, sort the keys first.\n\n**The **`switch`** statement** does not fall through by default and supports expression switches:\n\n\n```go\nswitch c {\ncase '(', '[', '{': // Multiple values per case\n stack = append(stack, c)\ncase ')', ']', '}':\n // ...\ndefault:\n // ...\n}\n\n// Expression switch (cleaner than chained if-else)\nswitch {\ncase x < 0:\n return -1\ncase x == 0:\n return 0\ndefault:\n return 1\n}\n```\n\n\n---\n\n# Functions and Multiple Return Values\n\nGo functions can return multiple values, which is the idiomatic way to signal success or failure without exceptions:\n\n\n```go\n// Returns the index and a boolean indicating \"found\"\nfunc find(nums []int, target int) (int, bool) {\n for i, v := range nums {\n if v == target {\n return i, true\n }\n }\n return -1, false\n}\n\n// Usage\nif idx, ok := find(nums, 5); ok {\n fmt.Println(\"Found at\", idx)\n}\n```\n\n\nThe `value, ok` pattern is everywhere in Go. Map lookups, type assertions, and channel receives all follow it.\n\n**Named return values** can act as documentation and let you use a bare `return`. In DSA they are mostly used for readability:\n\n\n```go\nfunc divmod(a, b int) (quotient, remainder int) {\n quotient = a / b\n remainder = a % b\n return // bare return uses the named values\n}\n```\n\n\n**Variadic functions** accept a variable number of arguments:\n\n\n```go\nfunc sum(nums ...int) int {\n total := 0\n for _, n := range nums {\n total += n\n }\n return total\n}\n\nsum(1, 2, 3) // 6\nsum(arr...) // spread a slice as variadic args\n```\n\n\n### Pass-by-Value Semantics\n\nGo is always **pass-by-value**. Primitives, structs, and arrays are copied. However, **slices, maps, and channels are reference types** internally, so passing them to a function lets the function modify the underlying data:\n\n\n```go\nfunc increment(n int) {\n n++ // Modifies a local copy\n}\n\nfunc incrementSlice(s []int) {\n for i := range s {\n s[i]++ // Modifies the caller's slice\n }\n}\n\nfunc incrementPointer(n *int) {\n *n++ // Modifies through the pointer\n}\n\nx := 5\nincrement(x) // x is still 5\n\nnums := []int{1, 2, 3}\nincrementSlice(nums) // nums becomes [2, 3, 4]\n\nincrementPointer(&x) // x becomes 6\n```\n\n\nThis distinction matters when you write helper functions for DSA. If you want to mutate an integer or a struct from a helper, take a pointer. If you want to mutate a slice's elements, pass the slice directly.\n\n### Closures\n\nFunctions are first-class in Go. Closures capture variables from the enclosing scope by reference:\n\n\n```go\nfunc twoSum(nums []int, target int) []int {\n seen := map[int]int{}\n for i, v := range nums {\n if j, ok := seen[target-v]; ok {\n return []int{j, i}\n }\n seen[v] = i\n }\n return nil\n}\n\n// Recursive helpers as closures are common in DSA\nfunc subsets(nums []int) [][]int {\n var result [][]int\n var dfs func(i int, path []int)\n dfs = func(i int, path []int) {\n if i == len(nums) {\n cp := make([]int, len(path))\n copy(cp, path)\n result = append(result, cp)\n return\n }\n dfs(i+1, path) // skip\n dfs(i+1, append(path, nums[i])) // include\n }\n dfs(0, nil)\n return result\n}\n```\n\n\nThe closure pattern lets a recursive helper share `result`, `nums`, and other state without passing them as parameters. This is the standard Go style for backtracking and DFS in DSA.\n\nThere is a subtle gotcha when capturing loop variables in older Go versions. Before Go 1.22, the loop variable was shared across iterations:\n\n\n```go\n// Go 1.22+: each iteration creates a fresh i. This works as expected.\nfuncs := []func(){}\nfor i := 0; i < 3; i++ {\n funcs = append(funcs, func() { fmt.Println(i) })\n}\n// Calling each func prints 0, 1, 2\n\n// Before Go 1.22: all closures would print 3 because they shared the same i.\n// Defensive fix that works in any version:\nfor i := 0; i < 3; i++ {\n i := i // shadow the loop variable\n funcs = append(funcs, func() { fmt.Println(i) })\n}\n```\n\n\nLeetCode typically runs Go 1.21+, so the modern semantics apply. The `i := i` shadow is still a safe habit if you are unsure.\n\n---\n\n# Slices: Go's Dynamic Array\n\nSlices are the core dynamic-array type in Go. They look like arrays but behave very differently, and the differences are where most Go bugs in DSA come from.\n\nA slice is a **three-word descriptor**: a pointer to an underlying array, a length, and a capacity. Multiple slices can point into the same backing array, which is the source of most slice surprises.\n\n\n```mermaid\nflowchart LR\n SLICE[\"Slice header
{ptr, len=3, cap=5}\"]\n ARR[\"Backing array
[10, 20, 30, 40, 50]\"]\n SLICE -->|ptr| ARR\n\n style SLICE fill:#00ceff,stroke:#000,color:#000\n style ARR fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Creating Slices\n\n\n```go\n// Slice literal\nnums := []int{1, 2, 3, 4, 5}\n\n// Nil slice, idiomatic when you do not know the size\nvar result []int\nresult = append(result, 1)\n\n// Fixed-length slice with zero values\nzeros := make([]int, 5) // [0, 0, 0, 0, 0]\n\n// Fixed-length and capacity (avoids reallocations if you know the upper bound)\nbuf := make([]int, 0, 100) // len=0, cap=100\n\n// 2D slice (slice of slices)\ngrid := make([][]int, rows)\nfor i := range grid {\n grid[i] = make([]int, cols)\n}\n```\n\n\n### Slice Operations\n\n\n```go\nnums := []int{1, 2, 3, 4, 5}\n\nlen(nums) // 5\ncap(nums) // 5 (or more, depending on how the slice was built)\n\nnums[0] // 1\nnums[len(nums)-1] // 5 (last element)\nnums = append(nums, 6) // append a value (returns a new slice header)\nnums = append(nums, 7, 8, 9) // append multiple\n\n// Slice expression: low:high (half-open, like most languages)\nnums[1:4] // [2, 3, 4]\nnums[:3] // [1, 2, 3]\nnums[2:] // [3, 4, 5, ...]\nnums[:] // entire slice (often used to clone via copy)\n```\n\n\n`append`** always returns a new slice header.** You must assign the result back. Forgetting this is a classic bug:\n\n\n```go\n// WRONG: ignores the return value\nappend(nums, 6)\n\n// CORRECT\nnums = append(nums, 6)\n```\n\n\n### The Aliasing Trap\n\nThe key Go gotcha for DSA: **slicing does not copy data**. The new slice shares the same backing array as the original. Mutating one can change the other.\n\n\n```go\nnums := []int{1, 2, 3, 4, 5}\nsub := nums[1:4] // sub shares storage with nums\n\nsub[0] = 99\nfmt.Println(nums) // [1, 99, 3, 4, 5] (the original changed!)\n```\n\n\nThis is especially dangerous in backtracking, where you build up a `path` slice and want to save snapshots of it. If you save the slice directly, every saved entry will be a window into the same backing array:\n\n\n```go\n// WRONG: every entry in result points to the same array\nresult = append(result, path)\n\n// CORRECT: copy the slice contents\ncp := make([]int, len(path))\ncopy(cp, path)\nresult = append(result, cp)\n\n// ALSO CORRECT: append([]int(nil), path...) creates a fresh slice\nresult = append(result, append([]int(nil), path...))\n```\n\n\nThe `append([]int(nil), path...)` idiom is the shortest way to clone a slice in one expression. The `copy` plus `make` version is more explicit.\n\n### The 2D Slice Pitfall\n\nWhen initializing a 2D slice, do not try to share a single inner slice across rows:\n\n\n```go\n// WRONG: every row points to the same inner slice\nrow := make([]int, cols)\ngrid := make([][]int, rows)\nfor i := range grid {\n grid[i] = row // all rows alias the same memory\n}\n\n// CORRECT: allocate each row independently\ngrid := make([][]int, rows)\nfor i := range grid {\n grid[i] = make([]int, cols)\n}\n```\n\n\n### Removing Elements\n\nGo has no built-in delete for slices. You concatenate the two sides:\n\n\n```go\n// Remove element at index i (preserves order, O(n))\nnums = append(nums[:i], nums[i+1:]...)\n\n// Remove element at index i (does NOT preserve order, O(1))\nnums[i] = nums[len(nums)-1]\nnums = nums[:len(nums)-1]\n\n// Remove last (O(1)), standard stack pop\nlast := nums[len(nums)-1]\nnums = nums[:len(nums)-1]\n\n// Remove first (O(n))\nnums = nums[1:] // beware: the backing array still holds the original first element\n```\n\n\nFor DSA stacks, growing and shrinking from the end with `append` and `nums[:len(nums)-1]` gives amortized O(1) operations. This is the standard way to implement a stack in Go.\n\n### Common Slice Operations Reference\n\n\n| Operation | Code | Time | Notes |\n|-----------|------|------|-------|\n| Length | `len(nums)` | O(1) | |\n| Append | `nums = append(nums, x)` | O(1) amortized | Returns new header |\n| Pop last | `nums[len(nums)-1]; nums = nums[:len(nums)-1]` | O(1) | Stack pattern |\n| Reverse in place | `for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 { nums[i], nums[j] = nums[j], nums[i] }` | O(n) | |\n| Clone | `append([]int(nil), nums...)` | O(n) | Independent backing array |\n| Contains | linear scan | O(n) | No built-in helper |\n\n\n---\n\n# Strings and Runes\n\nGo strings are **immutable** sequences of bytes. UTF-8 encoded by convention, but the type itself is just bytes. This dual nature, raw bytes underneath and UTF-8 text by convention, is central to Go string problems.\n\n\n```go\ns := \"hello\"\n\nlen(s) // 5 (bytes, not code points)\ns[0] // 104 (byte value of 'h'), not \"h\"\ns[1:3] // \"el\" (substring is also a string)\n\n// Strings are immutable: s[0] = 'H' is a compile error\n```\n\n\n### Byte vs Rune\n\n`s[i]` returns a `byte` (uint8). This is correct for ASCII strings, which covers most DSA problems. For Unicode, you need runes.\n\n\n```go\ns := \"abc\"\n\n// Iterate as bytes\nfor i := 0; i < len(s); i++ {\n b := s[i] // byte\n // ...\n}\n\n// Iterate as runes (Unicode code points)\nfor i, r := range s {\n // i is byte index, r is rune\n}\n\n// Convert\nbytes := []byte(s) // []byte slice (mutable)\nrunes := []rune(s) // []rune slice (mutable)\n\ns = string(bytes) // back to string\ns = string(runes)\n```\n\n\nFor LeetCode problems, the input is typically ASCII. Use `[]byte` for in-place mutation. Reserve `[]rune` for problems that explicitly mention Unicode.\n\n### Common String Methods\n\n\n| Operation | Code | Returns | Notes |\n|-----------|------|---------|-------|\n| Length | `len(s)` | `int` | Byte length |\n| Character at | `s[i]` | `byte` | Use `[]rune(s)[i]` for Unicode |\n| Substring | `s[i:j]` | `string` | Half-open, O(1) (shares backing memory) |\n| Concatenation | `s + t` | `string` | O(n + m), allocates |\n| Contains | `strings.Contains(s, \"ab\")` | `bool` | |\n| Index of | `strings.Index(s, \"ab\")` | `int` | -1 if not found |\n| Split | `strings.Split(s, \" \")` | `[]string` | Tokenize |\n| Join | `strings.Join(parts, \"-\")` | `string` | |\n| Replace | `strings.ReplaceAll(s, \"a\", \"b\")` | `string` | |\n| Trim | `strings.TrimSpace(s)` | `string` | |\n| Lowercase | `strings.ToLower(s)` | `string` | |\n| Uppercase | `strings.ToUpper(s)` | `string` | |\n| Repeat | `strings.Repeat(\"ab\", 3)` | `string` | \"ababab\" |\n| Prefix check | `strings.HasPrefix(s, \"ab\")` | `bool` | |\n| Suffix check | `strings.HasSuffix(s, \"ab\")` | `bool` | |\n\n\n### Building Strings Efficiently\n\nConcatenating in a loop with `+` is O(n^2) because each `+` allocates a new string. Use `strings.Builder` for O(n) string building:\n\n\n```go\n// BAD: O(n^2) because each += allocates a new string\nresult := \"\"\nfor _, c := range chars {\n result += string(c)\n}\n\n// GOOD: O(n)\nvar sb strings.Builder\nfor _, c := range chars {\n sb.WriteByte(byte(c)) // or sb.WriteRune(c)\n}\nresult := sb.String()\n```\n\n\nFor ASCII-only problems, working directly with a `[]byte` and converting to string at the end is even simpler and often faster:\n\n\n```go\nbuf := make([]byte, 0, len(s))\nfor i := 0; i < len(s); i++ {\n if s[i] != ' ' {\n buf = append(buf, s[i])\n }\n}\nresult := string(buf)\n```\n\n\n### Character Arithmetic\n\nGo's `byte` and `rune` are integer types, so you can do arithmetic directly:\n\n\n```go\n// Map 'a'-'z' to 0-25 (common for frequency arrays)\nidx := s[i] - 'a'\n\n// Convert 0-25 back to 'a'-'z'\nch := byte('a' + idx)\n\n// Digit character to int value\nd := int(s[i] - '0')\n\n// Check character class without a regex\nisLower := s[i] >= 'a' && s[i] <= 'z'\nisDigit := s[i] >= '0' && s[i] <= '9'\n```\n\n\nThis is faster and more memory-efficient than a `map[byte]int` when the character set is limited to lowercase (or uppercase, or digits).\n\n### String to Int Conversion\n\n\n```go\nn, err := strconv.Atoi(\"42\") // 42, nil\nn, err = strconv.Atoi(\"abc\") // 0, error\n\n// In DSA, the error rarely matters; the input is guaranteed to be valid\nn, _ := strconv.Atoi(token)\n\n// Int to string\ns := strconv.Itoa(42) // \"42\"\n\n// Parse with a base\nn, _ = strconv.ParseInt(\"ff\", 16, 64) // 255 (hex)\n```\n\n\n---\n\n# Maps\n\nGo's `map` is a hash map. It appears in most DSA problems alongside slices, providing O(1) average-case lookups, inserts, and deletes.\n\n\n```go\n// Declare and initialize\nfreq := map[string]int{} // empty map\nfreq := make(map[string]int) // same thing\nages := map[string]int{\"alice\": 30, \"bob\": 25}\n\n// Insert or update\nfreq[\"go\"] = 1\nfreq[\"go\"]++ // increment (zero value if missing)\n\n// Lookup\nv := freq[\"go\"] // 1\nv = freq[\"missing\"] // 0 (zero value, no error)\n\n// \"Comma ok\" idiom to distinguish missing from zero\nv, ok := freq[\"go\"] // v=1, ok=true\nv, ok = freq[\"missing\"] // v=0, ok=false\n\n// Delete\ndelete(freq, \"go\")\n\n// Size\nlen(freq)\n```\n\n\nThe zero-value-on-miss behavior is convenient for counters. `freq[key]++` works correctly even when `key` is new. If you need to distinguish \"missing\" from \"present but zero\", use the `value, ok := m[key]` form.\n\n### Frequency Counting\n\nThe most common DSA pattern is counting characters or numbers:\n\n\n```go\nfreq := map[byte]int{}\nfor i := 0; i < len(s); i++ {\n freq[s[i]]++\n}\n\n// For lowercase letters only, a fixed-size array is faster\nvar count [26]int\nfor i := 0; i < len(s); i++ {\n count[s[i]-'a']++\n}\n```\n\n\nThe `[26]int` array is faster than `map[byte]int` when the character set is known and small. It is also simpler to compare two such arrays directly (`count1 == count2`), which is useful for anagram checking.\n\n### Sets in Go\n\nGo has no built-in set type. The idiomatic substitute is `map[T]bool` or `map[T]struct{}`. The `struct{}` version uses zero bytes per entry, which can matter for very large sets:\n\n\n```go\n// Boolean set: clearer, slightly larger\nseen := map[int]bool{}\nseen[42] = true\nif seen[42] { /* ... */ }\n\n// Empty-struct set: zero bytes per entry, slightly less readable\nvisited := map[int]struct{}{}\nvisited[42] = struct{}{}\nif _, ok := visited[42]; ok { /* ... */ }\n```\n\n\nFor most DSA problems, `map[T]bool` is fine and reads more naturally. Save `map[T]struct{}` for problems with tight memory limits.\n\n### Composite Keys\n\nMaps require comparable keys. You can use structs as keys when you need to track a multi-dimensional state (e.g., `(row, col)` in BFS, `(index, remaining)` in DP):\n\n\n```go\ntype Cell struct{ r, c int }\n\nvisited := map[Cell]bool{}\nvisited[Cell{0, 0}] = true\nif visited[Cell{r, c}] { /* ... */ }\n\n// Memoization with multi-key\ntype State struct{ i, remaining int }\nmemo := map[State]int{}\nif v, ok := memo[State{i, k}]; ok {\n return v\n}\n```\n\n\nSlices are not comparable, so you cannot use a `[]int` as a map key. Convert to an array or to a string instead. For fixed-size keys, an array type works:\n\n\n```go\n// [26]int is an array (fixed size), which IS comparable\ngroups := map[[26]int][]string{}\nfor _, word := range words {\n var key [26]int\n for i := 0; i < len(word); i++ {\n key[word[i]-'a']++\n }\n groups[key] = append(groups[key], word)\n}\n```\n\n\nThis is the standard Go idiom for grouping anagrams: the `[26]int` frequency array becomes the map key.\n\n### Map Iteration Is Randomized\n\nIteration order over a Go map is intentionally randomized to discourage code that depends on order. If you need deterministic iteration, collect the keys, sort them, then iterate:\n\n\n```go\nkeys := make([]int, 0, len(m))\nfor k := range m {\n keys = append(keys, k)\n}\nsort.Ints(keys)\nfor _, k := range keys {\n v := m[k]\n // ...\n}\n```\n\n\n---\n\n# Sorting and Comparators\n\nThe `sort` package covers the common DSA needs. Most sorting is done with the convenience helpers `sort.Ints`, `sort.Strings`, and the generic `sort.Slice`.\n\n\n```go\nnums := []int{3, 1, 4, 1, 5, 9, 2, 6}\n\nsort.Ints(nums) // sort ascending in place\nsort.Sort(sort.Reverse(sort.IntSlice(nums))) // descending\nsort.Strings(strs) // sort string slice\nsort.Float64s(floats) // sort float64 slice\n```\n\n\n### Custom Comparators\n\nFor anything more complex, use `sort.Slice` with a `less` function:\n\n\n```go\nintervals := [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}\n\n// Sort by start time\nsort.Slice(intervals, func(i, j int) bool {\n return intervals[i][0] < intervals[j][0]\n})\n\n// Sort by length, descending\nsort.Slice(words, func(i, j int) bool {\n return len(words[i]) > len(words[j])\n})\n\n// Multi-key: by first element ascending, then by second descending\nsort.Slice(pairs, func(i, j int) bool {\n if pairs[i][0] != pairs[j][0] {\n return pairs[i][0] < pairs[j][0]\n }\n return pairs[i][1] > pairs[j][1]\n})\n```\n\n\nThe `less` function returns `true` when element `i` should come **before** element `j`. Given that rule, multi-key sorts become a matter of chaining returns.\n\n`sort.SliceStable` preserves the relative order of equal elements. Use it when ties need to keep input order:\n\n\n```go\nsort.SliceStable(items, func(i, j int) bool {\n return items[i].priority < items[j].priority\n})\n```\n\n\n`sort.Slice` uses introsort with a pattern-defeating optimization and is not guaranteed stable. Use the `Stable` variant whenever stability matters.\n\n### Binary Search\n\n`sort.Search` does a generic binary search over an index range. The trick is that you provide a predicate that is `false` for low indices and `true` for high indices, and it returns the first `true` index:\n\n\n```go\nnums := []int{1, 3, 5, 7, 9, 11}\n\n// lower_bound: first index where nums[i] >= target\ni := sort.Search(len(nums), func(i int) bool {\n return nums[i] >= 5\n})\n// i is 2 (nums[2] = 5)\n\n// upper_bound: first index where nums[i] > target\nj := sort.Search(len(nums), func(i int) bool {\n return nums[i] > 5\n})\n// j is 3 (nums[3] = 7)\n\n// Convenience helpers for sorted []int and []string\nidx := sort.SearchInts(nums, 5) // same as lower_bound\nidx = sort.SearchStrings(strs, \"abc\")\n```\n\n\nIf the target is missing, `sort.Search` returns `len(nums)`. Always check the returned index against the length before accessing the slice.\n\n### Reverse Sort\n\nThere is no `Collections.reverseOrder()` equivalent. Two idioms cover almost every case:\n\n\n```go\n// Flip the comparator\nsort.Slice(nums, func(i, j int) bool {\n return nums[i] > nums[j] // descending\n})\n\n// Sort then reverse (clean for primitive types)\nsort.Ints(nums)\nfor i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {\n nums[i], nums[j] = nums[j], nums[i]\n}\n```\n\n\n---\n\n# The Heap Interface\n\nGo does not have a built-in priority queue. The `container/heap` package provides the algorithm; you write the storage and the comparator.\n\nImplementing a heap takes five methods: `Len`, `Less`, `Swap`, `Push`, and `Pop`. The first three come from `sort.Interface`. The last two grow and shrink the underlying slice.\n\n\n```go\n// Min-heap of ints\ntype IntHeap []int\n\nfunc (h IntHeap) Len() int { return len(h) }\nfunc (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // < for min-heap, > for max-heap\nfunc (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }\nfunc (h *IntHeap) Pop() any {\n old := *h\n n := len(old)\n x := old[n-1]\n *h = old[:n-1]\n return x\n}\n```\n\n\nUse the heap through the `heap.Push` and `heap.Pop` functions (note the package-level functions, not the methods you wrote):\n\n\n```go\nh := &IntHeap{2, 1, 5}\nheap.Init(h) // O(n) heapify\n\nheap.Push(h, 3) // O(log n) insert\ntop := (*h)[0] // O(1) peek at the min\nmin := heap.Pop(h).(int) // O(log n) remove the min (type assertion required)\n```\n\n\nThe `heap.Push` and `heap.Pop` calls handle the sift-up and sift-down. Your `Push` and `Pop` methods just add or remove the last element. Mixing them up is a common bug; always go through the package functions to maintain the heap invariant.\n\n### Max-Heap\n\nTo make a max-heap, flip the comparator:\n\n\n```go\ntype MaxHeap []int\nfunc (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // ONLY change\n// Len, Swap, Push, Pop are identical to IntHeap\n```\n\n\nOr, for a quick fix, push negative values into a min-heap and negate them when popping.\n\n### Heap of Pairs\n\nFor Dijkstra and priority-queue patterns, you usually need to push a `(priority, payload)` pair:\n\n\n```go\ntype Item struct {\n cost, node int\n}\n\ntype PQ []Item\n\nfunc (p PQ) Len() int { return len(p) }\nfunc (p PQ) Less(i, j int) bool { return p[i].cost < p[j].cost }\nfunc (p PQ) Swap(i, j int) { p[i], p[j] = p[j], p[i] }\nfunc (p *PQ) Push(x any) { *p = append(*p, x.(Item)) }\nfunc (p *PQ) Pop() any {\n old := *p\n n := len(old)\n x := old[n-1]\n *p = old[:n-1]\n return x\n}\n\n// Usage in Dijkstra\npq := &PQ{}\nheap.Push(pq, Item{0, source})\nfor pq.Len() > 0 {\n cur := heap.Pop(pq).(Item)\n // ...\n}\n```\n\n\nWriting the heap once and copying the boilerplate per problem is the standard Go workflow. Some people keep a templated implementation handy for interviews.\n\n---\n\n# Nil Handling\n\nGo has no exceptions for null access; instead, dereferencing a `nil` pointer triggers a runtime panic. In DSA, `nil` shows up in tree traversal, linked list traversal, and map lookups.\n\n\n```go\n// Tree traversal: always check before accessing fields\nif node != nil {\n visit(node.Val)\n dfs(node.Left)\n dfs(node.Right)\n}\n\n// Linked list: check before advancing\nfor current != nil {\n // process current\n current = current.Next\n}\n\n// Nil slice is fine for most operations\nvar nums []int // nil slice\nlen(nums) // 0\nnums = append(nums, 1) // works (append handles nil)\nfor _, v := range nums { // works (loops 0 times)\n _ = v\n}\n```\n\n\nA `nil` slice behaves like an empty slice for most read operations. `len`, `range`, and `append` all handle it gracefully. The same is **not** true for maps: a `nil` map can be read from (returns zero values), but writing to it panics.\n\n\n```go\nvar m map[string]int\nv := m[\"key\"] // 0, no panic\nm[\"key\"] = 1 // PANIC: assignment to entry in nil map\n\n// Always initialize a map before writing\nm = map[string]int{}\nm[\"key\"] = 1 // OK\n```\n\n\nThis bites when you build a `map[K]V` by walking input and lazily creating sub-maps:\n\n\n```go\n// Adjacency list with nested maps\ngraph := map[int]map[int]int{}\n\n// WRONG: graph[u] is nil until you create it\ngraph[u][v] = weight // panic if graph[u] is nil\n\n// CORRECT: initialize the inner map first\nif graph[u] == nil {\n graph[u] = map[int]int{}\n}\ngraph[u][v] = weight\n```\n\n\n---\n\n# Iterating and Modifying Collections Safely\n\nModifying a slice or map while iterating over it is a source of subtle bugs. The rules for each container differ.\n\n### Slices\n\nYou can mutate elements of a slice during a `range` loop, but be careful: `range` copies the value. Modifying the copy does not modify the slice:\n\n\n```go\nnums := []int{1, 2, 3}\n\n// WRONG: v is a copy\nfor _, v := range nums {\n v *= 2 // local change, lost after the iteration\n}\n\n// CORRECT: use index\nfor i := range nums {\n nums[i] *= 2\n}\n```\n\n\nAppending to the slice while ranging is well-defined (the loop reads the original length captured at the start), but it usually creates confusing code. Build a new slice instead.\n\nFor in-place filtering, the standard idiom uses a write pointer:\n\n\n```go\n// Remove all zeros, in place\nw := 0\nfor _, v := range nums {\n if v != 0 {\n nums[w] = v\n w++\n }\n}\nnums = nums[:w]\n```\n\n\nThis is the Go version of the classic two-pointer filter from \"Remove Element\" and \"Remove Duplicates from Sorted Array\".\n\n### Maps\n\nYou **can** delete entries from a map during iteration. It is safe and well-defined: the entry will not be visited again. You **cannot** rely on whether a newly added entry will be visited; the spec leaves this implementation-defined.\n\n\n```go\n// Safe: delete during iteration\nfor k, v := range counts {\n if v == 0 {\n delete(counts, k)\n }\n}\n```\n\n\nFor most DSA problems, building a new map or slice is clearer than mutating one during iteration.\n\n---\n\n# Recursion and the Call Stack\n\nRecursion is the natural fit for tree traversal, DFS, backtracking, and divide-and-conquer. Go's default goroutine stack starts small (around 8 KB) and grows on demand, so deep recursion is supported, but stack overflows can still happen for very deep recursion on adversarial input.\n\n\n```go\n// DFS on a binary tree\nfunc maxDepth(root *TreeNode) int {\n if root == nil {\n return 0\n }\n return 1 + max(maxDepth(root.Left), maxDepth(root.Right))\n}\n```\n\n\nGo does **not** optimize tail recursion. A recursive function that does its work in the tail position still consumes a stack frame per call. For problems with potentially very deep recursion (a skewed tree of 10^5 nodes, for example), convert to an iterative solution with an explicit stack:\n\n\n```go\n// Iterative inorder traversal using a slice as a stack\nfunc inorder(root *TreeNode) []int {\n var result []int\n var stack []*TreeNode\n cur := root\n for cur != nil || len(stack) > 0 {\n for cur != nil {\n stack = append(stack, cur)\n cur = cur.Left\n }\n cur = stack[len(stack)-1]\n stack = stack[:len(stack)-1]\n result = append(result, cur.Val)\n cur = cur.Right\n }\n return result\n}\n```\n\n\n### Backtracking Template\n\nThe pattern for backtracking in Go uses a closure to share state with a recursive helper:\n\n\n```go\nfunc permute(nums []int) [][]int {\n var result [][]int\n var path []int\n used := make([]bool, len(nums))\n\n var backtrack func()\n backtrack = func() {\n if len(path) == len(nums) {\n cp := make([]int, len(path))\n copy(cp, path)\n result = append(result, cp)\n return\n }\n for i, v := range nums {\n if used[i] {\n continue\n }\n used[i] = true\n path = append(path, v)\n backtrack()\n path = path[:len(path)-1] // undo\n used[i] = false\n }\n }\n\n backtrack()\n return result\n}\n```\n\n\nThe `cp := make([]int, len(path)); copy(cp, path)` pattern is essential. If you push `path` directly into `result`, every result entry will alias the same backing array, and they will all change as the backtrack unwinds. This is the Go equivalent of the classic backtracking copy bug.\n\n---\n\n# Graph Representation Patterns\n\nGo has no built-in graph type, so you build representations from slices and maps.\n\n### Adjacency List with a Slice\n\nBest when node IDs are dense integers from 0 to n-1:\n\n\n```go\ngraph := make([][]int, n)\nfor _, e := range edges {\n u, v := e[0], e[1]\n graph[u] = append(graph[u], v)\n graph[v] = append(graph[v], u) // omit for directed graphs\n}\n\n// Walk neighbors\nfor _, nb := range graph[node] {\n // ...\n}\n```\n\n\n### Adjacency List with a Map\n\nBest when node IDs are arbitrary (strings, sparse integers):\n\n\n```go\ngraph := map[string][]string{}\nfor _, e := range edges {\n u, v := e[0], e[1]\n graph[u] = append(graph[u], v)\n graph[v] = append(graph[v], u)\n}\n```\n\n\n### Weighted Edges\n\nFor Dijkstra and shortest-path problems, store the weight alongside the neighbor:\n\n\n```go\ntype Edge struct {\n to, weight int\n}\n\ngraph := make([][]Edge, n)\nfor _, e := range edges {\n u, v, w := e[0], e[1], e[2]\n graph[u] = append(graph[u], Edge{v, w})\n graph[v] = append(graph[v], Edge{u, w})\n}\n```\n\n\n### BFS Template\n\n\n```go\nfunc bfs(graph [][]int, start int) []int {\n visited := make([]bool, len(graph))\n queue := []int{start}\n visited[start] = true\n var order []int\n for len(queue) > 0 {\n node := queue[0]\n queue = queue[1:]\n order = append(order, node)\n for _, nb := range graph[node] {\n if !visited[nb] {\n visited[nb] = true\n queue = append(queue, nb)\n }\n }\n }\n return order\n}\n```\n\n\nThe `queue = queue[1:]` pop is O(1) for the slice header update, but the unused element still occupies memory in the underlying array until the next `append` triggers reallocation. For very large BFS, this can matter; use an index-based head pointer instead:\n\n\n```go\nqueue := []int{start}\nfor head := 0; head < len(queue); head++ {\n node := queue[head]\n for _, nb := range graph[node] {\n if !visited[nb] {\n visited[nb] = true\n queue = append(queue, nb)\n }\n }\n}\n```\n\n\nThis avoids the slice-head churn entirely and is faster for large graphs.\n\n---\n\n# Pairs and Tuples\n\nGo has no built-in tuple. The idiomatic replacement is a small `struct` for clarity, or a `[2]int` array when you need two ints.\n\n\n```go\n// Option 1: [2]int for coordinate or edge pairs (most concise, comparable, hashable)\ntype Cell = [2]int // optional alias for readability\npoints := []Cell{{0, 0}, {1, 2}, {3, 4}}\n\n// Option 2: a named struct (clearest intent, supports any field types)\ntype Edge struct {\n from, to, weight int\n}\nedges := []Edge{{0, 1, 5}, {1, 2, 3}}\n\n// Option 3: []int slice (NOT comparable, NOT hashable, use only as values)\nintervals := [][]int{{1, 3}, {2, 6}, {8, 10}}\n```\n\n\nThe `[2]int` array is comparable and hashable, so it can be a map key. A `[]int` slice cannot be a map key because slices are not comparable. Use the array form whenever you need to put a pair into a `map` or `set`.\n\nFor more than two or three values, a named struct beats anonymous types for readability. Names like `Edge`, `State`, and `Step` document intent better than the third element of an array.\n\n---\n\n# Deduplication Patterns\n\nRemoving duplicates is a common DSA subtask. Three patterns cover most cases.\n\n### Sort and Skip\n\nBest for problems where the result must be sorted anyway (3Sum, 4Sum):\n\n\n```go\nsort.Ints(nums)\nfor i := 0; i < len(nums); i++ {\n if i > 0 && nums[i] == nums[i-1] {\n continue // skip duplicate at the same level\n }\n // ...\n}\n```\n\n\nThis runs in O(1) extra space beyond the sort and produces results in sorted order.\n\n### Set-Based Deduplication\n\nBest when input order is preserved or sorting is undesirable:\n\n\n```go\nseen := map[int]bool{}\nvar unique []int\nfor _, v := range nums {\n if !seen[v] {\n seen[v] = true\n unique = append(unique, v)\n }\n}\n```\n\n\n### Deduplicating Slices of Slices\n\nSlices cannot be set keys. Convert each slice to a comparable form (an array or a string) first:\n\n\n```go\n// Deduplicate fixed-length triplets using a [3]int key\nseen := map[[3]int]bool{}\nvar unique [][]int\nfor _, t := range triplets {\n key := [3]int{t[0], t[1], t[2]}\n if !seen[key] {\n seen[key] = true\n unique = append(unique, t)\n }\n}\n```\n\n\n---\n\n# Common DSA Idioms in Go\n\nA short reference of small patterns and utility calls that appear repeatedly across problems.\n\n### Two Pointers\n\n\n```go\nleft, right := 0, len(nums)-1\nfor left < right {\n sum := nums[left] + nums[right]\n switch {\n case sum < target:\n left++\n case sum > target:\n right--\n default:\n return []int{left, right}\n }\n}\n```\n\n\n### Sliding Window\n\n\n```go\nleft := 0\nsum := 0\nbest := 0\nfor right := 0; right < len(nums); right++ {\n sum += nums[right]\n for sum > target {\n sum -= nums[left]\n left++\n }\n best = max(best, right-left+1)\n}\n```\n\n\n### Stack with a Slice\n\n\n```go\nvar stack []int\nstack = append(stack, 1) // push\ntop := stack[len(stack)-1] // peek\nstack = stack[:len(stack)-1] // pop\nisEmpty := len(stack) == 0\n```\n\n\n### Queue with a Slice (and Index Head)\n\n\n```go\nqueue := []int{start}\nfor head := 0; head < len(queue); head++ {\n node := queue[head]\n // ... enqueue neighbors with queue = append(queue, ...)\n}\n```\n\n\n### Direction Arrays for Grid Traversal\n\n\n```go\ndirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}\n\nfor _, d := range dirs {\n nr, nc := r+d[0], c+d[1]\n if nr >= 0 && nr < rows && nc >= 0 && nc < cols {\n // ...\n }\n}\n```\n\n\n### Counting with a Fixed Array\n\n\n```go\nvar count [26]int\nfor i := 0; i < len(s); i++ {\n count[s[i]-'a']++\n}\n```\n\n\n### Abs and Sign\n\n`math.Abs` only works on `float64`. For integers, write your own:\n\n\n```go\nfunc abs(x int) int {\n if x < 0 {\n return -x\n }\n return x\n}\n```\n\n\n### Power of Two Check\n\n\n```go\nisPowerOfTwo := n > 0 && n&(n-1) == 0\n```\n\n\n### Ceiling Division for Positive Integers\n\n\n```go\nceilDiv := (a + b - 1) / b\n```\n\n\n---\n\n# Struct Basics for Design Problems\n\nDSA problems often define custom node types. These definitions appear throughout the course.\n\n\n```go\n// Linked list node\ntype ListNode struct {\n Val int\n Next *ListNode\n}\n\n// Binary tree node\ntype TreeNode struct {\n Val int\n Left, Right *TreeNode\n}\n\n// Graph node with neighbors\ntype Node struct {\n Val int\n Neighbors []*Node\n}\n\n// Trie node\ntype TrieNode struct {\n Children [26]*TrieNode\n IsEnd bool\n}\n```\n\n\nLeetCode provides these definitions for you, so you only need to write your solution function. Fields use capitalized names because Go uses capitalization for visibility, and LeetCode's runners expect the exported form.\n\n### Constructing Nodes\n\nTwo common ways to construct a struct:\n\n\n```go\n// Struct literal (zero values for omitted fields)\nnode := &ListNode{Val: 1} // Next is nil by default\nnode := &ListNode{Val: 1, Next: nil} // explicit\nnode := &ListNode{1, nil} // positional (order matters)\n\n// Constructor function (clearer when there is logic)\nfunc newTrieNode() *TrieNode {\n return &TrieNode{}\n}\n```\n\n\nThe `&T{}` form returns a pointer to a new value. This is the standard way to allocate a struct on the heap in Go. The compiler decides whether the value actually lives on the heap or the stack based on escape analysis, but you do not need to think about that for DSA.\n\n### Methods\n\nGo has no classes. You attach methods to types using a **receiver**:\n\n\n```go\ntype Trie struct {\n root *TrieNode\n}\n\nfunc (t *Trie) Insert(word string) {\n node := t.root\n for i := 0; i < len(word); i++ {\n idx := word[i] - 'a'\n if node.Children[idx] == nil {\n node.Children[idx] = &TrieNode{}\n }\n node = node.Children[idx]\n }\n node.IsEnd = true\n}\n\nfunc (t *Trie) Search(word string) bool {\n node := t.root\n for i := 0; i < len(word); i++ {\n idx := word[i] - 'a'\n if node.Children[idx] == nil {\n return false\n }\n node = node.Children[idx]\n }\n return node.IsEnd\n}\n```\n\n\nUse a **pointer receiver** (`*Trie`) when the method modifies the receiver or when the type is large enough that copying it would be wasteful. For DSA, pointer receivers are almost always the right choice on struct types.\n\n### LeetCode Design Problem Skeleton\n\n\n```go\ntype LRUCache struct {\n capacity int\n cache map[int]*node\n head *node // most recently used\n tail *node // least recently used\n}\n\nfunc Constructor(capacity int) LRUCache {\n return LRUCache{\n capacity: capacity,\n cache: map[int]*node{},\n }\n}\n\nfunc (c *LRUCache) Get(key int) int {\n // ...\n return -1\n}\n\nfunc (c *LRUCache) Put(key, value int) {\n // ...\n}\n```\n\n\nThe `Constructor` function returns the value, not a pointer. LeetCode's harness handles the pointer for you when it calls methods. Stick to this signature for design problems; deviating from it breaks the test runner.\n\n---\n\nThis crash course covers the Go features that come up most often in DSA problems. The rest of the course assumes you can read and write these patterns fluently. When a later chapter shows a Go solution, the building blocks here are the ones it uses.","pageType":"dsa"}

Go Crash Course for DSA

Ashish Pratap Singh

Get Premium