// — Arithmetic —
max(3, 7)                              // 7   (Go 1.21+)
min(3, 7)                              // 3
x := -5; if x < 0 { x = -x }         // 5   (int abs)
math.Abs(-3.14)                        // 3.14 (float64)

// — Power & Root —
math.Pow(2, 10)                        // 1024.0 (float64)
int(math.Pow(2, 10))                   // 1024
math.Sqrt(49)                          // 7.0
int(math.Sqrt(float64(49)))            // 7

// Perfect square check
sq := int(math.Sqrt(float64(n)))
isPerfect := sq*sq == n

// — Rounding —
math.Floor(2.7)                        // 2.0
math.Ceil(2.1)                         // 3.0
math.Round(2.5)                        // 3.0

// — Logarithms —
math.Log(math.E)                       // 1.0 (natural log)
math.Log2(8)                           // 3.0
math.Log10(1000)                       // 3.0

// Number of digits in n (n must be > 0; Log10(0) is -Inf!)
digits := int(math.Log10(float64(n))) + 1  // 9999 → 4

// — Ceiling division (positive a, b only) —
ceil := (a + b - 1) / b               // ceil(a / b) without float

// — Safe infinity for DP / shortest path —
INF := int(1e9)                        // 1e9 + 1e9 = 2e9, fits in int32
INF2 := math.MaxInt32 / 2              // safe for a single addition

// — Negative modulo —
// Go's % keeps sign of dividend: -7 % 3 == -1 (not 2!)
mod := ((a % n) + n) % n              // always-positive modulo

// GCD — Euclidean algorithm O(log min(a,b))
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

// LCM — divide first to avoid overflow
func lcm(a, b int) int { return a / gcd(a, b) * b }

// isPrime — trial division O(√n)
func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

// Modular exponentiation O(log exp)
const MOD = 1_000_000_007

func modPow(base, exp, mod int) int {
    result := 1; base %= mod
    for exp > 0 {
        if exp&1 == 1 {
            result = result * base % mod
        }
        base = base * base % mod
        exp >>= 1
    }
    return result
}

// Safe modular add
(a%MOD + b%MOD) % MOD

// Safe modular multiply (use int64 to prevent overflow)
int(int64(a) * int64(b) % int64(MOD))

// 1D DP with infinity
dp := make([]int, n)
for i := range dp { dp[i] = 1e9 }     // safer than MaxInt
dp[0] = 0  // base case

// 2D DP with infinity
dp := make([][]int, m)
for i := range dp {
    dp[i] = make([]int, n)
    for j := range dp[i] {
        dp[i][j] = 1e9
    }
}

// Memoization (sentinel = -1 for uncomputed)
memo := make([]int, n)
for i := range memo { memo[i] = -1 }

// Boolean DP
dp := make([]bool, n+1)
dp[0] = true  // base: empty subset

// Space-optimized (two variables) — House Robber pattern
prev2, prev1 := 0, 0
for _, num := range nums {
    curr := max(prev1, prev2+num)
    prev2 = prev1
    prev1 = curr
}

// ❌ Go wraps silently — no panic, no error!
a := math.MaxInt
b := 1
sum := a + b   // wraps to math.MinInt

// ✅ Check before adding
if a > math.MaxInt - b {
    // would overflow
}

// ❌ int32 values multiplied may overflow int
width, height := 50000, 50000
area := width * height   // may overflow int32

// ✅ Cast to int64 before multiplying
area := int64(width) * int64(height)

// ❌ Overflows when lo + hi > MaxInt
mid := (lo + hi) / 2

// ✅ Safe midpoint
mid := lo + (hi-lo)/2

// Go has no >>> — use the subtraction form above
// For uint: mid := (lo + hi) / 2  (safe since unsigned)

// ⚠ -math.MinInt64 == math.MinInt64 (wraps!)
n := math.MinInt64
neg := -n       // still MinInt64!

// ✅ Check before negating
if n == math.MinInt64 {
    // handle separately — no positive counterpart
}

// abs function must guard against MinInt
func abs(n int) int {
    if n == math.MinInt {
        panic("cannot negate MinInt")
    }
    if n < 0 { return -n }
    return n
}

// ❌ Using MaxInt as INF causes overflow when adding edge weight
INF := math.MaxInt
if dist[u] + w < dist[v] { ... }  // INF + w wraps!

// ✅ Use 1e9 as INF (1e9 + 1e9 = 2e9, fits in int32)
INF := int(1e9)

// ✅ Or guard before adding
if dist[u] != INF && dist[u]+w < dist[v] {
    dist[v] = dist[u] + w
}

// — int ↔ string —
s := strconv.Itoa(42)              // "42"
s  = fmt.Sprintf("%d", 42)        // "42"
s  = strconv.FormatInt(42, 10)    // "42"

n, err := strconv.Atoi("42")      // 42, nil
n64, _ := strconv.ParseInt("42", 10, 64) // int64(42)
f, _   := strconv.ParseFloat("3.14", 64) // 3.14

// — rune (char) ↔ int index —
idx := 'c' - 'a'                  // 2
d   := '7' - '0'                  // 7
ch  := 'a' + 2                    // 'c'
code := int('A')                   // 65

// — string ↔ []rune / []byte —
runes := []rune(s)                // unicode-safe characters
s = string(runes)
bytes := []byte(s)                // raw bytes
s = string(bytes)

// — Radix conversions —
strconv.FormatInt(10, 2)           // "1010" (binary)
strconv.FormatInt(255, 16)         // "ff"   (hex)
strconv.FormatInt(8, 8)            // "10"   (octal)
n, _ = strconv.ParseInt("1010", 2, 64)  // 10
n, _ = strconv.ParseInt("FF", 16, 64)   // 255

// ❌ Ignoring error — n is 0 on failure, silently wrong
n, _ := strconv.Atoi(s)

// ✅ Always check
n, err := strconv.Atoi(s)
if err != nil {
    return 0, err
}

// Go has no exceptions — error handling is explicit
// via (value, error) return pattern

unicode.IsDigit(c)          // '0'..'9'
unicode.IsLetter(c)         // a-z, A-Z, Unicode
unicode.IsSpace(c)          // space, tab, newline
unicode.IsUpper(c)          // A-Z
unicode.IsLower(c)          // a-z

// Fast inline ASCII-only checks (tight loops):
c >= 'a' && c <= 'z'        // lowercase
c >= 'A' && c <= 'Z'        // uppercase
c >= '0' && c <= '9'        // digit

unicode.ToUpper(c)  // 'a' → 'A'
unicode.ToLower(c)  // 'A' → 'a'

// Bit-level case tricks (ASCII letters only):
c | ' '    // force lowercase  ('A'→'a', 'a'→'a')
c & '_'    // force uppercase  ('a'→'A', 'A'→'A')
c ^ ' '    // toggle case      ('a'↔'A')
// ' ' = 32 = 0b0010_0000,  '_' = 95 = 0b0101_1111

// Vowel check
lower := unicode.ToLower(c)
isVowel := lower=='a' || lower=='e' || lower=='i' || lower=='o' || lower=='u'

// — Single-bit operations —
(n >> i) & 1 == 1                 // check bit i
n |= 1 << i                       // set bit i
n &^= 1 << i                      // clear bit i (Go AND-NOT)
n ^= 1 << i                       // toggle bit i

// — Lowest set bit, Kernighan's —
n & (-n)                           // isolate rightmost 1: 12(1100) → 4(0100)
n &= n - 1                        // clear lowest set bit

// Count set bits — Kernighan's O(k)
count := 0
for n != 0 { n &= n - 1; count++ }

// Count set bits — built-in O(1)
bits.OnesCount(uint(n))

// — Shifts, even/odd —
n << k    // n × 2^k
n >> k    // n ÷ 2^k (arithmetic, preserves sign)
n&1 == 0  // even
n&1 == 1  // odd

// — XOR rules —
a ^ 0 == a        // unchanged
a ^ a == 0        // self-cancels ← key for Single Number
a ^ b ^ a == b    // associative + self-cancel

// — Swap without temp —
a, b = b, a       // Go's idiomatic swap (no XOR trick needed)

// — Negate via bits (two's complement) —
^n + 1             // same as -n  (^ is bitwise NOT in Go)

// — Update bit i to value v (0 or 1) —
n = (n &^ (1 << i)) | (v << i)

// — Highest one bit (floor power of 2) —
1 << (bits.Len(uint(n)) - 1)    // 12 → 8, 16 → 16

// — Bitmask & subset enumeration —
(1 << n) - 1       // n=4 → 0b1111 = 15

for sub := m; sub > 0; sub = (sub - 1) & m {
    // process sub
}
// don't forget empty subset (sub = 0)

// Go's >> is arithmetic for signed (preserves sign)
// -1 >> 1 → still -1 (sign bit propagates)

// Count bits on any int (including negative):
// ✅ Convert to uint
bits.OnesCount(uint(n))

// Go has no >>> (unsigned shift) — use uint types instead

// ❌ 0 falsely passes
return (n & (n-1)) == 0

// ✅ Must check n > 0
return n > 0 && (n & (n-1)) == 0

// Nil slice (nil, length 0, capacity 0)
var arr []int             // arr == nil

// Empty slice (not nil, length 0)
arr := []int{}            // arr != nil, len=0
arr := make([]int, 0)     // same

// Pre-sized (length=n, all zeros)
arr := make([]int, n)

// Pre-sized with capacity
arr := make([]int, 0, n)  // len=0, cap=n

// Pre-filled literal
arr := []int{1, 2, 3}

// Grow dynamically
arr = append(arr, val)

// Fixed-size array (value type)
var a [5]int               // [0, 0, 0, 0, 0]
a := [3]int{1, 2, 3}
b := a                     // deep copy

// 2D slice
grid := make([][]int, rows)
for i := range grid {
    grid[i] = make([]int, cols)
}

// — Sort —
sort.Ints(arr)                             // ascending
sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
sort.Sort(sort.Reverse(sort.IntSlice(arr))) // descending

// Sort 2D by first element
sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0]
})

// — Copy —
cp := make([]int, len(arr))
copy(cp, arr)                              // deep copy

// 2D clone
cp2d := make([][]int, len(grid))
for i := range grid {
    cp2d[i] = make([]int, len(grid[i]))
    copy(cp2d[i], grid[i])
}

// — Aggregate —
sum := 0
for _, v := range arr { sum += v }

mn := arr[0]  // panics if arr is empty — guard with len check
for _, v := range arr[1:] { if v < mn { mn = v } }

// — Reverse in-place —
for l, r := 0, len(arr)-1; l < r; l, r = l+1, r-1 {
    arr[l], arr[r] = arr[r], arr[l]
}

// — Shuffle (Fisher-Yates) —
rand.Shuffle(len(arr), func(i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
})

// — Remove at index —
arr = append(arr[:i], arr[i+1:]...)       // O(n), order preserved
arr[i] = arr[len(arr)-1]; arr = arr[:len(arr)-1] // O(1), order lost

// — Rotate left by k (guard empty slice: len==0 panics on %) —
if len(s) > 0 { k %= len(s) }
s = append(s[k:], s[:k]...)

// — Remove duplicates (sorted) —
slices.Sort(s)
s = slices.Compact(s)                     // Go 1.21+

// — Print —
fmt.Println(arr)                           // [1 2 3]

// ✅ Guard before any logic
if len(nums) == 0 { return ... }
if len(nums) < 2 { return nums[0] }   // needs at least 2

// Kadane's: init with nums[0], loop from i=1 → needs guard
// Two pointers: right = len(nums)-1 → -1 if empty → panic
// Fixed window: k > n → index out of bounds

// Kadane: max subarray of [-5] = -5 (init from nums[0]) ✓
// House Robber II [5] → must return nums[0]
if len(nums) == 1 { return nums[0] }

// Binary Search [5], find 5: lo=hi=0, mid=0, found ✓
// Min in rotated [5]: no rotation → returns nums[0] ✓

// House Robber II [2,3]: can't rob both → max(2,3) = 3
if len(nums) == 2 { return max(nums[0], nums[1]) }

// Remove 2nd from end of [1→2]: removes head → need dummy
dummy := &ListNode{Next: head}

// Two Sum [3,3] target=6: same element used twice?
// Use index check: i != j

// — Access —
len(s)                  // byte length
len([]rune(s))          // rune (unicode char) count
s[i]                    // byte at index i
[]rune(s)[i]            // rune at index i
s[i:j]                  // substring [i, j)

// — Search —
strings.Index(s, "sub")       // first occurrence, -1 if not found
strings.LastIndex(s, "sub")   // last occurrence
strings.Contains(s, "sub")    // boolean
strings.HasPrefix(s, "pre")   // starts with
strings.HasSuffix(s, "suf")   // ends with

// — Transform —
strings.ToLower(s)
strings.ToUpper(s)
strings.TrimSpace(s)
strings.Replace(s, "old", "new", 1)    // first occurrence only
strings.ReplaceAll(s, "old", "new")    // all occurrences
strings.Trim(s, " \t")                // trim specific chars from both ends
strings.TrimLeft(s, "0")              // trim from left
strings.TrimRight(s, "\n")            // trim from right
strings.Split(s, ",")          // split by separator
strings.Fields(s)              // split by any whitespace
strings.Join(elems, "-")       // join with delimiter
strings.Repeat("ab", 3)        // "ababab"

// — Reverse (unicode-safe) —
runes := []rune(s)
for l, r := 0, len(runes)-1; l < r; l, r = l+1, r-1 {
    runes[l], runes[r] = runes[r], runes[l]
}
s = string(runes)

// — Comparison & anagram key —
s1 == s2                       // value comparison ✅
strings.EqualFold(s1, s2)      // case-insensitive

// Sorted key for anagram grouping
runes := []rune(s)
sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
key := string(runes)

// Frequency array key (no sort needed)
var freq [26]int
for _, c := range s { freq[c-'a']++ }
// use freq as map key (arrays are comparable in Go)

// — strings.Builder —
var sb strings.Builder
sb.WriteString("text")  // append string
sb.WriteRune('c')       // append rune
sb.WriteByte('a')       // append byte
sb.Len()                // current length
sb.Reset()              // clear
sb.String()             // convert to string

// Reverse a string via Builder
var sb2 strings.Builder
runes := []rune(s)
for i := len(runes) - 1; i >= 0; i-- {
    sb2.WriteRune(runes[i])
}
reversed := sb2.String()

// — Regex —
import "regexp"
re := regexp.MustCompile(`\d+`)
ok := re.MatchString("abc123")           // true
all := re.FindAllString("a1b2c3", -1)    // ["1", "2", "3"]
// Go uses RE2 (no backreferences, guaranteed linear time)

// strings.Split("", ",") returns [""] (length=1, NOT 0!)
parts := strings.Split("", ",")  // len=1, parts[0]=""

// ✅ Guard before split
if s == "" { return []string{} }

// Also: strings.Split("a,,b", ",") → ["a", "", "b"]
// Empty strings appear between consecutive delimiters

// Empty string → palindrome (true)
// Single char → palindrome (true)
// "  " → after stripping → empty → true

// Valid Palindrome: strip non-alphanumeric, lowercase
func isPalindrome(s string) bool {
    var clean []rune
    for _, c := range s {
        if unicode.IsLetter(c) || unicode.IsDigit(c) {
            clean = append(clean, unicode.ToLower(c))
        }
    }
    for l, r := 0, len(clean)-1; l < r; l, r = l+1, r-1 {
        if clean[l] != clean[r] { return false }
    }
    return true
}

// Sort ascending
sort.Ints(arr)
slices.Sort(arr)                      // Go 1.21+

// Sort descending
sort.Sort(sort.Reverse(sort.IntSlice(arr)))
slices.SortFunc(arr, func(a, b int) int { return cmp.Compare(b, a) }) // Go 1.21+; b-a can overflow

// Custom sort with bool less function
sort.Slice(arr, func(i, j int) bool {
    return arr[i] < arr[j]           // ascending
})

// Stable sort (preserves equal-element order)
sort.SliceStable(arr, func(i, j int) bool {
    return arr[i] < arr[j]
})

// Sort intervals by start asc, end desc (tie-break)
sort.Slice(intervals, func(i, j int) bool {
    if intervals[i][0] != intervals[j][0] {
        return intervals[i][0] < intervals[j][0]
    }
    return intervals[i][1] > intervals[j][1]
})

// Sort by string length
sort.Slice(strs, func(i, j int) bool {
    return len(strs[i]) < len(strs[j])
})

// Largest Number #179 — concat comparison
sort.Slice(strs, func(i, j int) bool {
    return strs[i]+strs[j] > strs[j]+strs[i]
})

// Sort by absolute value
sort.Slice(arr, func(i, j int) bool {
    ai, aj := arr[i], arr[j]
    if ai < 0 { ai = -ai }
    if aj < 0 { aj = -aj }
    return ai < aj
})

// Check if sorted
ok := slices.IsSorted(arr)            // Go 1.21+
ok  = sort.IntsAreSorted(arr)

// Next permutation (no built-in)
func nextPermutation(nums []int) bool {
    n := len(nums); i := n - 2
    for i >= 0 && nums[i] >= nums[i+1] { i-- }
    if i < 0 { return false }
    j := n - 1
    for nums[j] <= nums[i] { j-- }
    nums[i], nums[j] = nums[j], nums[i]
    slices.Reverse(nums[i+1:])
    return true
}

// Java: (a, b) -> a - b can overflow!
// Go:   sort.Slice uses bool, no subtraction needed ✅

sort.Slice(arr, func(i, j int) bool {
    return arr[i] < arr[j]   // safe — no overflow risk
})

// Go's sort panics if Less is inconsistent
// (violates transitivity), so always ensure:
//   Less(i,j) && Less(j,k) → Less(i,k)

// Binary search (sorted slice) — returns insertion point
idx := sort.SearchInts(sorted, target)
found := idx < len(sorted) && sorted[idx] == target

// Go 1.21+
idx, found := slices.BinarySearch(sorted, target)

// Lower / upper bound via sort.Search
lb := sort.Search(len(s), func(i int) bool { return s[i] >= target })
ub := sort.Search(len(s), func(i int) bool { return s[i] > target })

// Find minimum in rotated sorted array (= pivot index)
func findMin(nums []int) int {
    lo, hi := 0, len(nums)-1
    for lo < hi {
        mid := lo + (hi-lo)/2
        if nums[mid] > nums[hi] {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Search in rotated array
func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target { return mid }
        if nums[lo] <= nums[mid] {
            if nums[lo] <= target && target < nums[mid] {
                hi = mid - 1
            } else { lo = mid + 1 }
        } else {
            if nums[mid] < target && target <= nums[hi] {
                lo = mid + 1
            } else { hi = mid - 1 }
        }
    }
    return -1
}

// ❌ No progress when lo=0, hi=1: mid=0, lo stays 0
for lo < hi {
    mid := lo + (hi-lo)/2
    if valid(mid) { hi = mid }
    else { lo = mid }  // ← INFINITE LOOP!
}

// ✅ Always advance by at least 1
lo = mid + 1

// Rule: lo < hi  → boundary-finding
// Rule: lo <= hi → exact-match

// First occurrence: keep searching LEFT when found
if nums[mid] == target { hi = mid }       // ← not return!

// Last occurrence: keep searching RIGHT when found
if nums[mid] == target { lo = mid + 1 }   // ← not return!
// answer is lo-1 after loop

// lo/hi must cover the complete valid range!

// Koko Eating Bananas:
lo = 1             // minimum possible rate
hi = max(piles)    // one pile per hour

// Capacity to Ship:
lo = max(weights)  // must fit heaviest package
hi = sum(weights)  // ship everything in one day

// isFeasible must be strictly monotone!

// Sorted array = rotation by 0
// Binary search: findMin returns index 0 ✓
// Search in rotated: left half is always sorted ✓

// 3Sum on sorted array: early exit if nums[0] > 0
if nums[i] > 0 { break }

// No special case needed — algorithms handle it naturally

// — Map operations —
m := make(map[int]int)
m[key] = val                        // put
val := m[key]                       // get (zero if missing)
val, ok := m[key]                   // get with existence check
delete(m, key)                      // remove
len(m)                              // size
clear(m)                            // remove all (Go 1.21+)

// getOrDefault pattern
if v, ok := m[key]; ok { use(v) } else { use(defaultVal) }

// Frequency counting
freq := make(map[int]int)
for _, n := range nums { freq[n]++ }

// Decrement and remove if zero
freq[key]--
if freq[key] == 0 { delete(freq, key) }

// Group by key
groups := make(map[int][]int)
groups[key] = append(groups[key], val)  // auto-inits slice

// — Set via map[T]struct{} —
set := make(map[int]struct{})
set[val] = struct{}{}           // add
_, exists := set[val]           // contains
delete(set, val)                // remove

// Set from slice
for _, v := range arr { set[v] = struct{}{} }

// Intersection
for k := range set1 {
    if _, ok := set2[k]; ok { /* in both */ }
}

// Union
for k := range set2 { set1[k] = struct{}{} }

// Visited pattern (BFS/DFS)
visited := make(map[int]bool)
if !visited[node] { visited[node] = true }

// Ordered iteration (sort keys)
keys := make([]string, 0, len(m))
for k := range m { keys = append(keys, k) }
slices.Sort(keys)
for _, k := range keys { v := m[k]; /* ... */ }

// Multi-map pattern
mm := map[string][]int{}
mm["a"] = append(mm["a"], 1, 2)

// Check if two maps have same keys and values
func mapsEqual(a, b map[int]int) bool {
    if len(a) != len(b) { return false }
    for k, v := range a {
        if b[k] != v { return false }
    }
    return true
}

// In Go, modifying a map while iterating is ALLOWED
// (unlike Java's ConcurrentModificationException)
// BUT behavior is non-deterministic.

// ✅ Collect keys first, then modify
var toDelete []int
for k := range m {
    if shouldRemove(k) { toDelete = append(toDelete, k) }
}
for _, k := range toDelete { delete(m, k) }

type MinHeap []int
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h; n := len(old)
    x := old[n-1]; *h = old[:n-1]
    return x
}

// For max-heap: flip Less to h[i] > h[j]

// Usage:
h := &MinHeap{}
heap.Init(h)
heap.Push(h, 5)
heap.Push(h, 3)
top := heap.Pop(h).(int)   // 3 (smallest)
peek := (*h)[0]             // peek without removing

// PairHeap for {distance, node} — Dijkstra
type PairHeap [][2]int
func (h PairHeap) Len() int            { return len(h) }
func (h PairHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h PairHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PairHeap) Push(x any)         { *h = append(*h, x.([2]int)) }
func (h *PairHeap) Pop() any {
    old := *h; n := len(old)
    x := old[n-1]; *h = old[:n-1]
    return x
}

// Frequency-based max-heap: sort by freq desc, then val asc
type FreqItem struct{ val, freq int }
type FreqHeap []FreqItem
func (h FreqHeap) Less(i, j int) bool {
    if h[i].freq != h[j].freq { return h[i].freq > h[j].freq }
    return h[i].val < h[j].val
}
// ... Len, Swap, Push, Pop same pattern

// Top-K via heap (partial sort)
h := &MinHeap{}
heap.Init(h)
for _, v := range data {
    heap.Push(h, v)
    if h.Len() > k { heap.Pop(h) }  // evict smallest
}
// h now holds the k largest elements

// — Stack via slice —
var stack []int
stack = append(stack, x)           // push
top := stack[len(stack)-1]         // peek
stack = stack[:len(stack)-1]       // pop
len(stack) == 0                    // isEmpty

// — Queue via slice —
var queue []int
queue = append(queue, x)           // enqueue
front := queue[0]                  // peek
queue = queue[1:]                  // dequeue (O(n))
len(queue) == 0                    // isEmpty

// — O(1) queue via container/list —
q := list.New()
q.PushBack(x)                     // enqueue
val := q.Front().Value.(int)      // peek
q.Remove(q.Front())               // dequeue O(1)

// — Sliding window maximum (monotonic decreasing deque) —
var dq []int  // stores indices
for i, num := range nums {
    for len(dq) > 0 && nums[dq[len(dq)-1]] < num {
        dq = dq[:len(dq)-1]         // remove smaller from back
    }
    dq = append(dq, i)
    if dq[0] <= i-k { dq = dq[1:] } // out of window
    if i >= k-1 {
        result = append(result, nums[dq[0]])
    }
}

import "container/list"

l := list.New()
e1 := l.PushBack(10)               // append
e2 := l.PushFront(5)               // prepend
l.InsertBefore(7, e1)              // before element
front := l.Front()                 // *Element (nil if empty)
val   := front.Value.(int)         // type-assert
l.Remove(e2)                       // O(1)
l.MoveToFront(e1)                  // promote

l.InsertAfter(8, e1)               // after element
l.Len()                            // number of elements

// Iterate forward
for e := l.Front(); e != nil; e = e.Next() { fmt.Println(e.Value) }
// Iterate backward
for e := l.Back(); e != nil; e = e.Prev() { fmt.Println(e.Value) }

// LRU cache: map[key]*list.Element + list for eviction order
type LRU struct {
    cap   int
    items map[int]*list.Element
    order *list.List
}
type entry struct{ key, val int }

func (c *LRU) Get(key int) (int, bool) {
    if el, ok := c.items[key]; ok {
        c.order.MoveToFront(el)
        return el.Value.(*entry).val, true
    }
    return 0, false
}

func (c *LRU) Put(key, val int) {
    if el, ok := c.items[key]; ok {
        el.Value.(*entry).val = val
        c.order.MoveToFront(el)
        return
    }
    if c.order.Len() == c.cap {
        oldest := c.order.Back()
        c.order.Remove(oldest)
        delete(c.items, oldest.Value.(*entry).key)
    }
    el := c.order.PushFront(&entry{key, val})
    c.items[key] = el
}

// ❌ Panics: index out of range
top := stack[len(stack)-1]  // when stack is empty

// ✅ Always check before accessing
if len(stack) > 0 { top = stack[len(stack)-1] }
if len(queue) > 0 { front = queue[0] }

// Monotonic stack: after loop, remaining elements have
// no "next greater" → result stays default (often 0 or -1)

// Largest Rectangle (#84): append sentinel height 0
// to force all bars to pop at the end
heights = append(heights, 0)

// Next Greater Element: remaining stack elements → result = -1
// (already handled if result initialized to -1)

// 4-directional (up, right, down, left)
dr := [4]int{-1, 0, 1, 0}
dc := [4]int{0, 1, 0, -1}

// 8-directional (includes diagonals)
dr8 := [8]int{-1,-1,-1, 0, 0, 1, 1, 1}
dc8 := [8]int{-1, 0, 1,-1, 1,-1, 0, 1}

// Bounds check
func inBounds(r, c, rows, cols int) bool {
    return r >= 0 && r < rows && c >= 0 && c < cols
}

for d := 0; d < 4; d++ {
    nr, nc := r+dr[d], c+dc[d]
    if inBounds(nr, nc, rows, cols) { /* valid neighbor */ }
}

// 2D ↔ 1D index
idx := r*cols + c
r, c := idx/cols, idx%cols

// Transpose (square matrix)
for i := 0; i < n; i++ {
    for j := i+1; j < n; j++ {
        mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
    }
}
// Rotate 90° clockwise (square matrix) = transpose + reverse each row

// Spiral traversal: 4 boundaries shrinking
top, bot, left, right := 0, m-1, 0, n-1
for top <= bot && left <= right {
    // → top row, ↓ right col, ← bottom row, ↑ left col
    top++; right--; bot--; left++
}

// Diagonal properties:
// Same diagonal:      r - c  is constant
// Same anti-diagonal: r + c  is constant

// Grid DFS (4-directional)
func dfs(grid [][]int, vis [][]bool, r, c int) {
    if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) || vis[r][c] {
        return
    }
    vis[r][c] = true
    for d := 0; d < 4; d++ {
        dfs(grid, vis, r+dr[d], c+dc[d])
    }
}

type ListNode struct {
    Val  int
    Next *ListNode
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type GraphNode struct {
    Val       int
    Neighbors []*GraphNode
}

// Adjacency list — unweighted undirected
adj := make([][]int, n)
for _, e := range edges {
    adj[e[0]] = append(adj[e[0]], e[1])
    adj[e[1]] = append(adj[e[1]], e[0])  // omit for directed
}

// Weighted: [][2]int{neighbor, weight}
adj := make([][][2]int, n)
adj[u] = append(adj[u], [2]int{v, w})

// In-degree array (for Kahn's topo sort)
inDeg := make([]int, n)
for _, e := range edges { inDeg[e[1]]++ }

// Union-Find (DSU) with path compression + union by rank
parent := make([]int, n)
rank := make([]int, n)
for i := range parent { parent[i] = i }

func find(x int) int {
    if parent[x] != x { parent[x] = find(parent[x]) }
    return parent[x]
}

func union(x, y int) bool {
    px, py := find(x), find(y)
    if px == py { return false }
    if rank[px] < rank[py] { px, py = py, px }
    parent[py] = px
    if rank[px] == rank[py] { rank[px]++ }
    return true
}

if head == nil { return nil }
if head.Next == nil { return head }

// Iterate safely
for curr != nil { curr = curr.Next }

// Dummy head avoids nil checks for head insertion/deletion
dummy := &ListNode{Next: head}
// ... work with dummy ...
return dummy.Next

// ✅ Short-circuit: fast checked before fast.Next
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}

// ✅ Reverse: save next before overwriting
next := curr.Next    // 1. save
curr.Next = prev     // 2. reverse
prev = curr          // 3. advance prev
curr = next          // 4. advance curr

// Floyd's cycle: phase 2 — find cycle start
ptr := head
for ptr != slow {
    ptr = ptr.Next; slow = slow.Next
}
return ptr  // cycle entry point

// DFS base case — always first line
if node == nil { return 0 }

// BFS start
if root == nil { return result }

// ❌ BST validate with int bounds fails for MinInt node
// ✅ Always use int64 bounds
func validate(n *TreeNode, lo, hi int64) bool {
    if n == nil { return true }
    v := int64(n.Val)
    if v <= lo || v >= hi { return false }
    return validate(n.Left, lo, v) && validate(n.Right, v, hi)
}
validate(root, math.MinInt64, math.MaxInt64)

// Max Path Sum: init to MinInt (not 0!)
ans := math.MinInt
leftGain := max(0, maxGain(n.Left))
rightGain := max(0, maxGain(n.Right))

// Skewed tree (n=10^5 all left): use iterative traversal
var stack []*TreeNode
curr := root
for curr != nil || len(stack) > 0 {
    for curr != nil { stack = append(stack, curr); curr = curr.Left }
    curr = stack[len(stack)-1]; stack = stack[:len(stack)-1]
    curr = curr.Right
}

// ❌ Only visits component containing node 0
dfs(graph, 0, visited)
// ✅ Start from every unvisited node
for i := 0; i < n; i++ {
    if !visited[i] { dfs(graph, i, visited); components++ }
}

// Dijkstra: must skip stale entries
curr := heap.Pop(h)
if curr.dist > dist[curr.node] { continue }

// Dijkstra: unreachable nodes
if dist[dst] == INF { return -1 }
// ❌ Dijkstra with negative weights → use Bellman-Ford

// Undirected DFS: ignore parent, not all visited neighbors
if neighbor == parent { continue }
if visited[neighbor] { return true }  // real cycle
// For directed: use 3-state (unvisited / in-stack / done)

// n = list length → removes head → need dummy
dummy := &ListNode{Next: head}
fast, slow := dummy, dummy
for i := 0; i <= n; i++ { fast = fast.Next }
for fast != nil {
    fast = fast.Next; slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next

// Standard algorithm handles p-is-ancestor correctly
if root == nil || root == p || root == q { return root }
left := lca(root.Left, p, q)
right := lca(root.Right, p, q)
if left != nil && right != nil { return root }
if left != nil { return left }
return right

// Diameter of tree [1]: diameter = 0 (no edges)
// Not 1! Diameter counts edges, not nodes.

// BST validate [MinInt]: use int64 bounds
validate(root, math.MinInt64, math.MaxInt64)

// LCA: if root is p or q, early return handles it
if root == p || root == q { return root }

// — String palindrome (two pointers) —
l, r := 0, len(s)-1
for l < r {
    if s[l] != s[r] { return false }
    l++; r--
}

// — Integer palindrome (no string conversion) —
if x < 0 || (x%10 == 0 && x != 0) { return false }
rev := 0
for x > rev { rev = rev*10 + x%10; x /= 10 }
return x == rev || x == rev/10

// — Expand around center (longest palindrome) —
func expand(s string, l, r int) int {
    for l >= 0 && r < len(s) && s[l] == s[r] { l--; r++ }
    return r - l - 1
}

// — Find minimum / maximum —
ans := math.MaxInt
ans = min(ans, candidate)

// — Collect results: always snapshot the slice! —
cp := make([]int, len(current))
copy(cp, current)
result = append(result, cp)

// — Global variable for DFS via closure —
ans := 0
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
    if node == nil { return }
    ans = max(ans, node.Val)
    dfs(node.Left); dfs(node.Right)
}

// — Frequency arrays —
var freq [26]int                    // 26 lowercase letters
for _, c := range s { freq[c-'a']++ }
var freq128 [128]int                // 128 ASCII
freq1 == freq2                      // ✅ arrays are comparable in Go

// — Early-return checklist —
if len(nums) == 0  { return ... }   // array
if len(s) == 0     { return ... }   // string
if root == nil     { return ... }   // tree
if head == nil     { return head }  // linked list
if k > len(nums)   { return 0 }    // window too large

if k > len(nums) { return 0 }
if len(p) > len(s) { return false }  // Permutation In String

// Matches counter — increment only at exact boundary
if window[c] == need[c] { formed++ }

// Decrement only when crossing below threshold
window[lc]--
if window[lc] < need[lc] { formed-- }

// Min Window Substring: no valid window → return ""
result := ""
if minLen > len(s) { return "" }

// Max Consecutive Ones: all ones → return n
// All zeros → return 0 (default)

// Longest Substring w/o Repeat:
//   all unique → return n
//   all same char → return 1

// Climbing Stairs: n=1 → dp[i-2] accesses dp[-1]
if n <= 1 { return n }

// Decode Ways: s[0]='0' → 0 ways immediately
// Coin Change: amount=0 → 0 (no coins needed)
// Edit Distance: dp[i][0]=i, dp[0][j]=j → don't forget!

// House Robber II: can't use first and last together
if len(nums) == 1 { return nums[0] }   // guard before split
r1 := rob(nums[0 : n-1]); r2 := rob(nums[1 : n])
return max(r1, r2)

// Unbounded (Coin Change): each coin reusable → loop FORWARD
for _, coin := range coins {
    for j := coin; j <= amount; j++ {
        dp[j] = min(dp[j], dp[j-coin]+1)
    }
}
// 0/1 Knapsack: each item once → loop BACKWARD
for _, item := range items {
    for j := W; j >= item.w; j-- {
        dp[j] = max(dp[j], dp[j-item.w]+item.v)
    }
}

// ❌ All results point to same backing array
result = append(result, curr)
// ✅ Always copy on add
cp := make([]int, len(curr))
copy(cp, curr)
result = append(result, cp)

// ❌ i > 0: skips valid combinations (too aggressive)
if i > 0 && nums[i] == nums[i-1] { continue }
// ✅ i > start: only skip duplicates at same recursion level
if i > start && nums[i] == nums[i-1] { continue }
// MUST sort array first!
sort.Ints(nums)

// Kadane's: ❌ init maxSoFar = 0 → [-3,-1,-2] wrongly returns 0
// ✅ Init from first element
maxSoFar, curr := nums[0], nums[0]

// Max Product [2,3,0,4]: zero resets the subarray
// Product Except Self with zero: 2+ zeros → all products are zero

// 3Sum [0,0,0] → skip: if i > 0 && nums[i] == nums[i-1] { continue }

// Longest Consecutive [1,1,1] → answer=1 (not 3); use set

// Rotated Sorted Array II [1,1,1,1]: can't determine sorted half
if nums[lo] == nums[mid] && nums[mid] == nums[hi] {
    lo++; hi--  // linear fallback
}

// Subarray length: right - left + 1
// Substring s[i:j]: [i, j), length = j - i

// for left < right  vs  for left <= right
// Binary search: lo <= hi for exact-match
// Binary search: lo < hi  for boundary-finding

// Return conventions:
// Binary Search not found    → -1
// Coin Change impossible     → -1 (NOT 0!)
// Min Window no window       → ""
// Subsets: empty set []      → valid result

// Integer comparison: no autoboxing pitfall in Go
a, b := 1000, 1000
a == b   // ✅ true (Go has no Integer cache issue)

// — Goroutine —
go func() { fmt.Println("concurrent") }()

// — Channel —
ch := make(chan int, 10)      // buffered
ch <- 42                      // send
v := <-ch                     // receive
close(ch)

// Select for multiplexing
select {
case v := <-ch1: /* ... */
case ch2 <- val: /* ... */
default: /* non-blocking */
}

// — Mutex —
var mu sync.Mutex
mu.Lock()
defer mu.Unlock()

var rw sync.RWMutex
rw.RLock(); rw.RUnlock()       // read lock

// — WaitGroup —
var wg sync.WaitGroup
for i := 0; i < 5; i++ {
    wg.Add(1)
    go func() {
        defer wg.Done()
        work()
    }()
}
wg.Wait()

// — Once —
var once sync.Once
once.Do(func() { expensiveInit() })

// — Atomic —
var counter atomic.Int64
counter.Add(1)
v := counter.Load()
counter.Store(0)
swapped := counter.CompareAndSwap(old, new)

// — Future / async pattern —
ch := make(chan int, 1)
go func() { ch <- computeResult() }()
result := <-ch  // blocks until ready

// — Worker pool —
jobs := make(chan Job, 100)
for w := 0; w < numWorkers; w++ {
    go worker(jobs)
}

// — Error return —
func divide(a, b float64) (float64, error) {
    if b == 0 { return 0, errors.New("divide by zero") }
    return a / b, nil
}
result, err := divide(10, 0)
if err != nil { log.Fatal(err) }

// — Panic / recover —
// defer must be registered BEFORE the panic occurs
defer func() {
    if r := recover(); r != nil {
        fmt.Println("recovered:", r)
    }
}()
panic("fatal error")

// — Error wrapping —
err := fmt.Errorf("open failed: %w", origErr)
if errors.Is(err, os.ErrNotExist) { /* ... */ }
var pathErr *os.PathError
if errors.As(err, &pathErr) { /* ... */ }

// — Print —
fmt.Println("hello", 42)                  // hello 42\n
fmt.Printf("name=%s age=%d\n", name, age)
s := fmt.Sprintf("%.2f", 3.14159)         // "3.14"

// — Read input —
var n int
fmt.Scan(&n)

scanner := bufio.NewScanner(os.Stdin)
for scanner.Scan() {
    line := scanner.Text()
}

// — File read —
data, err := os.ReadFile("file.txt")       // entire file

f, _ := os.Open("file.txt")
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() { line := scanner.Text() }

// — File write —
os.WriteFile("file.txt", []byte("hello"), 0644)

f, _ := os.Create("file.txt")
defer f.Close()
w := bufio.NewWriter(f)
w.WriteString("hello")
w.Flush()

// — Generics (Go 1.18+) —
func Map[T, U any](s []T, f func(T) U) []U {
    r := make([]U, len(s))
    for i, v := range s { r[i] = f(v) }
    return r
}
type Number interface { ~int | ~float64 }

// — Interface (implicit satisfaction) —
type Reader interface {
    Read(p []byte) (n int, err error)
}

// — Type assertion —
v, ok := iface.(ConcreteType)       // safe
v := iface.(ConcreteType)           // panics if wrong

// — Type switch —
switch v := iface.(type) {
case int:    /* ... */
case string: /* ... */
}

// — any (alias for interface{}) —
var x any = 42
x = "hello"

// — Pair / Tuple via struct —
type Pair struct{ First, Second int }
func twoVals() (int, string) { return 1, "hi" }
a, b := twoVals()

// — Closures capture by reference —
counter := 0
inc := func() { counter++ }

// — for range —
for i, v := range s { }       // index + value
for _, v := range s { }       // value only
for i := range s { }          // index only
for range 10 { }              // Go 1.22+, repeat N times

// — Pair / Tuple via struct or multi-return —
type Pair struct{ First, Second int }
func twoVals() (int, string) { return 1, "hi" }

// — Ring Buffer —
import "container/ring"
r := ring.New(5)               // ring of 5 elements
r.Value = 1
r = r.Next()
r.Do(func(v any) { fmt.Println(v) })  // iterate all

// — Iterators (Go 1.23+) —
import "iter"
func All(s []int) iter.Seq[int] { /* ... */ }
// Push/pull iterators for lazy sequences

// — Unit test —
func TestAdd(t *testing.T) {
    got := Add(2, 3)
    if got != 5 {
        t.Errorf("Add(2,3) = %d, want 5", got)
    }
}
// Run: go test ./...

// — Benchmark —
func BenchmarkSort(b *testing.B) {
    for b.Loop() {
        sort.Ints(data)
    }
}
// Run: go test -bench=.

// — Table-driven tests —
tests := []struct{
    name string; a, b, want int
}{
    {"positive", 2, 3, 5},
    {"zero", 0, 0, 0},
}
for _, tt := range tests {
    t.Run(tt.name, func(t *testing.T) {
        if got := Add(tt.a, tt.b); got != tt.want {
            t.Errorf("got %d, want %d", got, tt.want)
        }
    })
}

// — HTTP Server —
import "net/http"
http.HandleFunc("/hello", func(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "Hello!")
})
http.ListenAndServe(":8080", nil)

// — HTTP Client —
resp, err := http.Get("https://api.example.com/data")
if err != nil { log.Fatal(err) }       // resp can be nil on error
defer resp.Body.Close()
body, _ := io.ReadAll(resp.Body)

// POST
resp, err = http.Post(url, "application/json", bytes.NewReader(data))

// — TCP Sockets —
import "net"
ln, _ := net.Listen("tcp", ":9000")
conn, _ := ln.Accept()
defer conn.Close()
buf := make([]byte, 1024)
n, _ := conn.Read(buf)

// — JSON —
type User struct {
    Name string `json:"name"`
    Age  int    `json:"age,omitempty"`
}
data, _ := json.Marshal(user)       // struct → JSON
json.Unmarshal(data, &user)          // JSON → struct
json.NewEncoder(w).Encode(user)     // streaming encode
json.NewDecoder(r).Decode(&user)     // streaming decode

// — Time —
now := time.Now()
unix := now.Unix()
elapsed := time.Since(start)
time.Sleep(100 * time.Millisecond)

// Go uses reference time: Mon Jan 2 15:04:05 MST 2006
s := now.Format("2006-01-02 15:04:05")
t, _ := time.Parse("2006-01-02", "2024-03-15")

d := 5 * time.Second

// Timer (one-shot)
timer := time.NewTimer(2 * time.Second)
<-timer.C  // blocks until timer fires

// Ticker (repeating)
ticker := time.NewTicker(time.Second)
defer ticker.Stop()
for t := range ticker.C { /* every second */ }

nano := now.UnixNano()                 // nanoseconds since epoch

// — Binary Serialization —
import "encoding/gob"
var buf bytes.Buffer
gob.NewEncoder(&buf).Encode(data)      // struct → bytes
gob.NewDecoder(&buf).Decode(&result)    // bytes → struct

import "encoding/binary"
binary.Write(w, binary.LittleEndian, val)  // write raw bytes

// — Memory —
// Go has garbage collection — no manual free needed
p := new(int)                   // *int, zero-valued
p  = &MyStruct{Field: 1}        // composite literal
s := make([]int, 0, 100)        // slice with capacity
// Compiler decides stack vs heap (escape analysis)

// sync.Pool for object reuse
pool := sync.Pool{
    New: func() any { return new(bytes.Buffer) },
}
buf := pool.Get().(*bytes.Buffer)
buf.Reset()
pool.Put(buf)