Pattern recognition: from problem to technique

package main
 
import (
	"container/heap"
	"fmt"
	"slices"
)
 
// 1. Binary search: first index with nums[i] >= target.
func lowerBound(nums []int, target int) int {
	lo, hi := 0, len(nums)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if nums[mid] >= target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return lo
}
 
// 2. Two pointers: pair in a sorted slice that sums to target.
func twoSumSorted(nums []int, target int) (int, int) {
	l, r := 0, len(nums)-1
	for l < r {
		switch s := nums[l] + nums[r]; {
		case s == target:
			return l, r
		case s < target:
			l++
		default:
			r--
		}
	}
	return -1, -1
}
 
// 3. Sliding window: longest substring with at most k distinct bytes.
func longestKDistinct(s string, k int) int {
	count := map[byte]int{}
	left, best := 0, 0
	for right := 0; right < len(s); right++ {
		count[s[right]]++
		for len(count) > k {
			count[s[left]]--
			if count[s[left]] == 0 {
				delete(count, s[left])
			}
			left++
		}
		best = max(best, right-left+1)
	}
	return best
}
 
// 4. Prefix sum + hash map: subarrays that sum to k (negatives allowed).
func subarraySum(nums []int, k int) int {
	seen := map[int]int{0: 1}
	sum, count := 0, 0
	for _, n := range nums {
		sum += n
		count += seen[sum-k]
		seen[sum]++
	}
	return count
}
 
// 5. Monotonic stack: days until a warmer temperature.
func dailyTemperatures(t []int) []int {
	res := make([]int, len(t))
	var stack []int // indices, temperatures decreasing
	for i, x := range t {
		for len(stack) > 0 && t[stack[len(stack)-1]] < x {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[j] = i - j
		}
		stack = append(stack, i)
	}
	return res
}
 
// 6. Heap: k-th largest with a min-heap that never holds more than k.
type minHeap []int
 
func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}
 
func kthLargest(nums []int, k int) int {
	h := &minHeap{}
	for _, n := range nums {
		heap.Push(h, n)
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	return (*h)[0]
}
 
// 7. Grid BFS: fewest steps from top-left to bottom-right (1 = wall).
func shortestPath(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if grid[0][0] == 1 {
		return -1
	}
	dist := make([][]int, m)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = -1
		}
	}
	dist[0][0] = 0
	queue := [][2]int{{0, 0}}
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for len(queue) > 0 {
		r, c := queue[0][0], queue[0][1]
		queue = queue[1:]
		for _, d := range dirs {
			nr, nc := r+d[0], c+d[1]
			if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == 1 || dist[nr][nc] != -1 {
				continue
			}
			dist[nr][nc] = dist[r][c] + 1
			queue = append(queue, [2]int{nr, nc})
		}
	}
	return dist[m-1][n-1]
}
 
// 8. Backtracking: every subset.
func subsets(nums []int) [][]int {
	var res [][]int
	var path []int
	var dfs func(i int)
	dfs = func(i int) {
		if i == len(nums) {
			res = append(res, slices.Clone(path))
			return
		}
		path = append(path, nums[i]) // take nums[i]
		dfs(i + 1)
		path = path[:len(path)-1] // undo
		dfs(i + 1)                // skip nums[i]
	}
	dfs(0)
	return res
}
 
// 9. Union-find: number of connected components.
func countComponents(n int, edges [][2]int) int {
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	comps := n
	for _, e := range edges {
		if a, b := find(e[0]), find(e[1]); a != b {
			parent[a] = b
			comps--
		}
	}
	return comps
}
 
// 10. Topological sort (Kahn): can every course be finished?
func canFinish(n int, prereq [][2]int) bool {
	adj := make([][]int, n)
	indeg := make([]int, n)
	for _, p := range prereq {
		adj[p[1]] = append(adj[p[1]], p[0])
		indeg[p[0]]++
	}
	var queue []int
	for i, d := range indeg {
		if d == 0 {
			queue = append(queue, i)
		}
	}
	done := 0
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		done++
		for _, v := range adj[u] {
			if indeg[v]--; indeg[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	return done == n
}
 
// 11. DP: fewest coins that make amount.
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		dp[a] = amount + 1 // "infinity"
		for _, c := range coins {
			if c <= a {
				dp[a] = min(dp[a], dp[a-c]+1)
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}
 
func main() {
	fmt.Println("1 lowerBound:", lowerBound([]int{1, 3, 5, 7}, 4))
	l, r := twoSumSorted([]int{2, 7, 11, 15}, 9)
	fmt.Println("2 two pointers:", l, r)
	fmt.Println("3 window:", longestKDistinct("eceba", 2))
	fmt.Println("4 prefix:", subarraySum([]int{1, -1, 1, 1}, 2))
	fmt.Println("5 stack:", dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76, 73}))
	fmt.Println("6 heap:", kthLargest([]int{3, 2, 1, 5, 6, 4}, 2))
	fmt.Println("7 bfs:", shortestPath([][]int{{0, 0, 0}, {1, 1, 0}, {0, 0, 0}}))
	fmt.Println("8 backtrack:", subsets([]int{1, 2}))
	fmt.Println("9 union-find:", countComponents(5, [][2]int{{0, 1}, {1, 2}, {3, 4}}))
	fmt.Println("10 topo:", canFinish(2, [][2]int{{1, 0}}), canFinish(2, [][2]int{{1, 0}, {0, 1}}))
	fmt.Println("11 dp:", coinChange([]int{1, 2, 5}, 11))
}

1 lowerBound: 2
2 two pointers: 0 1
3 window: 3
4 prefix: 2
5 stack: [1 1 4 2 1 1 0 0]
6 heap: 5
7 bfs: 4
8 backtrack: [[1 2] [1] [2] []]
9 union-find: 2
10 topo: true false
11 dp: 3