Array

LeetCode 2761 note: sieve primes below n, then try x up to n / 2; when x and n - x are both prime, they form a pair

LeetCode 2523 note: sieve the primes in range, since only adjacent primes can be closest; or trial-divide rightward from left and stop at the first twin primes with gap 2

LeetCode 1998 note: numbers in one component can be permuted freely; union each number with its prime factors via SPF, and the array sorts iff each position’s old and new values share a group

LeetCode 1001 note: one counter each for rows, columns and both diagonals (r - c, r + c), plus a set of lit lamps; turning one off decrements all four

LeetCode 4067 note: subarrays of a valid window stay valid, so slide; adding x only needs checks involving x: x as an addend (x + y in the window) or x as the sum (x - y in the window)

LeetCode 622 note: a fixed array plus head and count, every position taken modulo the capacity, and count deciding empty versus full

LeetCode 2218 note: piles are taken from the top, so taking x coins is worth a prefix sum; a grouped knapsack with dp[j] = the best value taking j coins so far, enumerating how many from each pile

LeetCode 1246 note: interval DP taking the minimum of removing arr[i] alone, removing equal ends together with the inside, or splitting into two parts

LeetCode 1425 note: dp[i] = nums[i] + max(0, max of the previous k dp values); that max is a sliding window maximum, available in O(1) from a monotonic deque

LeetCode 2963 note: all occurrences of a value must share a part, so last occurrences cut the array into b indivisible blocks; each boundary may be cut or not, giving 2^(b-1)

LeetCode 2163 note: try every boundary k between the two parts; the left takes the n smallest of nums[:k] (a max-heap) and the right the n largest of nums[k:] (a min-heap), one prefix and one suffix pass

LeetCode 1627 note: no pairwise GCDs; for each z > threshold, connect all multiples of z, O(n log n) unions in total