LeetCode Patterns (Go-разработчик Middle 3)

Зачем знать на Middle 3: даже в “non-FAANG” компаниях алгоритмическое собеседование никуда не делось. На Middle 3 ждут уверенного владения 15 паттернами и Top 30-50 задач. Главное — не запомнить решения, а распознать паттерн за первые 2 минуты.

Содержание

1. Two Pointers
2. Sliding Window
3. Fast & Slow Pointers
4. Merge Intervals
5. Cyclic Sort
6. In-place Reverse Linked List
7. Tree BFS
8. Tree DFS
9. Two Heaps
10. Subsets / Backtracking
11. Modified Binary Search
12. Top K Elements
13. K-way Merge
14. Dynamic Programming
15. Graph (BFS, DFS, TopSort, Dijkstra, Union-Find)
16. Top 30 задач
17. Источники

---

1. Two Pointers

Когда применять

• Массив отсортирован.
• Ищем пару/triplet/quadruplet с условием.
• Палиндром.
• Container/двусторонняя задача.

Template

i, j := 0, len(arr)-1
for i < j {
    s := arr[i] + arr[j]
    switch {
    case s == target: return ...
    case s < target:  i++
    default:          j--
    }
}

Complexity

• Time: O(n).
• Space: O(1).

Sample: Container With Most Water (LC 11)

func maxArea(h []int) int {
    i, j, best := 0, len(h)-1, 0
    for i < j {
        area := min(h[i], h[j]) * (j - i)
        if area > best { best = area }
        if h[i] < h[j] { i++ } else { j-- }
    }
    return best
}

Sample: 3Sum (LC 15)

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }
        l, r := i+1, len(nums)-1
        for l < r {
            s := nums[i] + nums[l] + nums[r]
            switch {
            case s == 0:
                res = append(res, []int{nums[i], nums[l], nums[r]})
                for l < r && nums[l] == nums[l+1] { l++ }
                for l < r && nums[r] == nums[r-1] { r-- }
                l++; r--
            case s < 0: l++
            default:    r--
            }
        }
    }
    return res
}

Pitfalls

• ⚠️ Дубликаты: пропустить same value.
• ⚠️ Сортировка O(n log n) — если запрещено, нужна другая стратегия.

---

2. Sliding Window

Когда применять

• Подстрока/подмассив с свойством.
• Минимум/максимум длина окна.
• Среднее по K элементам.

Template (variable-size window)

left := 0
state := initialState()
best := 0
for right := 0; right < len(arr); right++ {
    state.add(arr[right])
    for !state.isValid() {
        state.remove(arr[left])
        left++
    }
    best = max(best, right - left + 1)
}

Sample: Longest Substring Without Repeating Characters (LC 3)

func lengthOfLongestSubstring(s string) int {
    seen := make(map[byte]int)
    left, best := 0, 0
    for right := 0; right < len(s); right++ {
        if idx, ok := seen[s[right]]; ok && idx >= left {
            left = idx + 1
        }
        seen[s[right]] = right
        if right - left + 1 > best { best = right - left + 1 }
    }
    return best
}

Sample: Minimum Window Substring (LC 76)

func minWindow(s, t string) string {
    if len(t) > len(s) { return "" }
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ { need[t[i]]++ }
    missing := len(t)
    left, start, end := 0, 0, 0
    for right := 0; right < len(s); right++ {
        if need[s[right]] > 0 { missing-- }
        need[s[right]]--
        for missing == 0 {
            if end == 0 || right - left + 1 < end - start {
                start, end = left, right+1
            }
            need[s[left]]++
            if need[s[left]] > 0 { missing++ }
            left++
        }
    }
    return s[start:end]
}

Pitfalls

• ⚠️ left = idx + 1 — не idx.
• ⚠️ Map “expired” entries: проверяй idx >= left.

---

3. Fast & Slow Pointers

Когда применять

• Linked list cycle detection.
• Middle of list.
• Happy number / cycle in computation.

Template

slow, fast := head, head
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
    if slow == fast { return true } // cycle
}
return false

Sample: Linked List Cycle (LC 141)

См. template выше.

Sample: Cycle Start (LC 142)

Floyd’s:

1. slow/fast meet.
2. Reset slow к head; same step → meet at cycle start.

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            slow = head
            for slow != fast {
                slow, fast = slow.Next, fast.Next
            }
            return slow
        }
    }
    return nil
}

Complexity

• Time: O(n), Space: O(1).

---

4. Merge Intervals

Когда

• Перекрывающиеся ranges.
• Meeting rooms, calendars.

Template

sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
res := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
    if intervals[i][0] <= res[len(res)-1][1] {
        res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1])
    } else {
        res = append(res, intervals[i])
    }
}

Sample: Merge Intervals (LC 56)

См. выше.

Sample: Meeting Rooms II (LC 253) — min rooms

func minMeetingRooms(intervals [][]int) int {
    starts, ends := make([]int, 0), make([]int, 0)
    for _, in := range intervals {
        starts = append(starts, in[0])
        ends = append(ends, in[1])
    }
    sort.Ints(starts); sort.Ints(ends)
    rooms, end := 0, 0
    for i := 0; i < len(starts); i++ {
        if starts[i] < ends[end] {
            rooms++
        } else {
            end++
        }
    }
    return rooms
}

Pitfalls

• Strict vs non-strict overlap (< vs <=).

---

5. Cyclic Sort

Когда

• Числа от 1 до N (или 0 до N-1).
• Найти missing/duplicate.

Template

i := 0
for i < len(nums) {
    if nums[i] != nums[nums[i]-1] {
        nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
    } else {
        i++
    }
}
// теперь nums[i] should be i+1

Sample: Find Missing Number (LC 268)

func missingNumber(nums []int) int {
    for i := 0; i < len(nums); {
        if nums[i] < len(nums) && nums[i] != nums[nums[i]] {
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        } else { i++ }
    }
    for i := 0; i < len(nums); i++ {
        if nums[i] != i { return i }
    }
    return len(nums)
}

Complexity

• O(n) time, O(1) space.

---

6. In-place Reverse Linked List

Template

var prev *ListNode
cur := head
for cur != nil {
    next := cur.Next
    cur.Next = prev
    prev = cur
    cur = next
}
return prev

Sample: Reverse Linked List (LC 206)

См. template.

Sample: Reverse K Group (LC 25)

func reverseKGroup(head *ListNode, k int) *ListNode {
    cur := head
    for i := 0; i < k; i++ {
        if cur == nil { return head }
        cur = cur.Next
    }
    var prev *ListNode
    cur = head
    for i := 0; i < k; i++ {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    head.Next = reverseKGroup(cur, k)
    return prev
}

---

7. Tree BFS (level-order)

Template

queue := []*TreeNode{root}
for len(queue) > 0 {
    sz := len(queue)
    var level []int
    for i := 0; i < sz; i++ {
        node := queue[0]; queue = queue[1:]
        level = append(level, node.Val)
        if node.Left != nil { queue = append(queue, node.Left) }
        if node.Right != nil { queue = append(queue, node.Right) }
    }
    res = append(res, level)
}

Sample: Level Order (LC 102), Zigzag (LC 103), Right Side View (LC 199).

Pitfalls

• ⚠️ queue[0]; queue = queue[1:] — амортизация: лучше использовать индекс если стек большой.

---

8. Tree DFS

Template (recursive)

func dfs(node *TreeNode) {
    if node == nil { return }
    // pre-order
    dfs(node.Left)
    // in-order
    dfs(node.Right)
    // post-order
}

Iterative с stack

stack := []*TreeNode{}
cur := root
for cur != nil || len(stack) > 0 {
    for cur != nil {
        stack = append(stack, cur)
        cur = cur.Left
    }
    cur = stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    // visit cur
    cur = cur.Right
}

Sample: Validate BST (LC 98)

func isValidBST(root *TreeNode) bool {
    var prev *int
    var inorder func(n *TreeNode) bool
    inorder = func(n *TreeNode) bool {
        if n == nil { return true }
        if !inorder(n.Left) { return false }
        if prev != nil && n.Val <= *prev { return false }
        prev = &n.Val
        return inorder(n.Right)
    }
    return inorder(root)
}

Sample: Lowest Common Ancestor (LC 236)

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q { return root }
    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right, p, q)
    if l != nil && r != nil { return root }
    if l != nil { return l }
    return r
}

---

9. Two Heaps

Когда

• Median from data stream.
• Sliding median.

Idea

• maxHeap для нижней половины.
• minHeap для верхней.
• Balance |maxH - minH| <= 1.

Sample: Find Median from Data Stream (LC 295)

type MedianFinder struct {
    lo *IntHeap // max-heap (negate)
    hi *IntHeap // min-heap
}

func (mf *MedianFinder) AddNum(num int) {
    heap.Push(mf.lo, -num) // negated
    heap.Push(mf.hi, -(*mf.lo)[0])
    heap.Pop(mf.lo)
    if mf.hi.Len() > mf.lo.Len() {
        heap.Push(mf.lo, -(*mf.hi)[0])
        heap.Pop(mf.hi)
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.lo.Len() > mf.hi.Len() {
        return float64(-(*mf.lo)[0])
    }
    return (float64(-(*mf.lo)[0]) + float64((*mf.hi)[0])) / 2
}

(нужно реализовать IntHeap через container/heap.)

---

10. Subsets / Backtracking

Template

func backtrack(start int, path []int, res *[][]int) {
    cp := make([]int, len(path))
    copy(cp, path)
    *res = append(*res, cp)
    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])
        backtrack(i+1, path, res)
        path = path[:len(path)-1]
    }
}

Sample: Subsets (LC 78)

См. template.

Sample: Permutations (LC 46)

func permute(nums []int) [][]int {
    var res [][]int
    var bt func(path, remaining []int)
    bt = func(path, rem []int) {
        if len(rem) == 0 {
            cp := make([]int, len(path)); copy(cp, path)
            res = append(res, cp); return
        }
        for i := range rem {
            new := append([]int{}, rem[:i]...)
            new = append(new, rem[i+1:]...)
            bt(append(path, rem[i]), new)
        }
    }
    bt(nil, nums)
    return res
}

Sample: Word Search (LC 79) — backtracking on grid

func exist(board [][]byte, word string) bool {
    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        if k == len(word) { return true }
        if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[k] { return false }
        tmp := board[i][j]
        board[i][j] = '#'
        ok := dfs(i+1, j, k+1) || dfs(i-1, j, k+1) || dfs(i, j+1, k+1) || dfs(i, j-1, k+1)
        board[i][j] = tmp
        return ok
    }
    for i := range board {
        for j := range board[0] {
            if dfs(i, j, 0) { return true }
        }
    }
    return false
}

---

11. Modified Binary Search

Template

l, r := 0, len(arr)-1
for l <= r {
    m := l + (r-l)/2
    switch {
    case arr[m] == target: return m
    case arr[m] < target:  l = m+1
    default:               r = m-1
    }
}
return -1

Sample: Search in Rotated Sorted Array (LC 33)

func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        m := (l + r) / 2
        if nums[m] == target { return m }
        if nums[l] <= nums[m] { // left half sorted
            if nums[l] <= target && target < nums[m] { r = m-1 } else { l = m+1 }
        } else { // right half sorted
            if nums[m] < target && target <= nums[r] { l = m+1 } else { r = m-1 }
        }
    }
    return -1
}

Sample: Find Peak Element (LC 162) — O(log n).

Pitfalls

• m := l + (r-l)/2 чтобы избежать overflow.

---

12. Top K Elements (Heap)

Когда

• “Top K frequent”, “K closest points to origin”.

Sample: Top K Frequent (LC 347)

import "container/heap"

type kv struct{ k, v int }
type freqHeap []kv

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

func topKFrequent(nums []int, k int) []int {
    cnt := map[int]int{}
    for _, n := range nums { cnt[n]++ }
    h := &freqHeap{}
    heap.Init(h)
    for k_, v := range cnt {
        heap.Push(h, kv{k_, v})
        if h.Len() > k { heap.Pop(h) }
    }
    res := make([]int, k)
    for i := k-1; i >= 0; i-- {
        res[i] = heap.Pop(h).(kv).k
    }
    return res
}

Complexity

• O(n log k).

---

13. K-way Merge

Когда

• Merge K sorted lists.
• Find K smallest in sorted matrix.

Sample: Merge K Sorted Lists (LC 23)

type listHeap []*ListNode

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

func mergeKLists(lists []*ListNode) *ListNode {
    h := &listHeap{}
    for _, l := range lists {
        if l != nil { heap.Push(h, l) }
    }
    dummy := &ListNode{}
    cur := dummy
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        cur.Next = node
        cur = node
        if node.Next != nil { heap.Push(h, node.Next) }
    }
    return dummy.Next
}

---

14. Dynamic Programming

Когда

• Optimal substructure + overlapping subproblems.
• Min/max/count, choices.

Patterns

• 1D DP (climbing stairs, house robber).
• 2D DP (LCS, edit distance, knapsack).
• DP on subsequences.
• Bitmask DP.

Sample: Climbing Stairs (LC 70)

func climbStairs(n int) int {
    if n <= 2 { return n }
    a, b := 1, 2
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

Sample: Longest Common Subsequence (LC 1143)

func longestCommonSubsequence(s1, s2 string) int {
    n, m := len(s1), len(s2)
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, m+1) }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[n][m]
}

Sample: 0/1 Knapsack

func knapsack(weights, values []int, W int) int {
    n := len(weights)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        for w := W; w >= weights[i]; w-- {
            if dp[w-weights[i]] + values[i] > dp[w] {
                dp[w] = dp[w-weights[i]] + values[i]
            }
        }
    }
    return dp[W]
}

Sample: Longest Increasing Subsequence (LC 300) — O(n log n)

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, n := range nums {
        i := sort.SearchInts(tails, n)
        if i == len(tails) { tails = append(tails, n) } else { tails[i] = n }
    }
    return len(tails)
}

---

15. Graph

BFS template

visited := map[int]bool{start: true}
queue := []int{start}
for len(queue) > 0 {
    cur := queue[0]; queue = queue[1:]
    for _, next := range adj[cur] {
        if !visited[next] {
            visited[next] = true
            queue = append(queue, next)
        }
    }
}

DFS recursive

var dfs func(node int)
dfs = func(node int) {
    visited[node] = true
    for _, next := range adj[node] {
        if !visited[next] { dfs(next) }
    }
}

Topological Sort (Kahn’s BFS)

indeg := make([]int, n)
for _, e := range edges {
    indeg[e[1]]++
}
queue := []int{}
for i := 0; i < n; i++ {
    if indeg[i] == 0 { queue = append(queue, i) }
}
var order []int
for len(queue) > 0 {
    cur := queue[0]; queue = queue[1:]
    order = append(order, cur)
    for _, next := range adj[cur] {
        indeg[next]--
        if indeg[next] == 0 { queue = append(queue, next) }
    }
}
if len(order) != n { return nil } // cycle

Dijkstra (shortest path)

type item struct{ node, dist int }
type pq []item
// ... heap.Interface

func dijkstra(adj map[int][][2]int, src int, n int) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = math.MaxInt32 }
    dist[src] = 0
    h := &pq{{src, 0}}
    heap.Init(h)
    for h.Len() > 0 {
        cur := heap.Pop(h).(item)
        if cur.dist > dist[cur.node] { continue }
        for _, e := range adj[cur.node] {
            nd := cur.dist + e[1]
            if nd < dist[e[0]] {
                dist[e[0]] = nd
                heap.Push(h, item{e[0], nd})
            }
        }
    }
    return dist
}

Union-Find (DSU)

type DSU struct {
    parent, rank []int
}

func NewDSU(n int) *DSU {
    d := &DSU{parent: make([]int, n), rank: make([]int, n)}
    for i := range d.parent { d.parent[i] = i }
    return d
}

func (d *DSU) Find(x int) int {
    if d.parent[x] != x { d.parent[x] = d.Find(d.parent[x]) } // path compression
    return d.parent[x]
}

func (d *DSU) Union(x, y int) bool {
    px, py := d.Find(x), d.Find(y)
    if px == py { return false }
    if d.rank[px] < d.rank[py] { px, py = py, px }
    d.parent[py] = px
    if d.rank[px] == d.rank[py] { d.rank[px]++ }
    return true
}

Sample: Number of Islands (LC 200) — DFS

func numIslands(grid [][]byte) int {
    count := 0
    var dfs func(i, j int)
    dfs = func(i, j int) {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' { return }
        grid[i][j] = '0'
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
    }
    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == '1' { count++; dfs(i, j) }
        }
    }
    return count
}

Sample: Course Schedule (LC 207) — cycle detection

func canFinish(numCourses int, prereqs [][]int) bool {
    adj := make([][]int, numCourses)
    indeg := make([]int, numCourses)
    for _, p := range prereqs {
        adj[p[1]] = append(adj[p[1]], p[0])
        indeg[p[0]]++
    }
    q := []int{}
    for i, d := range indeg { if d == 0 { q = append(q, i) } }
    done := 0
    for len(q) > 0 {
        c := q[0]; q = q[1:]
        done++
        for _, n := range adj[c] {
            indeg[n]--
            if indeg[n] == 0 { q = append(q, n) }
        }
    }
    return done == numCourses
}

---

16. Top 30 LC задач (Go)

#	Задача	Pattern
1	Two Sum	Hashmap
3	Longest Substring Without Repeating	Sliding Window
5	Longest Palindromic Substring	DP / Expand
11	Container With Most Water	Two Pointers
15	3Sum	Two Pointers
20	Valid Parentheses	Stack
21	Merge Two Sorted Lists	Linked List
23	Merge K Sorted Lists	K-way Merge / Heap
33	Search in Rotated Sorted Array	Modified BS
39	Combination Sum	Backtracking
46	Permutations	Backtracking
49	Group Anagrams	Hashmap
53	Maximum Subarray (Kadane)	DP
56	Merge Intervals	Intervals
70	Climbing Stairs	DP
76	Minimum Window Substring	Sliding Window
78	Subsets	Backtracking
79	Word Search	Backtracking
98	Validate BST	DFS
102	Binary Tree Level Order	BFS
121	Best Time to Buy/Sell Stock	DP
124	Binary Tree Maximum Path Sum	DFS
128	Longest Consecutive Sequence	Hashset
141	Linked List Cycle	Fast/Slow
146	LRU Cache	Hashmap + DLL
200	Number of Islands	DFS / Union-Find
207	Course Schedule	TopSort
215	Kth Largest	Heap
217	Contains Duplicate	Hashset
295	Find Median from Data Stream	Two Heaps
300	Longest Increasing Subsequence	DP / Patience
322	Coin Change	DP
416	Partition Equal Subset Sum	DP
543	Diameter of Binary Tree	DFS
994	Rotting Oranges	BFS

(больше 30 — для usability)

---

17. Источники

1. Cracking the Coding Interview — Gayle McDowell
2. Elements of Programming Interviews — Aziz, Lee, Prakash
3. LeetCode Patterns: https://github.com/seanprashad/leetcode-patterns
4. NeetCode: https://neetcode.io
5. Grokking the Coding Interview (Educative)
6. Algorithm Design Manual — Skiena
7. CLRS — Cormen, Leiserson, Rivest, Stein
8. Competitive Programmer’s Handbook — Antti Laaksonen
9. AlgoMonster
10. Go container/heap docs
11. Go sort docs
12. Go runtime, slices, maps perf
13. “100 Go Mistakes” — Teiva Harsanyi (для idiomatic)
14. Go playground for prototyping
15. LeetCode Premium discuss tab