Two Pointers

// opposite-ends template on sorted data: each comparison rules out one element for good.
func pairTemplate(sorted []int, target int) (int, int, bool) {
	left, right := 0, len(sorted)-1
	for left < right {
		sum := sorted[left] + sorted[right]
		if sum == target {
			return left, right, true
		} else if sum < target {
			left++ // too small: nothing paired with sorted[left] can reach target
		} else {
			right-- // too big: nothing paired with sorted[right] can reach target
		}
	}
	return 0, 0, false
}

// TwoSumSorted: 1-based indices of two numbers in sorted input summing to target.
func TwoSumSorted(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		sum := numbers[left] + numbers[right]
		if sum == target {
			return []int{left + 1, right + 1}
		} else if sum < target {
			left++
		} else {
			right--
		}
	}
	return nil
}

// RemoveDuplicates: in a sorted slice keep one of each value, in place.
// Same-direction pointers: read scans everything, write marks the end of the kept prefix.
func RemoveDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	write := 1
	for read := 1; read < len(nums); read++ {
		if nums[read] != nums[write-1] {
			nums[write] = nums[read]
			write++
		}
	}
	return write
}

// MoveZeroes: push zeros to the end, keeping the order of the rest.
func MoveZeroes(nums []int) {
	write := 0
	for read := range nums {
		if nums[read] != 0 {
			nums[write], nums[read] = nums[read], nums[write]
			write++
		}
	}
}

// ThreeSum: unique triplets summing to zero.
// Fix one number, then run the opposite-ends scan on the rest; skip duplicates.
func ThreeSum(nums []int) [][]int {
	sort.Ints(nums)
	out := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break // everything after is positive too
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum < 0 {
				left++
			} else if sum > 0 {
				right--
			} else {
				out = append(out, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				for left < right && nums[left] == nums[left-1] {
					left++
				}
			}
		}
	}
	return out
}

// MaxArea: most water between two vertical lines.
// Width only shrinks, so the only way to improve is to move the shorter wall.
func MaxArea(height []int) int {
	best, left, right := 0, 0, len(height)-1
	for left < right {
		h := min(height[left], height[right])
		best = max(best, h*(right-left))
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return best
}

// Trap: water above a bar = min(tallest bar on its left, tallest bar on its right) - its height.
// Two pointers: the side with the SHORTER wall is the limiting side, so its water level is already known.
func Trap(height []int) int {
	left, right := 0, len(height)-1
	leftMax, rightMax, water := 0, 0, 0
	for left < right {
		if height[left] < height[right] {
			leftMax = max(leftMax, height[left]) // the right wall is at least this tall, so leftMax limits
			water += leftMax - height[left]
			left++
		} else {
			rightMax = max(rightMax, height[right])
			water += rightMax - height[right]
			right--
		}
	}
	return water
}

// IsPalindrome: ignoring case and non-alphanumerics, does it read the same both ways?
func IsPalindrome(s string) bool {
	alnum := func(c byte) bool {
		return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'
	}
	lower := func(c byte) byte {
		if c >= 'A' && c <= 'Z' {
			return c + 32
		}
		return c
	}
	left, right := 0, len(s)-1
	for left < right {
		if !alnum(s[left]) {
			left++
		} else if !alnum(s[right]) {
			right--
		} else if lower(s[left]) != lower(s[right]) {
			return false
		} else {
			left++
			right--
		}
	}
	return true
}