Go Interview Reference

package main

import "fmt"

func main() {
    // var declaration — explicit type
    var x int = 10
    var s string = "hello"

    // Short declaration — type inferred (ONLY inside functions)
    y := 42
    name := "gopher"

    // Multiple assignment
    a, b := 1, 2
    a, b = b, a // swap — no temp variable needed

    // Zero values (default when declared without init)
    var i int     // 0
    var f float64 // 0.0
    var bl bool   // false
    var str string // ""
    var p *int    // nil

    // Constants
    const Pi = 3.14159
    const (
        KB = 1024
        MB = KB * 1024
        GB = MB * 1024
    )

    // iota — auto-incrementing constant
    const (
        Sunday = iota // 0
        Monday        // 1
        Tuesday       // 2
    )

    fmt.Println(x, s, y, name, a, b, i, f, bl, str, p, Pi, KB, Sunday, Monday, Tuesday)
}

// Go is STRICT — no implicit conversion
var i int = 42
var f float64 = float64(i)   // explicit cast
var u uint = uint(f)

// string ↔ int via strconv (NOT string(65) = "A")
import "strconv"
n, err := strconv.Atoi("123")  // string → int
s := strconv.Itoa(n)           // int → string

// string ↔ []byte
bs := []byte("hello")   // string → []byte (copy)
str := string(bs)       // []byte → string (copy)

// string ↔ []rune (for Unicode)
runes := []rune("日本語") // len = 3
bytes := []byte("日本語") // len = 9

package main

import "fmt"

// ── Set pattern: map[T]struct{} ────────────────────────────
// struct{} uses 0 bytes vs bool which uses 1 byte per entry
func contains(slice []int, target int) bool {
    set := make(map[int]struct{})
    for _, v := range slice { set[v] = struct{}{} }
    _, ok := set[target]
    return ok
}

// ── Check if sentence is pangram ──────────────────────────
// Every letter a-z appears at least once
func checkIfPangram(sentence string) bool {
    seen := make(map[rune]bool)
    for _, c := range sentence { seen[c] = true }
    return len(seen) >= 26
}

// Bit manipulation variant — O(1) space
func checkIfPangramBits(sentence string) bool {
    var mask int
    for _, c := range sentence {
        if c >= 'a' && c <= 'z' {
            mask |= 1 << (c - 'a')
        }
    }
    return mask == (1<<26)-1
}

// ── Missing number: find what's absent from [0..n] ────────
func missingNumber(nums []int) int {
    set := make(map[int]bool)
    for _, n := range nums { set[n] = true }
    for i := 0; i <= len(nums); i++ {
        if !set[i] { return i }
    }
    return -1
}

// Math trick — O(1) space: expected sum minus actual sum
func missingNumberMath(nums []int) int {
    n := len(nums)
    expected := n * (n + 1) / 2
    actual := 0
    for _, v := range nums { actual += v }
    return expected - actual
}

// ── Counting Elements: how many x where x+1 also exists ───
func countElements(arr []int) int {
    set := make(map[int]bool)
    for _, v := range arr { set[v] = true }
    count := 0
    for _, v := range arr {
        if set[v+1] { count++ }
    }
    return count
}

// ── Two Sum — classic hash pattern ────────────────────────
// For each num, check if (target - num) already seen
func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int) // value → index
    for i, n := range nums {
        if j, ok := seen[target-n]; ok {
            return j, i
        }
        seen[n] = i
    }
    return -1, -1
}

// ── Two Sum II: count pairs summing to target ─────────────
func twoSumCount(nums []int, target int) int {
    freq := make(map[int]int)
    for _, n := range nums { freq[n]++ }
    count := 0
    for n, c := range freq {
        complement := target - n
        if complement == n {
            count += c * (c - 1) / 2 // C(c, 2) pairs
        } else if freq[complement] > 0 && complement > n {
            count += c * freq[complement]
        }
    }
    return count
}

func main() {
    fmt.Println(checkIfPangram("thequickbrownfoxjumpsoverthelazydog")) // true
    fmt.Println(checkIfPangramBits("abcdefghijklmnopqrstuvwxyz"))       // true
    fmt.Println(missingNumberMath([]int{3, 0, 1}))                      // 2
    fmt.Println(countElements([]int{1, 2, 3, 3, 5, 0}))                 // 3
    i, j := twoSum([]int{2, 7, 11, 15}, 9)
    fmt.Println(i, j) // 0 1
}

package main

import (
    "fmt"
    "sort"
)

// ── Anagram check ─────────────────────────────────────────
func isAnagram(s, t string) bool {
    if len(s) != len(t) { return false }
    freq := make(map[rune]int)
    for _, c := range s { freq[c]++ }
    for _, c := range t {
        freq[c]--
        if freq[c] < 0 { return false }
    }
    return true
}

// Fixed-size array variant for lowercase only — faster
func isAnagramArray(s, t string) bool {
    if len(s) != len(t) { return false }
    var freq [26]int
    for i := 0; i < len(s); i++ {
        freq[s[i]-'a']++
        freq[t[i]-'a']--
    }
    for _, v := range freq { if v != 0 { return false } }
    return true
}

// ── Group anagrams together ───────────────────────────────
// Key insight: anagrams have the same sorted string
func groupAnagrams(words []string) [][]string {
    groups := make(map[string][]string)
    for _, w := range words {
        key := sortedKey(w)
        groups[key] = append(groups[key], w)
    }
    result := make([][]string, 0, len(groups))
    for _, g := range groups { result = append(result, g) }
    return result
}

func sortedKey(s string) string {
    b := []byte(s)
    sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
    return string(b)
}

// ── Find players with 0 or 1 losses ──────────────────────
// losses[player] = loss count; find: 0 losses and exactly 1 loss
func findWinners(matches [][2]int) ([]int, []int) {
    losses := make(map[int]int)
    played := make(map[int]bool)
    for _, m := range matches {
        played[m[0]] = true
        played[m[1]] = true
        losses[m[1]]++ // only loser gets a loss
    }
    var noLoss, oneLoss []int
    for p := range played {
        switch losses[p] {
        case 0: noLoss  = append(noLoss, p)
        case 1: oneLoss = append(oneLoss, p)
        }
    }
    sort.Ints(noLoss); sort.Ints(oneLoss)
    return noLoss, oneLoss
}

// ── Largest unique number ──────────────────────────────────
// Largest integer that appears exactly once
func largestUniqueNumber(nums []int) int {
    freq := make(map[int]int)
    for _, n := range nums { freq[n]++ }
    result := -1
    for n, c := range freq {
        if c == 1 && n > result { result = n }
    }
    return result
}

// ── Maximum number of balloons ─────────────────────────────
// How many times can you form the word "balloon"?
func maxNumberOfBalloons(text string) int {
    freq := make(map[rune]int)
    for _, c := range text { freq[c]++ }
    // "balloon" needs: b×1, a×1, l×2, o×2, n×1
    return min(freq['b'], freq['a'], freq['l']/2, freq['o']/2, freq['n'])
}

func min(vals ...int) int {
    m := vals[0]
    for _, v := range vals[1:] { if v < m { m = v } }
    return m
}

func main() {
    fmt.Println(isAnagram("anagram", "nagaram")) // true
    fmt.Println(isAnagram("rat", "car"))          // false
    fmt.Println(groupAnagrams([]string{"eat","tea","tan","ate","nat","bat"}))
    fmt.Println(largestUniqueNumber([]int{5, 7, 3, 9, 4, 9, 8, 3, 1})) // 8
    fmt.Println(maxNumberOfBalloons("loonbalxballoon")) // 2
}

package main

import (
    "fmt"
    "sort"
)

// ── Top K frequent elements ────────────────────────────────
// Bucket sort: frequency → []elements (O(n), no heap needed)
func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, n := range nums { freq[n]++ }

    // Bucket: index = frequency, value = list of nums with that freq
    buckets := make([][]int, len(nums)+1)
    for n, f := range freq { buckets[f] = append(buckets[f], n) }

    result := make([]int, 0, k)
    for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
        result = append(result, buckets[i]...)
    }
    return result[:k]
}

// ── Contiguous array — equal 0s and 1s ────────────────────
// Replace 0→-1, find longest subarray with sum 0
// prefix sum + map: first time we see a prefix sum
func findMaxLength(nums []int) int {
    firstSeen := map[int]int{0: -1} // prefixSum → first index
    maxLen, sum := 0, 0
    for i, n := range nums {
        if n == 0 { sum-- } else { sum++ }
        if j, ok := firstSeen[sum]; ok {
            if l := i - j; l > maxLen { maxLen = l }
        } else {
            firstSeen[sum] = i
        }
    }
    return maxLen
}

// ── Subarray sum equals K (prefix sum + map) ──────────────
func subarraySum(nums []int, k int) int {
    count, sum := 0, 0
    freq := map[int]int{0: 1}
    for _, n := range nums {
        sum += n
        count += freq[sum-k]
        freq[sum]++
    }
    return count
}

// ── Longest substring with at most K distinct chars ───────
// Sliding window + frequency map
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    freq := make(map[byte]int)
    l, maxLen := 0, 0
    for r := 0; r < len(s); r++ {
        freq[s[r]]++
        for len(freq) > k { // shrink until valid
            freq[s[l]]--
            if freq[s[l]] == 0 { delete(freq, s[l]) }
            l++
        }
        if w := r - l + 1; w > maxLen { maxLen = w }
    }
    return maxLen
}

// ── Ransom note ───────────────────────────────────────────
// Can ransomNote be built from magazine letters?
func canConstruct(ransomNote, magazine string) bool {
    freq := make(map[rune]int)
    for _, c := range magazine { freq[c]++ }
    for _, c := range ransomNote {
        freq[c]--
        if freq[c] < 0 { return false }
    }
    return true
}

// ── 4Sum count ────────────────────────────────────────────
// Count tuples (i,j,k,l) where A[i]+B[j]+C[k]+D[l]==0
// Split into two halves: hash all A+B sums, count matches in C+D
func fourSumCount(A, B, C, D []int) int {
    abSum := make(map[int]int)
    for _, a := range A {
        for _, b := range B {
            abSum[a+b]++
        }
    }
    count := 0
    for _, c := range C {
        for _, d := range D {
            count += abSum[-(c + d)]
        }
    }
    return count
}

// ── Largest number of K-sum pairs ─────────────────────────
func maxOperations(nums []int, k int) int {
    freq := make(map[int]int)
    for _, n := range nums { freq[n]++ }
    ops := 0
    for n, c := range freq {
        comp := k - n
        if comp == n {
            ops += c / 2
        } else if freq[comp] > 0 {
            pairs := c
            if freq[comp] < pairs { pairs = freq[comp] }
            ops += pairs
            freq[comp] = 0
            freq[n]  = 0
        }
    }
    return ops
}

// ── Jewels and stones ─────────────────────────────────────
func numJewelsInStones(jewels, stones string) int {
    set := make(map[rune]bool)
    for _, j := range jewels { set[j] = true }
    count := 0
    for _, s := range stones { if set[s] { count++ } }
    return count
}

func main() {
    fmt.Println(topKFrequent([]int{1,1,1,2,2,3}, 2))  // [1 2]
    fmt.Println(findMaxLength([]int{0,1,0,0,1,1,0}))   // 6
    fmt.Println(subarraySum([]int{1,1,1}, 2))           // 2
    fmt.Println(canConstruct("aa", "aab"))              // true
    fmt.Println(numJewelsInStones("aA", "aAAbbbb"))     // 3
    fmt.Println(fourSumCount(
        []int{1,2}, []int{-2,-1}, []int{-1,2}, []int{0,2})) // 2

    words := []string{"eat","tea","tan","ate","nat","bat"}
    groups := groupAnagramsFromAbove(words)
    for _, g := range groups { sort.Strings(g); fmt.Println(g) }
}

// placeholder — already defined above in grouping example
func groupAnagramsFromAbove(words []string) [][]string {
    groups := make(map[string][]string)
    for _, w := range words {
        b := []byte(w); sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
        key := string(b)
        groups[key] = append(groups[key], w)
    }
    result := make([][]string, 0, len(groups))
    for _, g := range groups { result = append(result, g) }
    return result
}

package main

import "fmt"

// ── Template: count subarrays where f(sum) is true ────────
//
//  freq := map[int]int{identity: 1}  // seed for subarrays starting at 0
//  sum, count := 0, 0
//  for _, n := range nums {
//      sum = transform(sum, n)        // update running aggregate
//      count += freq[sum - target]    // how many earlier prefixes match
//      freq[sum]++                    // record this prefix
//  }

// ── Subarray sum equals K ──────────────────────────────────
func subarraySumK(nums []int, k int) int {
    freq := map[int]int{0: 1}
    sum, count := 0, 0
    for _, n := range nums {
        sum += n
        count += freq[sum-k]
        freq[sum]++
    }
    return count
}

// ── Subarray sum divisible by K ───────────────────────────
// Two subarrays have same (sum % k) → their difference is divisible by k
func subarraysDivByK(nums []int, k int) int {
    freq := map[int]int{0: 1}
    sum, count := 0, 0
    for _, n := range nums {
        sum += n
        mod := ((sum % k) + k) % k // handle negative modulo
        count += freq[mod]
        freq[mod]++
    }
    return count
}

// ── Longest subarray with sum 0 ───────────────────────────
func longestSubarraySumZero(nums []int) int {
    firstSeen := map[int]int{0: -1}
    sum, maxLen := 0, 0
    for i, n := range nums {
        sum += n
        if j, ok := firstSeen[sum]; ok {
            if l := i - j; l > maxLen { maxLen = l }
        } else {
            firstSeen[sum] = i // only store FIRST occurrence
        }
    }
    return maxLen
}

// ── Count subarrays with odd sum ─────────────────────────
// Odd sum = prefix sums have different parity at endpoints
func numOfSubarrays(nums []int) int {
    const mod = 1_000_000_007
    odd, even, sum, count := 0, 1, 0, 0 // even starts at 1 (empty prefix)
    for _, n := range nums {
        sum += n
        if sum%2 == 0 {
            count = (count + odd) % mod
            even++
        } else {
            count = (count + even) % mod
            odd++
        }
    }
    return count
}

// ── Binary array: longest subarray with equal 0s and 1s ───
// Map 0→-1, find longest subarray with sum 0
func findMaxLengthBinary(nums []int) int {
    firstSeen := map[int]int{0: -1}
    sum, maxLen := 0, 0
    for i, n := range nums {
        if n == 0 { sum-- } else { sum++ }
        if j, ok := firstSeen[sum]; ok {
            if l := i - j; l > maxLen { maxLen = l }
        } else {
            firstSeen[sum] = i
        }
    }
    return maxLen
}

// ── Path sum equals target (tree, prefix sum + map) ───────
// Extends the 1D pattern to binary trees via DFS
type TreeNode struct{ Val int; Left, Right *TreeNode }

func pathSum(root *TreeNode, target int) int {
    freq := map[int]int{0: 1}
    var dfs func(node *TreeNode, curr int) int
    dfs = func(node *TreeNode, curr int) int {
        if node == nil { return 0 }
        curr += node.Val
        count := freq[curr-target]   // subarrays ending here with sum=target
        freq[curr]++
        count += dfs(node.Left, curr) + dfs(node.Right, curr)
        freq[curr]--                 // backtrack
        return count
    }
    return dfs(root, 0)
}

func main() {
    fmt.Println(subarraySumK([]int{1, 2, 3}, 3))              // 2
    fmt.Println(subarraySumK([]int{1, 1, 1}, 2))              // 2
    fmt.Println(subarraysDivByK([]int{4,5,0,-2,-3,1}, 5))     // 7
    fmt.Println(longestSubarraySumZero([]int{1,-1,3,-3,2}))    // 4
    fmt.Println(findMaxLengthBinary([]int{0,1,0,0,1,1,0}))     // 6
}

package main

import "fmt"

// ── Happy number ──────────────────────────────────────────
// Repeatedly sum squares of digits — happy if reaches 1, else cycles
func isHappy(n int) bool {
    seen := make(map[int]bool)
    for n != 1 {
        if seen[n] { return false }
        seen[n] = true
        n = sumOfSquares(n)
    }
    return true
}

func sumOfSquares(n int) int {
    sum := 0
    for n > 0 { d := n % 10; sum += d * d; n /= 10 }
    return sum
}

// Floyd's cycle variant — O(1) space (no set needed)
func isHappyFloyd(n int) bool {
    slow, fast := n, sumOfSquares(n)
    for fast != 1 && slow != fast {
        slow = sumOfSquares(slow)
        fast = sumOfSquares(sumOfSquares(fast))
    }
    return fast == 1
}

// ── Longest consecutive sequence ─────────────────────────
// O(n) using set: only start counting from sequence beginnings
func longestConsecutive(nums []int) int {
    set := make(map[int]bool)
    for _, n := range nums { set[n] = true }
    maxLen := 0
    for n := range set {
        if !set[n-1] { // n is start of a sequence
            length := 1
            for set[n+length] { length++ }
            if length > maxLen { maxLen = length }
        }
    }
    return maxLen
}

// ── Destination city ──────────────────────────────────────
// Find the city that is never a source (only a destination)
func destCity(paths [][]string) string {
    sources := make(map[string]bool)
    for _, p := range paths { sources[p[0]] = true }
    for _, p := range paths {
        if !sources[p[1]] { return p[1] }
    }
    return ""
}

// ── Unique number of occurrences ──────────────────────────
// True if all occurrence counts are distinct
func uniqueOccurrences(arr []int) bool {
    freq := make(map[int]int)
    for _, n := range arr { freq[n]++ }
    seen := make(map[int]bool)
    for _, c := range freq {
        if seen[c] { return false }
        seen[c] = true
    }
    return true
}

// ── Intersection of two arrays ────────────────────────────
func intersection(a, b []int) []int {
    setA := make(map[int]bool)
    for _, v := range a { setA[v] = true }
    seen := make(map[int]bool)
    var result []int
    for _, v := range b {
        if setA[v] && !seen[v] {
            result = append(result, v)
            seen[v] = true
        }
    }
    return result
}

// ── Find duplicate in array of N+1 integers [1..N] ────────
// Without modifying the array, O(1) space: Floyd on array-as-graph
func findDuplicate(nums []int) int {
    slow, fast := nums[0], nums[nums[0]]
    for slow != fast {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

func main() {
    fmt.Println(isHappy(19))                                     // true
    fmt.Println(isHappyFloyd(19))                                // true
    fmt.Println(longestConsecutive([]int{100,4,200,1,3,2}))     // 4 (1-2-3-4)
    fmt.Println(longestConsecutive([]int{0,3,7,2,5,8,4,6,0,1})) // 9
    fmt.Println(destCity([][]string{{"B","C"},{"D","B"},{"A","D"}})) // "C"
    fmt.Println(uniqueOccurrences([]int{1, 2, 2, 1, 1, 3}))     // true
    fmt.Println(intersection([]int{1,2,2,1}, []int{2,2}))        // [2]
    fmt.Println(findDuplicate([]int{1, 3, 4, 2, 2}))             // 2
}

package main

import "fmt"

// ── 1D Prefix Sum ─────────────────────────────────────────
func buildPrefix(nums []int) []int {
    prefix := make([]int, len(nums)+1) // prefix[0] = 0 sentinel
    for i, v := range nums {
        prefix[i+1] = prefix[i] + v
    }
    return prefix
}

// Range sum [l, r] inclusive — O(1)
func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

// ── Subarray Sum Equals K ─────────────────────────────────
// Count subarrays whose sum == k  →  O(n) with prefix+hashmap
func subarraySum(nums []int, k int) int {
    count := 0
    sum := 0
    freq := map[int]int{0: 1} // sum→count; seed 0 for subarrays from index 0
    for _, n := range nums {
        sum += n
        count += freq[sum-k] // how many times (sum-k) appeared before
        freq[sum]++
    }
    return count
}

// ── Subarray Sum Divisible by K ───────────────────────────
func subarraySumDivK(nums []int, k int) int {
    count, sum := 0, 0
    rem := map[int]int{0: 1}
    for _, n := range nums {
        sum += n
        mod := ((sum % k) + k) % k // handle negative
        count += rem[mod]
        rem[mod]++
    }
    return count
}

// ── 2D Prefix Sum (matrix range queries) ─────────────────
func build2DPrefix(matrix [][]int) [][]int {
    m, n := len(matrix), len(matrix[0])
    p := make([][]int, m+1)
    for i := range p { p[i] = make([]int, n+1) }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            p[i][j] = matrix[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
        }
    }
    return p
}

// Sum of submatrix (r1,c1) to (r2,c2) inclusive
func matrixRangeSum(p [][]int, r1, c1, r2, c2 int) int {
    return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
}

func main() {
    nums := []int{1, 2, 3, 4, 5}
    pre := buildPrefix(nums)
    fmt.Println(rangeSum(pre, 1, 3)) // 2+3+4 = 9
    fmt.Println(rangeSum(pre, 0, 4)) // 15

    fmt.Println(subarraySum([]int{1, 1, 1}, 2))              // 2
    fmt.Println(subarraySum([]int{1, 2, 3, -1, 1, 2}, 3))    // 3

    fmt.Println(subarraySumDivK([]int{4, 5, 0, -2, -3, 1}, 5)) // 7

    matrix := [][]int{{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}}
    p2 := build2DPrefix(matrix)
    fmt.Println(matrixRangeSum(p2, 2, 1, 4, 3)) // 8
}

package main

import "fmt"

// Max subarray sum
func maxSubArray(nums []int) int {
    maxSum, curr := nums[0], nums[0]
    for _, n := range nums[1:] {
        if curr < 0 { curr = 0 } // reset: starting fresh is better
        curr += n
        if curr > maxSum { maxSum = curr }
    }
    return maxSum
}

// Max subarray sum — with indices (track start/end)
func maxSubArrayIdx(nums []int) (int, int, int) {
    maxSum, curr := nums[0], nums[0]
    start, end, tempStart := 0, 0, 0
    for i := 1; i < len(nums); i++ {
        if curr < 0 { curr = 0; tempStart = i }
        curr += nums[i]
        if curr > maxSum {
            maxSum = curr
            start, end = tempStart, i
        }
    }
    return maxSum, start, end
}

// Max product subarray (handle negatives with two passes)
func maxProduct(nums []int) int {
    maxP, minP, result := nums[0], nums[0], nums[0]
    for _, n := range nums[1:] {
        if n < 0 { maxP, minP = minP, maxP } // swap: negative flips max/min
        if n > maxP*1 { maxP = n } else { maxP = maxP * n } // simplified:
        maxP = max(n, maxP*n) // max of: start fresh OR extend
        minP = min(n, minP*n) // track min for future negative flip
        if maxP > result { result = maxP }
    }
    return result
}

// Cleaner max product
func maxProductClean(nums []int) int {
    maxP, minP, res := nums[0], nums[0], nums[0]
    for _, n := range nums[1:] {
        maxP, minP = max(n, max(maxP*n, minP*n)), min(n, min(maxP*n, minP*n))
        if maxP > res { res = maxP }
    }
    return res
}

// Circular subarray max (Kadane + total-minSubarray)
func maxSubarrayCircular(nums []int) int {
    // Case 1: normal Kadane
    maxSum, minSum := nums[0], nums[0]
    currMax, currMin, total := nums[0], nums[0], nums[0]
    for _, n := range nums[1:] {
        total += n
        currMax = max(n, currMax+n)
        currMin = min(n, currMin+n)
        if currMax > maxSum { maxSum = currMax }
        if currMin < minSum { minSum = currMin }
    }
    // Case 2: wrap-around = total - minSubarray
    // Edge: if all negative, wrap would give 0 (empty), return maxSum
    if maxSum < 0 { return maxSum }
    if wrap := total - minSum; wrap > maxSum { return wrap }
    return maxSum
}

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

func main() {
    fmt.Println(maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})) // 6
    sum, s, e := maxSubArrayIdx([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})
    fmt.Printf("sum=%d idx=[%d,%d]\n", sum, s, e) // sum=6 idx=[3,6]
    fmt.Println(maxProductClean([]int{2, 3, -2, 4})) // 6
    fmt.Println(maxSubarrayCircular([]int{1, -2, 3, -2})) // 3
    fmt.Println(maxSubarrayCircular([]int{5, -3, 5}))     // 10 (wrap)
}

package main

import "fmt"

// Sort Colors — LeetCode 75
// Invariants: nums[0..lo-1]=0, nums[lo..mid-1]=1, nums[hi+1..n-1]=2
func sortColors(nums []int) {
    lo, mid, hi := 0, 0, len(nums)-1
    for mid <= hi {
        switch nums[mid] {
        case 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo++; mid++
        case 1:
            mid++ // already in place
        case 2:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi-- // don't mid++ — swapped element not yet examined
        }
    }
}

// General 3-way partition around pivot value
func threeWayPartition(nums []int, pivot int) []int {
    lo, mid, hi := 0, 0, len(nums)-1
    for mid <= hi {
        switch {
        case nums[mid] < pivot:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo++; mid++
        case nums[mid] == pivot:
            mid++
        default:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi--
        }
    }
    return nums
}

// Move Zeros to end (2-way partition, stable)
func moveZeroes(nums []int) {
    writeIdx := 0
    for _, n := range nums {
        if n != 0 { nums[writeIdx] = n; writeIdx++ }
    }
    for writeIdx < len(nums) { nums[writeIdx] = 0; writeIdx++ }
}

// Partition array: negatives left, non-negatives right (2-way)
func partition(nums []int) []int {
    l, r := 0, len(nums)-1
    for l < r {
        for l < r && nums[l] < 0  { l++ }
        for l < r && nums[r] >= 0 { r-- }
        if l < r { nums[l], nums[r] = nums[r], nums[l] }
    }
    return nums
}

func main() {
    c := []int{2, 0, 2, 1, 1, 0}
    sortColors(c)
    fmt.Println(c) // [0 0 1 1 2 2]

    nums := []int{3, 1, 4, 1, 5, 9, 2, 6, 5}
    fmt.Println(threeWayPartition(nums, 4)) // all <4 | 4s | all >4

    z := []int{0, 1, 0, 3, 12}
    moveZeroes(z)
    fmt.Println(z) // [1 3 12 0 0]
}

package main

import (
    "fmt"
    "sort"
)

type Interval [2]int

// Merge overlapping intervals
func merge(intervals []Interval) []Interval {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    result := []Interval{intervals[0]}
    for _, curr := range intervals[1:] {
        last := &result[len(result)-1]
        if curr[0] <= last[1] { // overlap
            if curr[1] > last[1] { last[1] = curr[1] } // extend
        } else {
            result = append(result, curr)
        }
    }
    return result
}

// Insert interval into sorted non-overlapping list
func insert(intervals []Interval, newInterval Interval) []Interval {
    result := []Interval{}
    i := 0
    // Add all intervals that end before new one starts
    for i < len(intervals) && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i]); i++
    }
    // Merge all overlapping intervals
    for i < len(intervals) && intervals[i][0] <= newInterval[1] {
        if intervals[i][0] < newInterval[0] { newInterval[0] = intervals[i][0] }
        if intervals[i][1] > newInterval[1] { newInterval[1] = intervals[i][1] }
        i++
    }
    result = append(result, newInterval)
    // Add remaining
    result = append(result, intervals[i:]...)
    return result
}

// Meeting rooms — can attend all? (no overlap)
func canAttendMeetings(intervals []Interval) bool {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[i-1][1] { return false }
    }
    return true
}

// Meeting rooms II — min rooms needed (sweep line / min-heap)
func minMeetingRooms(intervals []Interval) int {
    if len(intervals) == 0 { return 0 }
    starts := make([]int, len(intervals))
    ends   := make([]int, len(intervals))
    for i, iv := range intervals { starts[i], ends[i] = iv[0], iv[1] }
    sort.Ints(starts); sort.Ints(ends)

    rooms, endPtr := 0, 0
    for i := range starts {
        if starts[i] < ends[endPtr] {
            rooms++ // new room needed
        } else {
            endPtr++ // reuse a room
        }
    }
    return rooms
}

func main() {
    ivs := []Interval{{1,3},{2,6},{8,10},{15,18}}
    fmt.Println(merge(ivs)) // [[1 6] [8 10] [15 18]]

    ivs2 := []Interval{{1,2},{3,5},{6,7},{8,10},{12,16}}
    fmt.Println(insert(ivs2, Interval{4, 8})) // [[1 2] [3 10] [12 16]]

    meetings := []Interval{{0,30},{5,10},{15,20}}
    fmt.Println(canAttendMeetings(meetings))  // false
    fmt.Println(minMeetingRooms(meetings))    // 2
}

package main

import "fmt"

// No division, O(1) extra space (output array doesn't count)
// Left pass: result[i] = product of all elements left of i
// Right pass: multiply in product of all elements right of i
func productExceptSelf(nums []int) []int {
    n := len(nums)
    result := make([]int, n)

    // Left products
    result[0] = 1
    for i := 1; i < n; i++ {
        result[i] = result[i-1] * nums[i-1]
    }

    // Right products — running right multiplier
    right := 1
    for i := n - 1; i >= 0; i-- {
        result[i] *= right
        right *= nums[i]
    }
    return result
}

// Variant: handle zeros — count zeros, then build answer
func productExceptSelfWithZeros(nums []int) []int {
    total, zeros := 1, 0
    for _, n := range nums {
        if n == 0 { zeros++ } else { total *= n }
    }
    result := make([]int, len(nums))
    for i, n := range nums {
        switch zeros {
        case 0: result[i] = total / n
        case 1:
            if n == 0 { result[i] = total }
        // zeros >= 2: all stay 0
        }
    }
    return result
}

func main() {
    fmt.Println(productExceptSelf([]int{1, 2, 3, 4}))      // [24 12 8 6]
    fmt.Println(productExceptSelf([]int{-1, 1, 0, -3, 3})) // [0 0 9 0 0]
}

package main

import "fmt"

// Two-pointer approach: O(n) time, O(1) space
// Water at position i = min(maxLeft, maxRight) - height[i]
// Move pointer from the side with smaller max height
func trap(height []int) int {
    l, r := 0, len(height)-1
    maxL, maxR := 0, 0
    water := 0
    for l < r {
        if height[l] < height[r] {
            if height[l] >= maxL { maxL = height[l] } else { water += maxL - height[l] }
            l++
        } else {
            if height[r] >= maxR { maxR = height[r] } else { water += maxR - height[r] }
            r--
        }
    }
    return water
}

// Prefix max approach (easier to understand, O(n) space)
func trapWithArrays(height []int) int {
    n := len(height)
    maxL, maxR := make([]int, n), make([]int, n)
    maxL[0] = height[0]
    for i := 1; i < n; i++ {
        if height[i] > maxL[i-1] { maxL[i] = height[i] } else { maxL[i] = maxL[i-1] }
    }
    maxR[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        if height[i] > maxR[i+1] { maxR[i] = height[i] } else { maxR[i] = maxR[i+1] }
    }
    water := 0
    for i := 0; i < n; i++ {
        waterLevel := maxL[i]; if maxR[i] < waterLevel { waterLevel = maxR[i] }
        if diff := waterLevel - height[i]; diff > 0 { water += diff }
    }
    return water
}

func main() {
    fmt.Println(trap([]int{0,1,0,2,1,0,1,3,2,1,2,1})) // 6
    fmt.Println(trap([]int{4,2,0,3,2,5}))               // 9
}

package main

import "fmt"

// Jump Game I — can reach last index?
// Greedy: track the furthest reachable index
func canJump(nums []int) bool {
    maxReach := 0
    for i, n := range nums {
        if i > maxReach { return false } // can't reach index i
        if i+n > maxReach { maxReach = i + n }
    }
    return true
}

// Jump Game II — minimum jumps to reach last index
// Greedy: at each "jump boundary", take the jump that reaches farthest
func jump(nums []int) int {
    jumps, currEnd, farthest := 0, 0, 0
    for i := 0; i < len(nums)-1; i++ {
        if i+nums[i] > farthest { farthest = i + nums[i] }
        if i == currEnd { // must jump here
            jumps++
            currEnd = farthest
        }
    }
    return jumps
}

// Jump Game III — can reach index with value 0?
// BFS from start, jump ±nums[i]
func canReachZero(arr []int, start int) bool {
    visited := make([]bool, len(arr))
    queue := []int{start}
    for len(queue) > 0 {
        i := queue[0]; queue = queue[1:]
        if arr[i] == 0 { return true }
        if visited[i] { continue }
        visited[i] = true
        if l := i - arr[i]; l >= 0 && !visited[l] { queue = append(queue, l) }
        if r := i + arr[i]; r < len(arr) && !visited[r] { queue = append(queue, r) }
    }
    return false
}

func main() {
    fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
    fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
    fmt.Println(jump([]int{2, 3, 1, 1, 4}))    // 2
    fmt.Println(jump([]int{2, 3, 0, 1, 4}))    // 2
    fmt.Println(canReachZero([]int{4,2,3,0,3,1,2}, 5)) // true
}

package main

import "fmt"

// Rotate NxN matrix 90° clockwise in-place
// Step 1: Transpose (swap [i][j] with [j][i])
// Step 2: Reverse each row
func rotate(matrix [][]int) {
    n := len(matrix)
    // Transpose
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    // Reverse each row
    for i := 0; i < n; i++ {
        for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
            matrix[i][l], matrix[i][r] = matrix[i][r], matrix[i][l]
        }
    }
}

// 90° counter-clockwise: reverse each row first, then transpose

// Set matrix zeroes — if cell is 0, set its row+col to 0
// O(1) space: use first row/col as flags
func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    firstRowZero, firstColZero := false, false
    for j := 0; j < n; j++ { if matrix[0][j] == 0 { firstRowZero = true } }
    for i := 0; i < m; i++ { if matrix[i][0] == 0 { firstColZero = true } }
    // Use first row/col to mark
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 { matrix[i][0] = 0; matrix[0][j] = 0 }
        }
    }
    for i := 1; i < m; i++ { if matrix[i][0] == 0 { for j := 1; j < n; j++ { matrix[i][j] = 0 } } }
    for j := 1; j < n; j++ { if matrix[0][j] == 0 { for i := 1; i < m; i++ { matrix[i][j] = 0 } } }
    if firstRowZero { for j := 0; j < n; j++ { matrix[0][j] = 0 } }
    if firstColZero { for i := 0; i < m; i++ { matrix[i][0] = 0 } }
}

// Spiral order traversal
func spiralOrder(matrix [][]int) []int {
    result := []int{}
    top, bottom, left, right := 0, len(matrix)-1, 0, len(matrix[0])-1
    for top <= bottom && left <= right {
        for j := left; j <= right; j++  { result = append(result, matrix[top][j]) };    top++
        for i := top; i <= bottom; i++  { result = append(result, matrix[i][right]) };  right--
        if top <= bottom {
            for j := right; j >= left; j-- { result = append(result, matrix[bottom][j]) }; bottom--
        }
        if left <= right {
            for i := bottom; i >= top; i-- { result = append(result, matrix[i][left]) };  left++
        }
    }
    return result
}

// Search in sorted matrix (each row sorted, first of row > last of prev)
// Treat as flat 1D sorted array — binary search
func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    lo, hi := 0, m*n-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        val := matrix[mid/n][mid%n]
        switch {
        case val == target: return true
        case val < target:  lo = mid + 1
        default:            hi = mid - 1
        }
    }
    return false
}

func main() {
    m := [][]int{{1,2,3},{4,5,6},{7,8,9}}
    rotate(m)
    fmt.Println(m) // [[7 4 1] [8 5 2] [9 6 3]]

    m2 := [][]int{{1,2,3},{4,5,6},{7,8,9}}
    fmt.Println(spiralOrder(m2)) // [1 2 3 6 9 8 7 4 5]

    m3 := [][]int{{1,3,5,7},{10,11,16,20},{23,30,34,60}}
    fmt.Println(searchMatrix(m3, 3))  // true
    fmt.Println(searchMatrix(m3, 13)) // false
}

package main

import "fmt"

// Next Permutation (lexicographically next)
// Algorithm: find rightmost ascent, swap with next-larger, reverse suffix
func nextPermutation(nums []int) {
    n := len(nums)
    // Step 1: find rightmost i where nums[i] < nums[i+1]
    i := n - 2
    for i >= 0 && nums[i] >= nums[i+1] { i-- }

    if i >= 0 {
        // Step 2: find rightmost j > i where nums[j] > nums[i]
        j := n - 1
        for nums[j] <= nums[i] { j-- }
        nums[i], nums[j] = nums[j], nums[i]
    }
    // Step 3: reverse suffix after i
    for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
        nums[l], nums[r] = nums[r], nums[l]
    }
}

// Cyclic Sort — for arrays with values in range [1..n] or [0..n-1]
// Place each number at its correct index in O(n) time
func cyclicSort(nums []int) {
    i := 0
    for i < len(nums) {
        correct := nums[i] - 1 // expected index for value nums[i] (1-indexed)
        if nums[i] != nums[correct] {
            nums[i], nums[correct] = nums[correct], nums[i]
        } else {
            i++
        }
    }
}

// Find missing number using cyclic sort (values 1..n, one missing)
func findMissingNumber(nums []int) int {
    cyclicSort(nums)
    for i, n := range nums {
        if n != i+1 { return i + 1 }
    }
    return len(nums) + 1
}

// Find all duplicates (values 1..n, each appears once or twice)
func findDuplicates(nums []int) []int {
    cyclicSort(nums)
    var result []int
    for i, n := range nums {
        if n != i+1 { result = append(result, n) }
    }
    return result
}

// All permutations (backtracking)
func permutations(nums []int) [][]int {
    var result [][]int
    var backtrack func(start int)
    backtrack = func(start int) {
        if start == len(nums) {
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            result = append(result, tmp)
            return
        }
        for i := start; i < len(nums); i++ {
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
        }
    }
    backtrack(0)
    return result
}

func main() {
    n := []int{1, 2, 3}
    nextPermutation(n); fmt.Println(n) // [1 3 2]
    nextPermutation(n); fmt.Println(n) // [2 1 3]

    s := []int{3, 2, 1}
    nextPermutation(s); fmt.Println(s) // [1 2 3] — wraps around

    nums := []int{3, 1, 4, 2, 5}
    cyclicSort(nums)
    fmt.Println(nums) // [1 2 3 4 5]

    fmt.Println(findMissingNumber([]int{3, 0, 1}))        // 2  (0-indexed variant)
    fmt.Println(findDuplicates([]int{4, 3, 2, 7, 8, 2, 3, 1})) // [2 3]

    fmt.Println(permutations([]int{1, 2, 3})) // all 6 permutations
}

package main

import "fmt"

// Boyer-Moore Voting — majority element (appears > n/2 times)
func majorityElement(nums []int) int {
    candidate, count := nums[0], 1
    for _, n := range nums[1:] {
        if count == 0 { candidate = n }
        if n == candidate { count++ } else { count-- }
    }
    return candidate // guaranteed to exist per problem constraint
}

// Majority Element II — all elements > n/3 (at most 2 candidates)
func majorityElementII(nums []int) []int {
    c1, c2, cnt1, cnt2 := 0, 1, 0, 0 // c2=1 ensures c1 != c2 initially
    for _, n := range nums {
        switch {
        case n == c1: cnt1++
        case n == c2: cnt2++
        case cnt1 == 0: c1, cnt1 = n, 1
        case cnt2 == 0: c2, cnt2 = n, 1
        default: cnt1--; cnt2--
        }
    }
    var result []int
    cnt1, cnt2 = 0, 0
    for _, n := range nums { if n == c1 { cnt1++ } else if n == c2 { cnt2++ } }
    if cnt1 > len(nums)/3 { result = append(result, c1) }
    if cnt2 > len(nums)/3 { result = append(result, c2) }
    return result
}

// Rotate array right by k positions — reversal trick
func rotateRight(nums []int, k int) {
    n := len(nums)
    k %= n
    reverse := func(l, r int) {
        for l < r { nums[l], nums[r] = nums[r], nums[l]; l++; r-- }
    }
    reverse(0, n-1)   // reverse all
    reverse(0, k-1)   // reverse first k
    reverse(k, n-1)   // reverse rest
}

// Find duplicate in array [1..n] — Floyd's cycle detection on array
// Treat array as linked list: index → value → index → ...
func findDuplicate(nums []int) int {
    slow, fast := nums[0], nums[nums[0]]
    for slow != fast {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

// H-Index — max h such that h papers have >= h citations
func hIndex(citations []int) int {
    n := len(citations)
    bucket := make([]int, n+1)
    for _, c := range citations {
        if c >= n { bucket[n]++ } else { bucket[c]++ }
    }
    total := 0
    for h := n; h >= 0; h-- {
        total += bucket[h]
        if total >= h { return h }
    }
    return 0
}

// Smallest missing positive integer — O(n) time, O(1) space
// Key: answer is in [1, n+1]; use the array itself as a hash
func firstMissingPositive(nums []int) int {
    n := len(nums)
    // Place each nums[i] at index nums[i]-1 if in range [1..n]
    for i := 0; i < n; {
        j := nums[i] - 1
        if j >= 0 && j < n && nums[j] != nums[i] {
            nums[i], nums[j] = nums[j], nums[i]
        } else {
            i++
        }
    }
    for i, v := range nums {
        if v != i+1 { return i + 1 }
    }
    return n + 1
}

func main() {
    fmt.Println(majorityElement([]int{3,2,3}))             // 3
    fmt.Println(majorityElement([]int{2,2,1,1,1,2,2}))     // 2
    fmt.Println(majorityElementII([]int{3,2,3}))            // [3]
    fmt.Println(majorityElementII([]int{1,1,1,3,3,2,2,2})) // [1 2]

    arr := []int{1, 2, 3, 4, 5, 6, 7}
    rotateRight(arr, 3)
    fmt.Println(arr) // [5 6 7 1 2 3 4]

    fmt.Println(findDuplicate([]int{1, 3, 4, 2, 2})) // 2
    fmt.Println(findDuplicate([]int{3, 1, 3, 4, 2})) // 3

    fmt.Println(hIndex([]int{3, 0, 6, 1, 5})) // 3

    fmt.Println(firstMissingPositive([]int{3, 4, -1, 1})) // 2
    fmt.Println(firstMissingPositive([]int{1, 2, 0}))     // 3
    fmt.Println(firstMissingPositive([]int{7, 8, 9, 11})) // 1
}

package main

import "fmt"

// ── Node ──────────────────────────────────────────────────
type DNode struct {
    Val        int
    Prev, Next *DNode
}

// ── Doubly Linked List with sentinel head/tail ────────────
// head ↔ [node1] ↔ [node2] ↔ ... ↔ tail
// Sentinels eliminate all nil-pointer edge cases
type DoublyLinkedList struct {
    head, tail *DNode
    size       int
}

func NewDLL() *DoublyLinkedList {
    head := &DNode{}
    tail := &DNode{}
    head.Next = tail
    tail.Prev = head
    return &DoublyLinkedList{head: head, tail: tail}
}

// insertAfter inserts node n immediately after node at
func (dl *DoublyLinkedList) insertAfter(at, n *DNode) {
    n.Prev = at
    n.Next = at.Next
    at.Next.Prev = n
    at.Next = n
    dl.size++
}

// remove detaches node n from the list
func (dl *DoublyLinkedList) remove(n *DNode) {
    n.Prev.Next = n.Next
    n.Next.Prev = n.Prev
    n.Prev = nil // help GC
    n.Next = nil
    dl.size--
}

// AddFront inserts a new node at the front (after head sentinel)
func (dl *DoublyLinkedList) AddFront(val int) *DNode {
    n := &DNode{Val: val}
    dl.insertAfter(dl.head, n)
    return n
}

// AddBack inserts a new node at the back (before tail sentinel)
func (dl *DoublyLinkedList) AddBack(val int) *DNode {
    n := &DNode{Val: val}
    dl.insertAfter(dl.tail.Prev, n)
    return n
}

// RemoveFront removes and returns the front node (nil if empty)
func (dl *DoublyLinkedList) RemoveFront() *DNode {
    if dl.size == 0 { return nil }
    n := dl.head.Next
    dl.remove(n)
    return n
}

// RemoveBack removes and returns the back node (nil if empty)
func (dl *DoublyLinkedList) RemoveBack() *DNode {
    if dl.size == 0 { return nil }
    n := dl.tail.Prev
    dl.remove(n)
    return n
}

// MoveToFront moves an existing node to the front
func (dl *DoublyLinkedList) MoveToFront(n *DNode) {
    dl.remove(n)
    dl.size++ // remove decremented, insertAfter will increment
    dl.insertAfter(dl.head, n)
}

// Front / Back peek
func (dl *DoublyLinkedList) Front() *DNode {
    if dl.size == 0 { return nil }
    return dl.head.Next
}

func (dl *DoublyLinkedList) Back() *DNode {
    if dl.size == 0 { return nil }
    return dl.tail.Prev
}

func (dl *DoublyLinkedList) Len() int { return dl.size }

// Print traverses forward
func (dl *DoublyLinkedList) Print() {
    for n := dl.head.Next; n != dl.tail; n = n.Next {
        fmt.Printf("%d ", n.Val)
    }
    fmt.Println()
}

// PrintReverse traverses backward
func (dl *DoublyLinkedList) PrintReverse() {
    for n := dl.tail.Prev; n != dl.head; n = n.Prev {
        fmt.Printf("%d ", n.Val)
    }
    fmt.Println()
}

func dllDemo() {
    dl := NewDLL()
    dl.AddBack(1)
    dl.AddBack(2)
    dl.AddBack(3)
    n := dl.AddFront(0)

    dl.Print()        // 0 1 2 3
    dl.PrintReverse() // 3 2 1 0

    dl.MoveToFront(dl.Back()) // move 3 to front
    dl.Print()        // 3 0 1 2

    dl.remove(n)      // remove node with val=0
    dl.Print()        // 3 1 2

    fmt.Println("len:", dl.Len()) // 3
    fmt.Println("front:", dl.Front().Val) // 3
    fmt.Println("back:",  dl.Back().Val)  // 2
}

package main

import "fmt"

// ── LRU Cache Node ────────────────────────────────────────
type LRUNode struct {
    key, val   int
    prev, next *LRUNode
}

// ── LRU Cache ─────────────────────────────────────────────
type LRUCache struct {
    capacity int
    cache    map[int]*LRUNode // key → node (O(1) lookup)
    head     *LRUNode         // MRU end (most recently used)
    tail     *LRUNode         // LRU end (least recently used)
}

func NewLRUCache(capacity int) *LRUCache {
    head := &LRUNode{} // sentinel
    tail := &LRUNode{} // sentinel
    head.next = tail
    tail.prev = head
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*LRUNode),
        head:     head,
        tail:     tail,
    }
}

// insertFront places node right after head sentinel (MRU position)
func (c *LRUCache) insertFront(n *LRUNode) {
    n.prev = c.head
    n.next = c.head.next
    c.head.next.prev = n
    c.head.next = n
}

// removeNode detaches node from wherever it is
func (c *LRUCache) removeNode(n *LRUNode) {
    n.prev.next = n.next
    n.next.prev = n.prev
}

// Get returns the value for key, or -1 if not found.
// Moves accessed node to front (most recently used).
func (c *LRUCache) Get(key int) int {
    node, ok := c.cache[key]
    if !ok { return -1 }
    // Move to front — mark as most recently used
    c.removeNode(node)
    c.insertFront(node)
    return node.val
}

// Put inserts or updates key→val.
// Evicts the LRU entry (back of list) if over capacity.
func (c *LRUCache) Put(key, val int) {
    if node, ok := c.cache[key]; ok {
        // Update existing — move to front
        node.val = val
        c.removeNode(node)
        c.insertFront(node)
        return
    }
    // Evict LRU if at capacity
    if len(c.cache) == c.capacity {
        lru := c.tail.prev   // node just before tail sentinel
        c.removeNode(lru)
        delete(c.cache, lru.key)
    }
    // Insert new node at front
    node := &LRUNode{key: key, val: val}
    c.insertFront(node)
    c.cache[key] = node
}

func lruDemo() {
    cache := NewLRUCache(3)
    cache.Put(1, 10)
    cache.Put(2, 20)
    cache.Put(3, 30)
    fmt.Println(cache.Get(1))  // 10 — 1 moves to MRU
    cache.Put(4, 40)           // evicts 2 (LRU)
    fmt.Println(cache.Get(2))  // -1 (evicted)
    fmt.Println(cache.Get(3))  // 30
    fmt.Println(cache.Get(4))  // 40
    cache.Put(5, 50)           // evicts 1 (now LRU after 3 and 4 accessed)
    fmt.Println(cache.Get(1))  // -1 (evicted)
}

package main

import "fmt"

type LFUNode struct {
    key, val, freq int
    prev, next     *LFUNode
}

// freqList is a DLL for one frequency bucket
type freqList struct {
    head, tail *LFUNode
    size       int
}

func newFreqList() *freqList {
    h, t := &LFUNode{}, &LFUNode{}
    h.next = t; t.prev = h
    return &freqList{head: h, tail: t}
}

func (fl *freqList) addFront(n *LFUNode) {
    n.prev = fl.head; n.next = fl.head.next
    fl.head.next.prev = n; fl.head.next = n
    fl.size++
}

func (fl *freqList) remove(n *LFUNode) {
    n.prev.next = n.next; n.next.prev = n.prev
    fl.size--
}

func (fl *freqList) removeLast() *LFUNode {
    if fl.size == 0 { return nil }
    n := fl.tail.prev
    fl.remove(n)
    return n
}

// ── LFU Cache ─────────────────────────────────────────────
type LFUCache struct {
    capacity int
    minFreq  int
    keys     map[int]*LFUNode    // key  → node
    freqs    map[int]*freqList   // freq → DLL of nodes at that freq
}

func NewLFUCache(capacity int) *LFUCache {
    return &LFUCache{
        capacity: capacity,
        keys:     make(map[int]*LFUNode),
        freqs:    make(map[int]*freqList),
    }
}

func (c *LFUCache) promote(n *LFUNode) {
    oldFreq := n.freq
    c.freqs[oldFreq].remove(n)
    if c.freqs[oldFreq].size == 0 {
        delete(c.freqs, oldFreq)
        if c.minFreq == oldFreq { c.minFreq++ }
    }
    n.freq++
    if c.freqs[n.freq] == nil { c.freqs[n.freq] = newFreqList() }
    c.freqs[n.freq].addFront(n)
}

func (c *LFUCache) Get(key int) int {
    n, ok := c.keys[key]
    if !ok { return -1 }
    c.promote(n)
    return n.val
}

func (c *LFUCache) Put(key, val int) {
    if c.capacity == 0 { return }
    if n, ok := c.keys[key]; ok {
        n.val = val
        c.promote(n)
        return
    }
    if len(c.keys) == c.capacity {
        evicted := c.freqs[c.minFreq].removeLast()
        delete(c.keys, evicted.key)
    }
    n := &LFUNode{key: key, val: val, freq: 1}
    c.keys[key] = n
    if c.freqs[1] == nil { c.freqs[1] = newFreqList() }
    c.freqs[1].addFront(n)
    c.minFreq = 1
}

func lfuDemo() {
    cache := NewLFUCache(2)
    cache.Put(1, 1)
    cache.Put(2, 2)
    fmt.Println(cache.Get(1)) // 1  (freq[1]=2, freq[2]=1→ 2 is LFU)
    cache.Put(3, 3)           // evict key 2 (freq=1, LRU among freq-1)
    fmt.Println(cache.Get(2)) // -1 (evicted)
    fmt.Println(cache.Get(3)) // 3
    cache.Put(4, 4)           // evict key 3 (freq=1) — key 1 has freq=2
    fmt.Println(cache.Get(1)) // 1
    fmt.Println(cache.Get(3)) // -1 (evicted)
    fmt.Println(cache.Get(4)) // 4
}

func main() {
    dllDemo()
    fmt.Println("---")
    lruDemo()
    fmt.Println("---")
    lfuDemo()
}

package main

import "fmt"

// ── Template 1: Recursive DFS on graph ───────────────────
func dfsRecursive(graph [][]int, node int, visited []bool) {
    visited[node] = true
    fmt.Println("visit:", node)
    for _, nei := range graph[node] {
        if !visited[nei] {
            dfsRecursive(graph, nei, visited)
        }
    }
}

// ── Template 2: Iterative DFS (explicit stack) ────────────
// NOTE: iterative DFS visits in REVERSE order vs recursive
func dfsIterative(graph [][]int, start int) []int {
    n := len(graph)
    visited := make([]bool, n)
    stack := []int{start}
    var order []int
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if visited[node] { continue }
        visited[node] = true
        order = append(order, node)
        for _, nei := range graph[node] { // push all neighbours
            if !visited[nei] { stack = append(stack, nei) }
        }
    }
    return order
}

// ── Template 3: DFS returning a value (path sum) ─────────
type TreeNode struct{ Val int; Left, Right *TreeNode }

func hasPathSum(root *TreeNode, target int) bool {
    if root == nil { return false }
    target -= root.Val
    if root.Left == nil && root.Right == nil { return target == 0 } // leaf
    return hasPathSum(root.Left, target) || hasPathSum(root.Right, target)
}

// ── Template 4: DFS collecting all paths ─────────────────
func allPaths(root *TreeNode, target int) [][]int {
    var result [][]int
    var dfs func(node *TreeNode, remaining int, path []int)
    dfs = func(node *TreeNode, remaining int, path []int) {
        if node == nil { return }
        path = append(path, node.Val) // path is a copy here (append may allocate)
        remaining -= node.Val
        if node.Left == nil && node.Right == nil && remaining == 0 {
            tmp := make([]int, len(path))
            copy(tmp, path)          // MUST copy — path slice will be reused
            result = append(result, tmp)
            return
        }
        dfs(node.Left,  remaining, path)
        dfs(node.Right, remaining, path)
    }
    dfs(root, target, []int{})
    return result
}

// ── Template 5: DFS with state / global max ───────────────
func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 62
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil { return 0 }
        left  := max(0, dfs(node.Left))  // ignore negative subtrees
        right := max(0, dfs(node.Right))
        if path := node.Val + left + right; path > maxSum { maxSum = path }
        if left > right { return node.Val + left }; return node.Val + right
    }
    dfs(root)
    return maxSum
}

// ── Connected components count ────────────────────────────
func countComponents(n int, edges [][2]int) int {
    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])
    }
    visited := make([]bool, n)
    var dfs func(int)
    dfs = func(v int) {
        visited[v] = true
        for _, nei := range adj[v] { if !visited[nei] { dfs(nei) } }
    }
    count := 0
    for i := 0; i < n; i++ {
        if !visited[i] { dfs(i); count++ }
    }
    return count
}

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

func main() {
    graph := [][]int{{1,2},{0,3},{0,3},{1,2}}
    visited := make([]bool, 4)
    dfsRecursive(graph, 0, visited)
    fmt.Println(dfsIterative(graph, 0))

    root := &TreeNode{5,
        &TreeNode{4, &TreeNode{11, &TreeNode{7,nil,nil}, &TreeNode{2,nil,nil}}, nil},
        &TreeNode{8, &TreeNode{13,nil,nil}, &TreeNode{4,nil,&TreeNode{1,nil,nil}}}}
    fmt.Println(hasPathSum(root, 22))   // true (5→4→11→2)
    fmt.Println(allPaths(root, 22))     // [[5 4 11 2]]
    fmt.Println(maxPathSum(root))       // 48

    fmt.Println(countComponents(5, [][2]int{{0,1},{1,2},{3,4}})) // 2
}

package main

import "fmt"

// ── Template 1: Basic BFS — shortest path ─────────────────
func bfsShortestPath(graph [][]int, start, end int) int {
    visited := make([]bool, len(graph))
    visited[start] = true
    queue := []int{start}
    dist := 0
    for len(queue) > 0 {
        size := len(queue) // process entire level
        for i := 0; i < size; i++ {
            node := queue[i]
            if node == end { return dist }
            for _, nei := range graph[node] {
                if !visited[nei] {
                    visited[nei] = true
                    queue = append(queue, nei)
                }
            }
        }
        queue = queue[size:] // dequeue whole level
        dist++
    }
    return -1 // unreachable
}

// ── Template 2: BFS with distance map ─────────────────────
func bfsDistances(graph [][]int, start int) []int {
    dist := make([]int, len(graph))
    for i := range dist { dist[i] = -1 }
    dist[start] = 0
    queue := []int{start}
    for len(queue) > 0 {
        node := queue[0]; queue = queue[1:]
        for _, nei := range graph[node] {
            if dist[nei] == -1 {
                dist[nei] = dist[node] + 1
                queue = append(queue, nei)
            }
        }
    }
    return dist
}

// ── Template 3: Multi-source BFS ──────────────────────────
// Start BFS from multiple sources simultaneously
// Classic: 01 Matrix (distance to nearest 0), Rotting Oranges
func multiSourceBFS(grid [][]int) [][]int {
    m, n := len(grid), len(grid[0])
    dist := make([][]int, m)
    for i := range dist { dist[i] = make([]int, n); for j := range dist[i] { dist[i][j] = -1 } }
    queue := [][2]int{}
    // Seed all sources at distance 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 0 { dist[i][j] = 0; queue = append(queue, [2]int{i, j}) }
        }
    }
    dirs := [][2]int{{0,1},{0,-1},{1,0},{-1,0}}
    for len(queue) > 0 {
        cur := queue[0]; queue = queue[1:]
        for _, d := range dirs {
            r, c := cur[0]+d[0], cur[1]+d[1]
            if r >= 0 && r < m && c >= 0 && c < n && dist[r][c] == -1 {
                dist[r][c] = dist[cur[0]][cur[1]] + 1
                queue = append(queue, [2]int{r, c})
            }
        }
    }
    return dist
}

// ── Template 4: BFS on implicit graph (Word Ladder) ────────
// Shortest transformation sequence: "hit" → "cog"
func ladderLength(beginWord, endWord string, wordList []string) int {
    wordSet := make(map[string]bool)
    for _, w := range wordList { wordSet[w] = true }
    if !wordSet[endWord] { return 0 }

    queue := []string{beginWord}
    visited := map[string]bool{beginWord: true}
    steps := 1

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            word := queue[i]
            bs := []byte(word)
            for pos := 0; pos < len(bs); pos++ {
                orig := bs[pos]
                for c := byte('a'); c <= byte('z'); c++ {
                    if c == orig { continue }
                    bs[pos] = c
                    next := string(bs)
                    if next == endWord { return steps + 1 }
                    if wordSet[next] && !visited[next] {
                        visited[next] = true
                        queue = append(queue, next)
                    }
                    bs[pos] = orig
                }
            }
        }
        queue = queue[size:]
        steps++
    }
    return 0
}

// ── Template 5: 0-1 BFS (deque, edge weight 0 or 1) ───────
// Faster than Dijkstra when edges are only 0 or 1
func zeroOneBFS(graph [][2]int, n, src int, adj [][]struct{ to, w int }) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = 1<<62 }
    dist[src] = 0
    deque := []int{src} // front for w=0, back for w=1
    for len(deque) > 0 {
        u := deque[0]; deque = deque[1:]
        for _, e := range adj[u] {
            if nd := dist[u] + e.w; nd < dist[e.to] {
                dist[e.to] = nd
                if e.w == 0 { deque = append([]int{e.to}, deque...) } else { deque = append(deque, e.to) }
            }
        }
    }
    return dist
}

func main() {
    graph := [][]int{{1,2},{0,3},{0,3},{1,2,4},{3}}
    fmt.Println(bfsShortestPath(graph, 0, 4))  // 2
    fmt.Println(bfsDistances(graph, 0))         // [0 1 1 2 3]

    grid := [][]int{{0,0,0},{0,1,0},{1,1,1}}
    fmt.Println(multiSourceBFS(grid))           // distances from nearest 0

    words := []string{"hot","dot","dog","lot","log","cog"}
    fmt.Println(ladderLength("hit", "cog", words)) // 5
}

package main

import (
    "fmt"
    "sort"
)

// ── Subsets (no duplicates in input) ──────────────────────
func subsets(nums []int) [][]int {
    var result [][]int
    var backtrack func(start int, current []int)
    backtrack = func(start int, current []int) {
        tmp := make([]int, len(current))
        copy(tmp, current)
        result = append(result, tmp) // add at every node, not just leaves
        for i := start; i < len(nums); i++ {
            current = append(current, nums[i])
            backtrack(i+1, current)
            current = current[:len(current)-1] // undo
        }
    }
    backtrack(0, []int{})
    return result
}

// ── Subsets II (duplicates in input) ──────────────────────
func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums) // sort first to group duplicates
    var result [][]int
    var backtrack func(start int, current []int)
    backtrack = func(start int, current []int) {
        tmp := make([]int, len(current)); copy(tmp, current)
        result = append(result, tmp)
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] { continue } // skip duplicate
            current = append(current, nums[i])
            backtrack(i+1, current)
            current = current[:len(current)-1]
        }
    }
    backtrack(0, []int{})
    return result
}

// ── Combinations: choose k from n ─────────────────────────
func combine(n, k int) [][]int {
    var result [][]int
    var backtrack func(start int, current []int)
    backtrack = func(start int, current []int) {
        if len(current) == k {
            tmp := make([]int, k); copy(tmp, current)
            result = append(result, tmp); return
        }
        // Pruning: need (k - len(current)) more, so stop if not enough remain
        for i := start; i <= n-(k-len(current))+1; i++ {
            current = append(current, i)
            backtrack(i+1, current)
            current = current[:len(current)-1]
        }
    }
    backtrack(1, []int{})
    return result
}

// ── Combination Sum (unlimited reuse, unique candidates) ──
func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    var result [][]int
    var backtrack func(start, remaining int, current []int)
    backtrack = func(start, remaining int, current []int) {
        if remaining == 0 {
            tmp := make([]int, len(current)); copy(tmp, current)
            result = append(result, tmp); return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining { break } // pruning: sorted, so rest are bigger
            current = append(current, candidates[i])
            backtrack(i, remaining-candidates[i], current) // i (not i+1) = allow reuse
            current = current[:len(current)-1]
        }
    }
    backtrack(0, target, []int{})
    return result
}

// ── Permutations (no duplicates) ─────────────────────────
func permute(nums []int) [][]int {
    var result [][]int
    var backtrack func(start int)
    backtrack = func(start int) {
        if start == len(nums) {
            tmp := make([]int, len(nums)); copy(tmp, nums)
            result = append(result, tmp); return
        }
        for i := start; i < len(nums); i++ {
            nums[start], nums[i] = nums[i], nums[start] // swap in
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start] // swap out (undo)
        }
    }
    backtrack(0)
    return result
}

// ── Permutations II (with duplicates) ─────────────────────
func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    used := make([]bool, len(nums))
    var result [][]int
    var backtrack func(current []int)
    backtrack = func(current []int) {
        if len(current) == len(nums) {
            tmp := make([]int, len(current)); copy(tmp, current)
            result = append(result, tmp); return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] { continue }
            // Skip duplicate: same value, previous sibling not used
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue }
            used[i] = true
            backtrack(append(current, nums[i]))
            used[i] = false
        }
    }
    backtrack([]int{})
    return result
}

func main() {
    fmt.Println(len(subsets([]int{1,2,3})))          // 8
    fmt.Println(subsetsWithDup([]int{1,2,2}))         // 6 unique
    fmt.Println(combine(4, 2))                         // C(4,2) = 6
    fmt.Println(combinationSum([]int{2,3,6,7}, 7))    // [[2 2 3] [7]]
    fmt.Println(len(permute([]int{1,2,3})))            // 6
    fmt.Println(len(permuteUnique([]int{1,1,2})))      // 3
}

package main

import (
    "fmt"
    "strings"
)

// ── N-Queens ──────────────────────────────────────────────
func solveNQueens(n int) [][]string {
    var result [][]string
    board := make([][]byte, n)
    for i := range board { board[i] = []byte(strings.Repeat(".", n)) }

    cols := make([]bool, n)
    diag1 := make([]bool, 2*n) // row-col+n: top-left diagonals
    diag2 := make([]bool, 2*n) // row+col:   top-right diagonals

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            snapshot := make([]string, n)
            for i, r := range board { snapshot[i] = string(r) }
            result = append(result, snapshot)
            return
        }
        for col := 0; col < n; col++ {
            if cols[col] || diag1[row-col+n] || diag2[row+col] { continue }
            board[row][col] = 'Q'
            cols[col], diag1[row-col+n], diag2[row+col] = true, true, true
            backtrack(row + 1)
            board[row][col] = '.'
            cols[col], diag1[row-col+n], diag2[row+col] = false, false, false
        }
    }
    backtrack(0)
    return result
}

// ── Sudoku Solver ─────────────────────────────────────────
func solveSudoku(board [][]byte) {
    rows  := [9][9]bool{}
    cols  := [9][9]bool{}
    boxes := [9][9]bool{}
    var empty [][2]int

    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            if board[r][c] == '.' { empty = append(empty, [2]int{r, c}); continue }
            d := board[r][c] - '1'
            rows[r][d], cols[c][d], boxes[(r/3)*3+c/3][d] = true, true, true
        }
    }
    var solve func(idx int) bool
    solve = func(idx int) bool {
        if idx == len(empty) { return true }
        r, c := empty[idx][0], empty[idx][1]
        box := (r/3)*3 + c/3
        for d := 0; d < 9; d++ {
            if rows[r][d] || cols[c][d] || boxes[box][d] { continue }
            board[r][c] = byte('1' + d)
            rows[r][d], cols[c][d], boxes[box][d] = true, true, true
            if solve(idx + 1) { return true }
            board[r][c] = '.'
            rows[r][d], cols[c][d], boxes[box][d] = false, false, false
        }
        return false
    }
    solve(0)
}

// ── Word Search (grid) ────────────────────────────────────
func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(r, c, idx int) bool
    dfs = func(r, c, idx int) bool {
        if idx == len(word) { return true }
        if r < 0 || r >= m || c < 0 || c >= n { return false }
        if board[r][c] != word[idx] { return false }
        tmp := board[r][c]
        board[r][c] = '#'        // mark visited in-place
        found := dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1) ||
                 dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1)
        board[r][c] = tmp        // restore
        return found
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if dfs(r, c, 0) { return true }
        }
    }
    return false
}

func main() {
    fmt.Println(len(solveNQueens(4))) // 2 solutions
    fmt.Println(solveNQueens(4)[0])

    grid := [][]byte{
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'},
    }
    fmt.Println(exist(grid, "ABCCED")) // true
    fmt.Println(exist(grid, "SEE"))    // true
    fmt.Println(exist(grid, "ABCB"))   // false
}

package main

import "fmt"

// ── Standard Trie (26 lowercase letters) ─────────────────
type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
    // Optional extras often needed in interviews:
    count    int    // how many words pass through this node
    word     string // store word at leaf (useful for Word Search II)
}

type Trie struct{ root *TrieNode }

func NewTrie() *Trie { return &Trie{root: &TrieNode{}} }

func (t *Trie) Insert(word string) {
    node := t.root
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &TrieNode{}
        }
        node = node.children[idx]
        node.count++ // count words with this prefix
    }
    node.isEnd = true
    node.word = word
}

func (t *Trie) Search(word string) bool {
    node := t.find(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.find(prefix) != nil
}

func (t *Trie) CountWithPrefix(prefix string) int {
    node := t.find(prefix)
    if node == nil { return 0 }
    return node.count
}

func (t *Trie) find(prefix string) *TrieNode {
    node := t.root
    for _, c := range prefix {
        idx := c - 'a'
        if node.children[idx] == nil { return nil }
        node = node.children[idx]
    }
    return node
}

// Delete word from trie
func (t *Trie) Delete(word string) bool {
    return t.deleteHelper(t.root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
    if node == nil { return false }
    if depth == len(word) {
        if !node.isEnd { return false }
        node.isEnd = false
        node.word = ""
        return true // caller may prune this node if no children
    }
    idx := word[depth] - 'a'
    if t.deleteHelper(node.children[idx], word, depth+1) {
        node.count--
        // Prune leaf if no longer needed
        if !node.children[idx].isEnd && node.children[idx].count == 0 {
            node.children[idx] = nil
        }
        return true
    }
    return false
}

// ── Trie with wildcard '.' (Word Dictionary) ─────────────
type WordDictionary struct{ root *TrieNode }

func NewWordDictionary() *WordDictionary { return &WordDictionary{&TrieNode{}} }

func (d *WordDictionary) AddWord(word string) {
    node := d.root
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil { node.children[idx] = &TrieNode{} }
        node = node.children[idx]
    }
    node.isEnd = true
}

func (d *WordDictionary) Search(word string) bool {
    return d.searchFrom(d.root, word, 0)
}

func (d *WordDictionary) searchFrom(node *TrieNode, word string, idx int) bool {
    if node == nil { return false }
    if idx == len(word) { return node.isEnd }
    c := word[idx]
    if c != '.' {
        return d.searchFrom(node.children[c-'a'], word, idx+1)
    }
    // Wildcard: try all 26 children
    for _, child := range node.children {
        if d.searchFrom(child, word, idx+1) { return true }
    }
    return false
}

// ── Map-based Trie (simpler, supports any alphabet) ───────
type MapTrieNode struct {
    children map[rune]*MapTrieNode
    isEnd    bool
}

func NewMapTrie() *MapTrieNode { return &MapTrieNode{children: make(map[rune]*MapTrieNode)} }

func (n *MapTrieNode) Insert(word string) {
    curr := n
    for _, c := range word {
        if _, ok := curr.children[c]; !ok {
            curr.children[c] = &MapTrieNode{children: make(map[rune]*MapTrieNode)}
        }
        curr = curr.children[c]
    }
    curr.isEnd = true
}

func (n *MapTrieNode) Search(word string) bool {
    curr := n
    for _, c := range word {
        if _, ok := curr.children[c]; !ok { return false }
        curr = curr.children[c]
    }
    return curr.isEnd
}

func main() {
    t := NewTrie()
    t.Insert("apple"); t.Insert("app"); t.Insert("application")
    fmt.Println(t.Search("apple"))       // true
    fmt.Println(t.Search("app"))         // true
    fmt.Println(t.Search("appl"))        // false
    fmt.Println(t.StartsWith("appl"))    // true
    fmt.Println(t.CountWithPrefix("app")) // 3
    t.Delete("app")
    fmt.Println(t.Search("app"))         // false
    fmt.Println(t.StartsWith("app"))     // true (apple still exists)

    d := NewWordDictionary()
    d.AddWord("bad"); d.AddWord("dad"); d.AddWord("mad")
    fmt.Println(d.Search("pad"))  // false
    fmt.Println(d.Search("bad"))  // true
    fmt.Println(d.Search(".ad"))  // true
    fmt.Println(d.Search("b.."))  // true
}

package main

import "fmt"

type WNode struct {
    children [26]*WNode
    word     string // non-empty at terminal node
}

// Find all words from list that exist in the grid
func findWords(board [][]byte, words []string) []string {
    root := &WNode{}
    // Build trie from word list
    for _, w := range words {
        node := root
        for _, c := range w {
            idx := c - 'a'
            if node.children[idx] == nil { node.children[idx] = &WNode{} }
            node = node.children[idx]
        }
        node.word = w
    }

    m, n := len(board), len(board[0])
    var result []string

    var dfs func(node *WNode, r, c int)
    dfs = func(node *WNode, r, c int) {
        if r < 0 || r >= m || c < 0 || c >= n { return }
        ch := board[r][c]
        if ch == '#' { return } // already visited
        next := node.children[ch-'a']
        if next == nil { return } // no words with this prefix

        if next.word != "" {
            result = append(result, next.word)
            next.word = "" // deduplicate: don't add same word twice
        }

        board[r][c] = '#'
        dfs(next, r+1, c); dfs(next, r-1, c)
        dfs(next, r, c+1); dfs(next, r, c-1)
        board[r][c] = ch
    }

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            dfs(root, r, c)
        }
    }
    return result
}

func main() {
    board := [][]byte{
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'},
    }
    words := []string{"oath","pea","eat","rain"}
    fmt.Println(findWords(board, words)) // [oath eat]
}

package main

import "fmt"

// ── Direction arrays ──────────────────────────────────────
var dirs4 = [][2]int{{0,1},{0,-1},{1,0},{-1,0}}             // 4-directional
var dirs8 = [][2]int{{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}} // 8-directional

func inBounds(r, c, m, n int) bool { return r >= 0 && r < m && c >= 0 && c < n }

// ── DFS flood fill ────────────────────────────────────────
func floodFill(image [][]int, sr, sc, color int) [][]int {
    src := image[sr][sc]
    if src == color { return image }
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if !inBounds(r, c, len(image), len(image[0])) { return }
        if image[r][c] != src { return }
        image[r][c] = color
        for _, d := range dirs4 { dfs(r+d[0], c+d[1]) }
    }
    dfs(sr, sc)
    return image
}

// ── BFS: 01 Matrix — distance to nearest 0 ───────────────
func updateMatrix(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    dist := make([][]int, m)
    queue := [][2]int{}
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            if mat[i][j] == 0 {
                dist[i][j] = 0
                queue = append(queue, [2]int{i, j})
            } else {
                dist[i][j] = 1<<30
            }
        }
    }
    for len(queue) > 0 {
        cur := queue[0]; queue = queue[1:]
        for _, d := range dirs4 {
            r, c := cur[0]+d[0], cur[1]+d[1]
            if inBounds(r, c, m, n) && dist[r][c] > dist[cur[0]][cur[1]]+1 {
                dist[r][c] = dist[cur[0]][cur[1]] + 1
                queue = append(queue, [2]int{r, c})
            }
        }
    }
    return dist
}

// ── BFS: Rotting Oranges — minimum time ──────────────────
func orangesRotting(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    fresh, minutes := 0, 0
    queue := [][2]int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch grid[i][j] {
            case 1: fresh++
            case 2: queue = append(queue, [2]int{i, j})
            }
        }
    }
    for len(queue) > 0 && fresh > 0 {
        size := len(queue)
        for k := 0; k < size; k++ {
            r, c := queue[k][0], queue[k][1]
            for _, d := range dirs4 {
                nr, nc := r+d[0], c+d[1]
                if inBounds(nr, nc, m, n) && grid[nr][nc] == 1 {
                    grid[nr][nc] = 2
                    fresh--
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
        queue = queue[size:]
        minutes++
    }
    if fresh > 0 { return -1 }
    return minutes
}

// ── Pacific Atlantic Water Flow ───────────────────────────
// Water can flow to cell with equal or lower height
// Find cells that can reach BOTH oceans
func pacificAtlantic(heights [][]int) [][2]int {
    m, n := len(heights), len(heights[0])
    pacific  := make([][]bool, m)
    atlantic := make([][]bool, m)
    for i := range pacific { pacific[i] = make([]bool, n); atlantic[i] = make([]bool, n) }

    var bfs func(queue [][2]int, visited [][]bool)
    bfs = func(queue [][2]int, visited [][]bool) {
        for len(queue) > 0 {
            cur := queue[0]; queue = queue[1:]
            for _, d := range dirs4 {
                r, c := cur[0]+d[0], cur[1]+d[1]
                if inBounds(r, c, m, n) && !visited[r][c] &&
                    heights[r][c] >= heights[cur[0]][cur[1]] { // reverse flow: go uphill
                    visited[r][c] = true
                    queue = append(queue, [2]int{r, c})
                }
            }
        }
    }

    // Seed Pacific (top row + left col) and Atlantic (bottom row + right col)
    pQueue, aQueue := [][2]int{}, [][2]int{}
    for i := 0; i < m; i++ {
        pacific[i][0] = true;   pQueue = append(pQueue, [2]int{i, 0})
        atlantic[i][n-1] = true; aQueue = append(aQueue, [2]int{i, n-1})
    }
    for j := 0; j < n; j++ {
        pacific[0][j] = true;   pQueue = append(pQueue, [2]int{0, j})
        atlantic[m-1][j] = true; aQueue = append(aQueue, [2]int{m-1, j})
    }
    bfs(pQueue, pacific); bfs(aQueue, atlantic)

    var result [][2]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pacific[i][j] && atlantic[i][j] { result = append(result, [2]int{i, j}) }
        }
    }
    return result
}

// ── Surrounded Regions — capture 'O' not connected to edge ─
func solve(board [][]byte) {
    m, n := len(board), len(board[0])
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if !inBounds(r, c, m, n) || board[r][c] != 'O' { return }
        board[r][c] = 'S' // safe — connected to border
        for _, d := range dirs4 { dfs(r+d[0], c+d[1]) }
    }
    // Mark all 'O's connected to border as safe
    for i := 0; i < m; i++ { dfs(i, 0); dfs(i, n-1) }
    for j := 0; j < n; j++ { dfs(0, j); dfs(m-1, j) }
    // Flip: remaining 'O' → 'X', safe 'S' → 'O'
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch board[i][j] {
            case 'O': board[i][j] = 'X'
            case 'S': board[i][j] = 'O'
            }
        }
    }
}

// ── Number of Distinct Islands (shape hashing) ───────────
func numDistinctIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    shapes := make(map[string]bool)
    var shape []byte
    var dfs func(r, c, br, bc int)
    dfs = func(r, c, br, bc int) {
        if !inBounds(r, c, m, n) || grid[r][c] != '1' { return }
        grid[r][c] = '0'
        shape = append(shape, byte(r-br+'0'), byte(c-bc+'0'), ',') // relative position
        for _, d := range dirs4 { dfs(r+d[0], c+d[1], br, bc) }
        shape = append(shape, '!') // backtrack marker (distinguishes shapes)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                shape = shape[:0]
                dfs(i, j, i, j)
                shapes[string(shape)] = true
            }
        }
    }
    return len(shapes)
}

func main() {
    img := [][]int{{1,1,1},{1,1,0},{1,0,1}}
    fmt.Println(floodFill(img, 1, 1, 2)) // [[2 2 2] [2 2 0] [2 0 1]]

    mat := [][]int{{0,0,0},{0,1,0},{1,1,1}}
    fmt.Println(updateMatrix(mat)) // [[0 0 0] [0 1 0] [1 2 1]]

    grid := [][]int{{2,1,1},{1,1,0},{0,1,1}}
    fmt.Println(orangesRotting(grid)) // 4

    heights := [][]int{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}}
    fmt.Println(pacificAtlantic(heights)) // cells reaching both oceans
}

package main

import "fmt"

// ── Union-Find for grid connectivity ──────────────────────
type UnionFind struct {
    parent, rank []int
    components   int
}

func newUF(n int) *UnionFind {
    uf := &UnionFind{parent: make([]int, n), rank: make([]int, n), components: n}
    for i := range uf.parent { uf.parent[i] = i }
    return uf
}

func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x { uf.parent[x] = uf.find(uf.parent[x]) } // path compression
    return uf.parent[x]
}

func (uf *UnionFind) union(x, y int) {
    rx, ry := uf.find(x), uf.find(y)
    if rx == ry { return }
    uf.components--
    if uf.rank[rx] < uf.rank[ry] { rx, ry = ry, rx }
    uf.parent[ry] = rx
    if uf.rank[rx] == uf.rank[ry] { uf.rank[rx]++ }
}

// Number of Islands using Union-Find
func numIslandsUF(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    uf := newUF(m * n)
    islandCount := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                islandCount++
                if i > 0 && grid[i-1][j] == '1' { uf.union(i*n+j, (i-1)*n+j); islandCount-- }
                if j > 0 && grid[i][j-1] == '1' { uf.union(i*n+j, i*n+j-1);   islandCount-- }
            }
        }
    }
    return islandCount
}

// ── Diagonal traversal ────────────────────────────────────
// Traverse all diagonals of m×n matrix (anti-diagonal: r+c=const)
func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    result := make([]int, 0, m*n)
    diags := make(map[int][]int)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            diags[i+j] = append(diags[i+j], mat[i][j])
        }
    }
    for d := 0; d < m+n-1; d++ {
        if d%2 == 0 { // go up-right: reverse the diagonal
            for k := len(diags[d])-1; k >= 0; k-- { result = append(result, diags[d][k]) }
        } else {
            result = append(result, diags[d]...)
        }
    }
    return result
}

// ── Valid path in grid with obstacles ─────────────────────
// 0 = free, 1 = obstacle
func hasPathInGrid(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    if grid[0][0] == 1 || grid[m-1][n-1] == 1 { return false }
    queue := [][2]int{{0, 0}}
    grid[0][0] = 1 // mark visited
    for len(queue) > 0 {
        r, c := queue[0][0], queue[0][1]; queue = queue[1:]
        if r == m-1 && c == n-1 { return true }
        for _, d := range dirs4 {
            nr, nc := r+d[0], c+d[1]
            if inBounds(nr, nc, m, n) && grid[nr][nc] == 0 {
                grid[nr][nc] = 1
                queue = append(queue, [2]int{nr, nc})
            }
        }
    }
    return false
}

var dirs4 = [][2]int{{0,1},{0,-1},{1,0},{-1,0}}
func inBounds(r, c, m, n int) bool { return r >= 0 && r < m && c >= 0 && c < n }

func main() {
    g := [][]byte{{'1','1','0'},{'0','1','1'},{'0','0','1'}}
    fmt.Println(numIslandsUF(g)) // 1

    mat := [][]int{{1,2,3},{4,5,6},{7,8,9}}
    fmt.Println(findDiagonalOrder(mat)) // [1 2 4 7 5 3 6 8 9]
}

package main

import "fmt"

func main() {
    // ── fmt.Scan — reads space/newline-separated tokens ──
    var a, b int
    fmt.Scan(&a, &b)         // reads two ints; works across newlines
    fmt.Println(a + b)

    // ── fmt.Scanln — stops at newline ───────────────────
    var x, y float64
    fmt.Scanln(&x, &y)       // both must be on the SAME line
    fmt.Printf("%.2f\n", x+y)

    // ── fmt.Scanf — formatted, like C scanf ─────────────
    var name string
    var age int
    fmt.Scanf("%s %d", &name, &age)
    fmt.Printf("name=%s age=%d\n", name, age)

    // ── Read N numbers on one line ───────────────────────
    var n int
    fmt.Scan(&n)
    nums := make([]int, n)
    for i := range nums {
        fmt.Scan(&nums[i])   // works even if spread across lines
    }
    fmt.Println(nums)

    // ── Read until EOF (unknown count) ───────────────────
    var v int
    var values []int
    for {
        _, err := fmt.Scan(&v)
        if err != nil { break } // io.EOF or parse error
        values = append(values, v)
    }
    fmt.Println(values)
}

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    // ── Increase buffer for long lines (default = 64KB) ─
    // Required if a single line can be very long
    const maxBuf = 1024 * 1024 // 1MB
    scanner.Buffer(make([]byte, maxBuf), maxBuf)

    // ── Read line by line ────────────────────────────────
    var lines []string
    for scanner.Scan() {
        line := scanner.Text()   // current line, no trailing \n
        if line == "" { break }  // stop on blank line (optional)
        lines = append(lines, line)
    }
    if err := scanner.Err(); err != nil {
        fmt.Fprintln(os.Stderr, "read error:", err)
    }
    fmt.Println(lines)

    // ── Read first line as single integer ────────────────
    scanner2 := bufio.NewScanner(os.Stdin)
    scanner2.Scan()
    n, _ := strconv.Atoi(scanner2.Text())
    fmt.Println(n)

    // ── Read line of space-separated ints ────────────────
    scanner3 := bufio.NewScanner(os.Stdin)
    scanner3.Scan()
    parts := strings.Fields(scanner3.Text()) // splits on any whitespace
    nums := make([]int, len(parts))
    for i, p := range parts {
        nums[i], _ = strconv.Atoi(p)
    }
    fmt.Println(nums)

    // ── Read a grid (matrix) ─────────────────────────────
    scanner4 := bufio.NewScanner(os.Stdin)
    var grid [][]int
    for scanner4.Scan() {
        row := []int{}
        for _, p := range strings.Fields(scanner4.Text()) {
            v, _ := strconv.Atoi(p)
            row = append(row, v)
        }
        if len(row) > 0 { grid = append(grid, row) }
    }
    fmt.Println(grid)

    // ── Split by words instead of lines ─────────────────
    scanner5 := bufio.NewScanner(os.Stdin)
    scanner5.Split(bufio.ScanWords) // default is ScanLines
    for scanner5.Scan() {
        fmt.Println(scanner5.Text()) // each word
    }
}

package main

import (
    "bufio"
    "fmt"
    "os"
)

// ── Standard fast I/O template ────────────────────────────
// Copy this boilerplate at the top of every competitive solution

var (
    reader = bufio.NewReader(os.Stdin)
    writer = bufio.NewWriter(os.Stdout)
)

func main() {
    defer writer.Flush() // CRITICAL: flush buffered output at end

    // Read a single integer
    var n int
    fmt.Fscan(reader, &n)

    // Read n integers
    nums := make([]int, n)
    for i := range nums {
        fmt.Fscan(reader, &nums[i])
    }

    // Read a string
    var s string
    fmt.Fscan(reader, &s) // stops at whitespace

    // Read multiple values in one call
    var a, b, c int
    fmt.Fscan(reader, &a, &b, &c)

    // Read a grid of n rows, m cols
    var rows, cols int
    fmt.Fscan(reader, &rows, &cols)
    grid := make([][]int, rows)
    for i := range grid {
        grid[i] = make([]int, cols)
        for j := range grid[i] {
            fmt.Fscan(reader, &grid[i][j])
        }
    }

    // Write output (always to writer, not fmt.Println)
    fmt.Fprintln(writer, n)
    for _, v := range nums {
        fmt.Fprintf(writer, "%d ", v)
    }
    fmt.Fprintln(writer)
    fmt.Fprintln(writer, grid)
}

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strings"
)

var in  = bufio.NewReader(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
    defer out.Flush()
    // ── Choose the pattern matching your problem input ───

    pattern1() // "read N, then N numbers"
    // pattern2() // "read until EOF"
    // pattern3() // "read T test cases"
    // pattern4() // "read a grid"
    // pattern5() // "read edges for a graph"
    // pattern6() // "read key-value pairs"
}

// Pattern 1: N followed by N space-separated integers
// Input:
//   5
//   3 1 4 1 5
func pattern1() {
    var n int
    fmt.Fscan(in, &n)
    nums := make([]int, n)
    for i := range nums { fmt.Fscan(in, &nums[i]) }
    sort.Ints(nums)
    fmt.Fprintln(out, nums)
}

// Pattern 2: Read until EOF — unknown number of integers
// Input:
//   1 2 3
//   4 5 6
func pattern2() {
    var nums []int
    var v int
    for {
        _, err := fmt.Fscan(in, &v)
        if err != nil { break }
        nums = append(nums, v)
    }
    fmt.Fprintln(out, nums)
}

// Pattern 3: T test cases
// Input:
//   3
//   5
//   10
//   15
func pattern3() {
    var t int
    fmt.Fscan(in, &t)
    for ; t > 0; t-- {
        var n int
        fmt.Fscan(in, &n)
        fmt.Fprintln(out, n*2) // solve per test case
    }
}

// Pattern 4: R x C grid of integers
// Input:
//   3 4
//   1 2 3 4
//   5 6 7 8
//   9 0 1 2
func pattern4() {
    var r, c int
    fmt.Fscan(in, &r, &c)
    grid := make([][]int, r)
    for i := range grid {
        grid[i] = make([]int, c)
        for j := range grid[i] { fmt.Fscan(in, &grid[i][j]) }
    }
    for _, row := range grid { fmt.Fprintln(out, row) }
}

// Pattern 4b: R x C grid of characters (maze, board)
// Input:
//   3 3
//   #.#
//   .S.
//   #.#
func pattern4b() {
    var r, c int
    fmt.Fscan(in, &r, &c)
    scanner := bufio.NewScanner(in)
    scanner.Scan() // consume trailing newline after "r c"
    grid := make([]string, r)
    for i := range grid {
        scanner.Scan()
        grid[i] = scanner.Text()
    }
    for _, row := range grid { fmt.Fprintln(out, row) }
}

// Pattern 5: Graph as edge list
// Input:
//   4 5        ← n nodes, m edges
//   0 1
//   0 2
//   1 3
//   2 3
//   1 2
func pattern5() {
    var n, m int
    fmt.Fscan(in, &n, &m)
    adj := make([][]int, n)
    for i := 0; i < m; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u) // undirected; remove for directed
    }
    for i, neighbors := range adj {
        fmt.Fprintf(out, "%d: %v\n", i, neighbors)
    }
}

// Pattern 6: Read words / string tokens per line
// Input:
//   hello world foo
//   bar baz
func pattern6() {
    scanner := bufio.NewScanner(in)
    for scanner.Scan() {
        words := strings.Fields(scanner.Text())
        fmt.Fprintln(out, len(words), words)
    }
}

package main

import (
    "flag"
    "fmt"
    "os"
    "strconv"
)

func main() {
    // ── os.Args — raw positional arguments ───────────────
    // Usage: go run cli_args.go hello 42
    fmt.Println("program:", os.Args[0])
    if len(os.Args) > 1 {
        fmt.Println("args:", os.Args[1:])
        for i, arg := range os.Args[1:] {
            if n, err := strconv.Atoi(arg); err == nil {
                fmt.Printf("  arg[%d] is int: %d\n", i, n)
            } else {
                fmt.Printf("  arg[%d] is string: %s\n", i, arg)
            }
        }
    }

    // ── flag package — named flags ────────────────────────
    // Usage: go run cli_args.go -port 8080 -verbose -name gopher
    port    := flag.Int("port", 3000, "server port")
    verbose := flag.Bool("verbose", false, "enable verbose output")
    name    := flag.String("name", "world", "name to greet")
    timeout := flag.Duration("timeout", 0, "request timeout e.g. 30s")

    flag.Parse() // MUST call before reading any flag values

    // flag.Args() returns remaining non-flag arguments
    rest := flag.Args()

    fmt.Printf("port=%d verbose=%v name=%s timeout=%v\n",
        *port, *verbose, *name, *timeout)
    fmt.Println("remaining args:", rest)

    // Custom usage message
    flag.Usage = func() {
        fmt.Fprintf(os.Stderr, "Usage of %s:\n", os.Args[0])
        flag.PrintDefaults()
    }
}

# Pipe a string directly
echo "5\n3 1 4 1 5" | go run solution.go

# Multi-line input (use $'...' for actual newlines in bash)
echo $'5\n3 1 4 1 5' | go run solution.go

# Redirect from a file (best for complex test cases)
go run solution.go < input.txt

# Redirect output too
go run solution.go < input.txt > output.txt

# Interactive: just run and type, Ctrl+D to send EOF
go run solution.go

# Create a test input file
cat > input.txt << 'EOF'
5
3 1 4 1 5
EOF
go run solution.go < input.txt