In-place array patterns

package main
 
import "fmt"
 
func main() {
	nums := []int{4, 3, 2, 7, 8, 2, 3, 1} // values 1..n, some repeated, some missing
	i := 0
	for i < len(nums) {
		want := nums[i] - 1 // the index where nums[i] belongs
		if nums[i] != nums[want] {
			nums[i], nums[want] = nums[want], nums[i]
			fmt.Printf("i=%d swap %d into index %d -> %v\n", i, nums[want], want, nums)
		} else {
			i++ // in place, or its spot already holds a copy
		}
	}
	for i, n := range nums {
		if n != i+1 {
			fmt.Printf("index %d holds %d: %d is missing, %d is a duplicate\n", i, n, i+1, n)
		}
	}
}

i=0 swap 4 into index 3 -> [7 3 2 4 8 2 3 1]
i=0 swap 7 into index 6 -> [3 3 2 4 8 2 7 1]
i=0 swap 3 into index 2 -> [2 3 3 4 8 2 7 1]
i=0 swap 2 into index 1 -> [3 2 3 4 8 2 7 1]
i=4 swap 8 into index 7 -> [3 2 3 4 1 2 7 8]
i=4 swap 1 into index 0 -> [1 2 3 4 3 2 7 8]
index 4 holds 3: 5 is missing, 3 is a duplicate
index 5 holds 2: 6 is missing, 2 is a duplicate

package main
 
import (
	"fmt"
	"slices"
)
 
// cyclicSort places each value v (1..n) at index v-1. Each swap fixes one value, so it is O(n).
func cyclicSort(nums []int) {
	for i := 0; i < len(nums); {
		want := nums[i] - 1
		if want >= 0 && want < len(nums) && nums[i] != nums[want] {
			nums[i], nums[want] = nums[want], nums[i]
		} else {
			i++
		}
	}
}
 
// findDisappeared returns every value in 1..n that is missing.
func findDisappeared(nums []int) []int {
	cyclicSort(nums)
	var out []int
	for i, n := range nums {
		if n != i+1 {
			out = append(out, i+1)
		}
	}
	return out
}
 
// firstMissingPositive ignores values outside 1..n; the first slot that is wrong is the answer.
func firstMissingPositive(nums []int) int {
	cyclicSort(nums)
	for i, n := range nums {
		if n != i+1 {
			return i + 1
		}
	}
	return len(nums) + 1
}
 
// missingNumber in 0..n: XOR every index and value; pairs cancel, the missing one remains.
func missingNumber(nums []int) int {
	x := len(nums)
	for i, n := range nums {
		x ^= i ^ n
	}
	return x
}
 
// findDuplicate without modifying nums: values are "next" pointers, so a duplicate is a cycle entrance.
func findDuplicate(nums []int) int {
	slow, fast := nums[0], nums[nums[0]]
	for slow != fast {
		slow, fast = nums[slow], nums[nums[fast]]
	}
	slow = 0
	for slow != fast {
		slow, fast = nums[slow], nums[fast]
	}
	return slow
}
 
// findDuplicates marks a value v as seen by negating nums[v-1].
func findDuplicates(nums []int) []int {
	var out []int
	for _, n := range nums {
		v := abs(n)
		if nums[v-1] < 0 {
			out = append(out, v)
		} else {
			nums[v-1] = -nums[v-1]
		}
	}
	return out
}
 
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
 
// majority: Boyer-Moore vote. A different value cancels one vote; the majority survives.
func majority(nums []int) int {
	cand, votes := 0, 0
	for _, n := range nums {
		if votes == 0 {
			cand = n
		}
		if n == cand {
			votes++
		} else {
			votes--
		}
	}
	return cand
}
 
// majorityThird: at most two values can appear more than n/3 times. Keep two candidates, then verify.
func majorityThird(nums []int) []int {
	c1, c2, v1, v2 := 0, 1, 0, 0 // distinct starting candidates
	for _, n := range nums {
		switch {
		case n == c1:
			v1++
		case n == c2:
			v2++
		case v1 == 0:
			c1, v1 = n, 1
		case v2 == 0:
			c2, v2 = n, 1
		default:
			v1--
			v2--
		}
	}
	var out []int
	for _, c := range []int{c1, c2} {
		count := 0
		for _, n := range nums {
			if n == c {
				count++
			}
		}
		if count > len(nums)/3 {
			out = append(out, c)
		}
	}
	return out
}
 
// nextPermutation rearranges nums into the next larger order, or the smallest if it is the last.
func nextPermutation(nums []int) {
	i := len(nums) - 2
	for i >= 0 && nums[i] >= nums[i+1] { // find the rightmost ascent
		i--
	}
	if i >= 0 {
		j := len(nums) - 1
		for nums[j] <= nums[i] { // rightmost value larger than nums[i]
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	slices.Reverse(nums[i+1:]) // the suffix was descending; make it ascending
}
 
func main() {
	fmt.Println(findDisappeared([]int{4, 3, 2, 7, 8, 2, 3, 1}))
	fmt.Println(firstMissingPositive([]int{3, 4, -1, 1}), firstMissingPositive([]int{7, 8, 9}), firstMissingPositive([]int{1, 2, 0}))
	fmt.Println(missingNumber([]int{3, 0, 1}), missingNumber([]int{9, 6, 4, 2, 3, 5, 7, 0, 1}))
	fmt.Println(findDuplicate([]int{1, 3, 4, 2, 2}), findDuplicate([]int{3, 1, 3, 4, 2}))
	fmt.Println(findDuplicates([]int{4, 3, 2, 7, 8, 2, 3, 1}))
	fmt.Println(majority([]int{2, 2, 1, 1, 1, 2, 2}), majorityThird([]int{3, 2, 3}), majorityThird([]int{1, 2}))
	for _, p := range [][]int{{1, 2, 3}, {1, 3, 2}, {3, 2, 1}, {1, 5, 8, 4, 7, 6, 5, 3, 1}} {
		before := slices.Clone(p)
		nextPermutation(p)
		fmt.Println(before, "->", p)
	}
}

[5 6]
2 1 3
2 8
2 3
[2 3]
2 [3] [2 1]
[1 2 3] -> [1 3 2]
[1 3 2] -> [2 1 3]
[3 2 1] -> [1 2 3]
[1 5 8 4 7 6 5 3 1] -> [1 5 8 5 1 3 4 6 7]