Problem Solving

package main

import "fmt"

// Restated: the second-largest distinct value in nums.
// Input: []int, may be nil or empty. Output: (value, ok); ok is false if there is none.
func secondLargest(nums []int) (int, bool) {
	var first, second int
	haveFirst, haveSecond := false, false
	for _, n := range nums {
		switch {
		case !haveFirst || n > first:
			if haveFirst {
				second, haveSecond = first, true // old leader drops to second
			}
			first, haveFirst = n, true
		case n < first && (!haveSecond || n > second):
			second, haveSecond = n, true
		}
	}
	return second, haveSecond
}

func main() {
	fmt.Println(secondLargest([]int{4, 1, 7, 7, 3})) // normal, with a duplicate leader
	fmt.Println(secondLargest([]int{5, 5, 5}))       // all equal: no answer
	fmt.Println(secondLargest(nil))                  // empty
	fmt.Println(secondLargest([]int{-2, -9}))        // negatives
}

package main

import (
	"fmt"
	"strings"
	"unicode"
)

// normalise keeps letters and digits, lower-cased, as runes (not bytes).
func normalise(s string) []rune {
	var out []rune
	for _, r := range strings.ToLower(s) {
		if unicode.IsLetter(r) || unicode.IsDigit(r) {
			out = append(out, r)
		}
	}
	return out
}

func isMirror(rs []rune) bool {
	for i, j := 0, len(rs)-1; i < j; i, j = i+1, j-1 {
		if rs[i] != rs[j] {
			return false
		}
	}
	return true
}

func isPalindrome(s string) bool { return isMirror(normalise(s)) }

func main() {
	cases := []struct {
		in   string
		want bool
	}{
		{"", true},    // empty
		{"a", true},   // one character
		{"ab", false}, // smallest false case
		{"Aba", true}, // case
		{"A man, a plan, a canal: Panama", true},
		{"race a car", false},
		{".,", true},  // only punctuation
		{"été", true}, // multi-byte runes
	}
	passed := 0
	for _, c := range cases {
		if got := isPalindrome(c.in); got != c.want {
			fmt.Printf("FAIL %q: want %t, got %t\n", c.in, c.want, got)
		} else {
			passed++
		}
	}
	fmt.Printf("%d passed, %d failed\n", passed, len(cases)-passed)
}

package main

import (
	"fmt"
	"slices"
)

var ops int

func naive(a []int, queries [][2]int) []int {
	out := make([]int, 0, len(queries))
	for _, q := range queries {
		sum := 0
		for i := q[0]; i <= q[1]; i++ {
			sum += a[i]
			ops++
		}
		out = append(out, sum)
	}
	return out
}

func withPrefix(a []int, queries [][2]int) []int {
	prefix := make([]int, len(a)+1) // prefix[i] = sum of a[:i]
	for i, v := range a {
		prefix[i+1] = prefix[i] + v
		ops++
	}
	out := make([]int, 0, len(queries))
	for _, q := range queries {
		out = append(out, prefix[q[1]+1]-prefix[q[0]])
		ops++
	}
	return out
}

func main() {
	for _, n := range []int{1_000, 10_000} {
		a := make([]int, n)
		for i := range a {
			a[i] = i % 7
		}
		queries := make([][2]int, n) // n queries, each over the whole slice: worst case
		for i := range queries {
			queries[i] = [2]int{0, n - 1}
		}
		ops = 0
		x := naive(a, queries)
		slow := ops
		ops = 0
		y := withPrefix(a, queries)
		fmt.Printf("n=%d  naive=%d  prefix=%d  same=%t\n", n, slow, ops, slices.Equal(x, y))
	}
}

package main

import "fmt"

// pairSum: a is sorted; indices of two values that add up to target.
func pairSum(a []int, target int) (int, int, bool) {
	i, j := 0, len(a)-1
	for i < j {
		sum := a[i] + a[j]
		switch {
		case sum == target:
			return i, j, true
		case sum < target:
			i++ // too small: a[i] cannot pair with anything, drop it
		default:
			j-- // too big: a[j] cannot pair with anything, drop it
		}
	}
	return -1, -1, false
}

// dedupe: a is sorted; removes repeats in place, returns the shortened slice.
func dedupe(a []int) []int {
	if len(a) == 0 {
		return a
	}
	w := 1 // next write position
	for r := 1; r < len(a); r++ {
		if a[r] != a[w-1] {
			a[w] = a[r]
			w++
		}
	}
	return a[:w]
}

func main() {
	a := []int{2, 5, 7, 9, 12, 15}
	fmt.Println(pairSum(a, 21))
	fmt.Println(pairSum(a, 100))
	fmt.Println(dedupe([]int{1, 1, 2, 3, 3, 3, 4}))
}

package main

import "fmt"

// longestUnique: length of the longest substring with no repeated byte.
func longestUnique(s string) int {
	lastSeen := map[byte]int{}
	best, left := 0, 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		if prev, ok := lastSeen[c]; ok && prev >= left {
			left = prev + 1 // jump the left edge past the earlier copy
		}
		lastSeen[c] = right
		best = max(best, right-left+1)
	}
	return best
}

// maxSumK: largest sum of any k consecutive values (fixed-size window).
func maxSumK(a []int, k int) int {
	sum := 0
	for i := 0; i < k; i++ {
		sum += a[i]
	}
	best := sum
	for i := k; i < len(a); i++ {
		sum += a[i] - a[i-k] // add the new right value, drop the old left one
		best = max(best, sum)
	}
	return best
}

func main() {
	fmt.Println(longestUnique("abcabcbb"), longestUnique("bbbbb"), longestUnique("pwwkew"), longestUnique(""))
	fmt.Println(maxSumK([]int{2, 1, 5, 1, 3, 2}, 3))
}

package main

import (
	"fmt"
	"slices"
)

// twoSum: a is NOT sorted; indices of two values adding to target.
func twoSum(nums []int, target int) (int, int, bool) {
	indexOf := map[int]int{} // value -> index where we saw it
	for i, n := range nums {
		if j, ok := indexOf[target-n]; ok {
			return j, i, true
		}
		indexOf[n] = i
	}
	return -1, -1, false
}

// groupAnagrams: words with the same letters, groups in first-seen order.
func groupAnagrams(words []string) [][]string {
	groupOf := map[string]int{} // sorted letters -> index into groups
	var groups [][]string
	for _, w := range words {
		b := []byte(w)
		slices.Sort(b)
		key := string(b)
		i, ok := groupOf[key]
		if !ok {
			i = len(groups)
			groupOf[key] = i
			groups = append(groups, nil)
		}
		groups[i] = append(groups[i], w)
	}
	return groups
}

func main() {
	fmt.Println(twoSum([]int{3, 8, 11, 2, 7}, 9))
	fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
}

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// daysUntilWarmer: for each day, days until a warmer one (0 if never).
func daysUntilWarmer(temps []int) []int {
	answer := make([]int, len(temps))
	var waiting []int // indices; their temperatures only decrease up the stack
	for i, t := range temps {
		for len(waiting) > 0 && t > temps[waiting[len(waiting)-1]] {
			day := waiting[len(waiting)-1]
			waiting = waiting[:len(waiting)-1]
			answer[day] = i - day
		}
		waiting = append(waiting, i)
	}
	return answer
}

// evalRPN: evaluate postfix like "3 4 +"; errors instead of panicking.
func evalRPN(expr string) (int, error) {
	var stack []int
	for _, tok := range strings.Fields(expr) {
		switch tok {
		case "+", "-", "*":
			if len(stack) < 2 {
				return 0, fmt.Errorf("not enough operands for %s", tok)
			}
			a, b := stack[len(stack)-2], stack[len(stack)-1] // b was pushed last
			stack = stack[:len(stack)-2]
			switch tok {
			case "+":
				stack = append(stack, a+b)
			case "-":
				stack = append(stack, a-b)
			case "*":
				stack = append(stack, a*b)
			}
		default:
			n, err := strconv.Atoi(tok)
			if err != nil {
				return 0, err
			}
			stack = append(stack, n)
		}
	}
	if len(stack) != 1 {
		return 0, fmt.Errorf("malformed expression, stack %v", stack)
	}
	return stack[0], nil
}

func main() {
	fmt.Println(daysUntilWarmer([]int{73, 74, 75, 71, 69, 72, 76, 73}))
	fmt.Println(evalRPN("5 1 2 + 4 * + 3 -"))
	fmt.Println(evalRPN("1 +"))
}

package main

import (
	"fmt"
	"slices"
)

func permutations(nums []int) [][]int {
	var out [][]int
	cur := make([]int, 0, len(nums))
	used := make([]bool, len(nums))
	var explore func()
	explore = func() {
		if len(cur) == len(nums) {
			out = append(out, slices.Clone(cur)) // copy: cur keeps changing
			return
		}
		for i, n := range nums {
			if used[i] {
				continue
			}
			used[i], cur = true, append(cur, n)    // choose
			explore()                              // explore
			used[i], cur = false, cur[:len(cur)-1] // un-choose
		}
	}
	explore()
	return out
}

// combinationSum: every multiset of cands (reuse allowed) that adds to target.
func combinationSum(cands []int, target int) [][]int {
	slices.Sort(cands)
	var out [][]int
	var cur []int
	var explore func(start, remain int)
	explore = func(start, remain int) {
		if remain == 0 {
			out = append(out, slices.Clone(cur))
			return
		}
		for i := start; i < len(cands); i++ {
			if cands[i] > remain {
				break // sorted, so every later candidate is too big as well
			}
			cur = append(cur, cands[i])
			explore(i, remain-cands[i]) // i, not i+1: the same value may repeat
			cur = cur[:len(cur)-1]
		}
	}
	explore(0, target)
	return out
}

func main() {
	fmt.Println(permutations([]int{1, 2, 3}))
	fmt.Println(combinationSum([]int{7, 3, 6, 2}, 7))
}

package main

import (
	"cmp"
	"fmt"
	"slices"
)

// merge overlapping [start, end] intervals.
func merge(intervals [][]int) [][]int {
	slices.SortFunc(intervals, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
	var out [][]int
	for _, iv := range intervals {
		if n := len(out); n > 0 && iv[0] <= out[n-1][1] {
			out[n-1][1] = max(out[n-1][1], iv[1]) // overlap: extend the last one
		} else {
			out = append(out, []int{iv[0], iv[1]}) // gap: a new interval (a copy)
		}
	}
	return out
}

// minRooms: meetings needed at once; a meeting ending at t frees its room for one starting at t.
func minRooms(meetings [][2]int) int {
	starts := make([]int, len(meetings))
	ends := make([]int, len(meetings))
	for i, m := range meetings {
		starts[i], ends[i] = m[0], m[1]
	}
	slices.Sort(starts)
	slices.Sort(ends)
	rooms, e := 0, 0
	for _, s := range starts {
		if s >= ends[e] {
			e++ // the earliest-ending meeting is over: reuse its room
		} else {
			rooms++
		}
	}
	return rooms
}

func main() {
	fmt.Println(merge([][]int{{1, 3}, {8, 10}, {2, 6}, {15, 18}, {17, 20}}))
	fmt.Println(minRooms([][2]int{{0, 30}, {5, 10}, {15, 20}}), minRooms([][2]int{{1, 5}, {5, 8}, {8, 10}}))
}

package main

import "fmt"

var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func countIslands(rows []string) int {
	g := make([][]byte, len(rows))
	for i, r := range rows {
		g[i] = []byte(r) // strings are immutable; copy so we can mark cells
	}
	var sink func(r, c int)
	sink = func(r, c int) { // DFS: turn a whole island into water
		if r < 0 || c < 0 || r >= len(g) || c >= len(g[r]) || g[r][c] != '#' {
			return
		}
		g[r][c] = '.'
		for _, d := range dirs {
			sink(r+d[0], c+d[1])
		}
	}
	count := 0
	for r := range g {
		for c := range g[r] {
			if g[r][c] == '#' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}

// shortest: fewest moves from (sr, sc) to (gr, gc) through '.', or -1.
func shortest(maze []string, sr, sc, gr, gc int) int {
	dist := make([][]int, len(maze))
	for i := range dist {
		dist[i] = make([]int, len(maze[i]))
		for j := range dist[i] {
			dist[i][j] = -1 // -1 = not visited yet
		}
	}
	dist[sr][sc] = 0
	queue := [][2]int{{sr, sc}}
	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 && c >= 0 && r < len(maze) && c < len(maze[r]) && maze[r][c] == '.' && dist[r][c] == -1 {
				dist[r][c] = dist[cur[0]][cur[1]] + 1
				queue = append(queue, [2]int{r, c})
			}
		}
	}
	return dist[gr][gc]
}

func main() {
	fmt.Println("islands:", countIslands([]string{
		"##...",
		"#..#.",
		"..##.",
		"#...#",
	}))
	maze := []string{
		"...#",
		"##.#",
		"....",
		".##.",
	}
	fmt.Println("to (3,3):", shortest(maze, 0, 0, 3, 3))
	fmt.Println("to (3,0):", shortest(maze, 0, 0, 3, 0))
	fmt.Println("to (3,1):", shortest(maze, 0, 0, 3, 1))
}

package main

import "fmt"

// rob: max money from houses in a row, never robbing two neighbours.
func rob(houses []int) int {
	skip, take := 0, 0 // best so far if the previous house was skipped / taken
	for _, money := range houses {
		skip, take = max(skip, take), skip+money
	}
	return max(skip, take)
}

// maxSubarray: largest sum of a non-empty contiguous run (Kadane).
func maxSubarray(a []int) int {
	best, cur := a[0], a[0]
	for _, x := range a[1:] {
		cur = max(x, cur+x) // extend the run, or start again at x
		best = max(best, cur)
	}
	return best
}

// uniquePaths: ways from top-left to bottom-right moving only right or down.
func uniquePaths(rows, cols int) int {
	row := make([]int, cols)
	for c := range row {
		row[c] = 1 // one way along the top edge
	}
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			row[c] += row[c-1] // from above (old row[c]) + from the left
		}
	}
	return row[cols-1]
}

func main() {
	fmt.Println("rob =", rob([]int{2, 7, 9, 3, 1}))
	fmt.Println("max subarray =", maxSubarray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
	fmt.Println("paths 3x7 =", uniquePaths(3, 7))
}