When the values are a permutation of a known range, the array is its own index. Put every value in its home slot. Then the odd ones out name themselves.
This is the narrowest pattern on the site. It is also the easiest to spot once you know it. It only applies when the numbers come from a bounded range like 1..n. When it applies, it beats sorting and beats hashing. You get O(n) time with O(1) space, on a plain int[].
n numbers from a bounded range tied to n, usually 1..n or 0..n. The question asks for the missing, duplicated, corrupted, or smallest absent value. Then comes the constraint that seals it: O(n) time and O(1) space.HashSet<int> or a bool[] seen array.ReadOnlySpan<int> or IReadOnlyList<int> means hands off. That is when Find the Duplicate Number switches to Floyd’s cycle detection. Both patterns claim that problem. The constraint decides which one is meant.1..n, value v has an obvious home: index v - 1. Walk the array. If the value at i is not home, swap it to its home. Repeat at the same i until the value there is home, then move on. When the pass ends, every index that does not hold its own value is an anomaly. It points straight at the answer.Reading the figure. Red cells hold a value that lives somewhere else. Green cells hold their own value. The purple arrow is one swap. Each swap turns at least one cell green for good.
Once the placement pass is done, one linear scan reads off the result. What you look for depends on the question.
i where nums[i] != i (or != i + 1).List<int>.The loop is a while that sometimes does not advance i. So linear time needs an argument. It is short, and interviewers like it.
n values, so the whole run makes at most n swaps. Separately, i advances at most n times. Total work is at most 2n steps, so O(n).Put another way: the count of seated values never goes down. Every pass that does not advance i raises it by at least one. The loop cannot spin.
public static class CyclicSort
{
/// <summary>Place every value v of 1..n at index v - 1, in place.</summary>
/// <param name="nums">Values in 1..nums.Length. Mutated.</param>
/// <returns>Nothing. The array itself is the result.</returns>
/// <example><c>Sort([3, 1, 4, 2])</c> leaves the array as [1, 2, 3, 4].</example>
public static void Sort(int[] nums)
{
int i = 0; // 0: start scanning at the first slot
// i is the slot we are fixing. Invariant: slots 0..i-1 are settled.
// Each holds its own value, or a duplicate whose home is taken.
while (i < nums.Length)
{
// - 1: values are 1-based, indices are 0-based. Value v lives at v - 1.
int home = nums[i] - 1; // where nums[i] wants to live
// If home already holds the same value, a swap would loop forever.
if (nums[i] != nums[home]) // compare VALUES, not indices
{
// Each swap seats one value for good, so at most n swaps.
// Do not advance i: a new value just landed here and needs a home.
(nums[i], nums[home]) = (nums[home], nums[i]);
}
else
{
i++; // settled, or a duplicate. Move on
}
}
}
}
For a 0..n range, drop the - 1: int home = nums[i];. That is the only change.
The swap line uses a tuple swap. C# reads both right-hand values before it writes either slot. So it is as safe as the three-line version with a temp, and much shorter.
i when a swap would gain nothing, which is what stops it looping on duplicates.Reading the figure. The amber box is slot i. Green means the value sits at its home, index v - 1. Red means it does not. The purple arrow is the swap, from slot i to the home of its value. On the left, a swap brings in a new value, so i stays put. On the right, the home already holds a 2. So the loop gives up on this copy and moves on.
nums[i] != nums[home] and not i != home. With duplicates the two differ. Take [2, 2]. At i = 0 the home is index 1, so i != home is true. You swap and get [2, 2] again, forever. Comparing values sees that the target already holds this value. There is nothing to gain, so it advances. This one line is the most common bug in the pattern.i++ after a swap. The value swapped into slot i has not been checked yet. Only advance when nothing was swapped. A for loop hides this bug, so use while.0..n and 1..n. Write the home formula down before you write the loop.nums[i] - 1 can be negative or huge. C# throws IndexOutOfRangeException. Guard it first.(nums[i], nums[home]) = (nums[home], nums[i]) is safe. The three-line temp version breaks if you write nums[nums[i] - 1] after nums[i] has changed. Always copy home into a local first.An array nums holds n distinct numbers from the range 0..n. Exactly one number in that range is absent. Return it.
0..n, so the home of value v is index v, with no offset.n has no home, because the array only has indices 0..n-1. Skip it during placement. It just sits wherever it lands.n itself was missing.public static class MissingNumber
{
/// <summary>The one value of 0..n absent from nums.</summary>
/// <param name="nums">n distinct integers from 0..n. Mutated in place.</param>
/// <returns>The missing value.</returns>
/// <example><c>MissingNumber.Find([3, 0, 1])</c> returns 2.</example>
public static int Find(int[] nums)
{
int n = nums.Length; // n slots, but n + 1 values 0..n
int i = 0; // 0: start at the first slot
// Invariant: slots 0..i-1 hold their own value, or hold n (no home).
while (i < n)
{
// No - 1 here: values start at 0, so value v lives at index v.
int home = nums[i]; // 0..n range, so home == value
// n has no slot to go to, so leave it where it is.
// home < n guards the index. nums[i] != nums[home] stops a self-swap.
if (home < n && nums[i] != nums[home])
{
(nums[i], nums[home]) = (nums[home], nums[i]); // one value lands
}
else
{
i++; // this slot is done. Next one
}
}
// Every value is home now. The first slot that does not hold its own
// index is the hole left by the missing value.
for (int index = 0; index < n; index++) // 0..n-1: every slot once
{
if (nums[index] != index)
{
return index;
}
}
return n; // every slot matched, so n is missing
}
}
nums = [3, 0, 1], n = 3:
i = 0, [3, 0, 1]: home of 3 is 3, out of range, advance.i = 1, [3, 0, 1]: home of 0 is 0, swap.i = 1, [0, 3, 1]: home of 3 is out of range, advance.i = 2, [0, 3, 1]: home of 1 is 1, swap.i = 2, [0, 1, 3]: home of 3 is out of range, advance. Done.Scan: index 2 holds 3, a mismatch. So the answer is 2.
Reading the figure. Each row is the array at one step. The amber box is slot i. Green values sit at home, which is index v here. Grey marks 3, which has no index to live at. The purple arrow sends a value home. Notice that 3 drifts right with each swap. It ends in the slot that 2 should own.
public static class MissingNumberShortcuts
{
/// <summary>Subtract the actual sum from the expected sum of 0..n.</summary>
/// <param name="nums">n distinct integers from 0..n. Not modified.</param>
/// <returns>The missing value.</returns>
/// <example><c>MissingNumberShortcuts.Gauss([3, 0, 1])</c> returns 2.</example>
public static int Gauss(int[] nums)
{
long n = nums.Length; // long: n * (n + 1) overflows int fast
// n * (n + 1) / 2: Gauss sum of 0..n. / 2 is exact since n * (n + 1) is even.
long expected = n * (n + 1) / 2;
long actual = 0; // 0: empty sum. long for the same reason
// value is the next number. Invariant: actual is the sum of all seen so far.
foreach (int value in nums)
{
actual += value;
}
return (int)(expected - actual); // the gap fits in int: it is in 0..n
}
/// <summary>XOR every index and value. Pairs cancel, the missing one survives.</summary>
/// <param name="nums">n distinct integers from 0..n. Not modified.</param>
/// <returns>The missing value.</returns>
/// <example><c>MissingNumberShortcuts.Xor([3, 0, 1])</c> returns 2.</example>
public static int Xor(int[] nums)
{
// Start with n: indices only reach n - 1, so n must be added by hand.
int result = nums.Length;
// index runs 0..n-1. Invariant: result is the XOR of n and every
// index and value seen so far.
for (int index = 0; index < nums.Length; index++)
{
result ^= index ^ nums[index]; // x ^ x == 0, so matched pairs vanish
}
return result; // only the unpaired value is left
}
}
int is 32 bits, and n * (n + 1) passes int.MaxValue once n is about 46,341. By default C# wraps around silently, with no exception. So do the math in long, or wrap it in checked(...) to get an OverflowException. The XOR version has no overflow at all, which is why it exists. Cyclic sort is still the one to know. It is the version that extends to all the missing numbers and to duplicates.nums = [0]: answer 1, from the final return n.nums = [1]: answer 0, from the scan.0.n, such as 100,000: the Gauss sum needs long.nums has n integers, each in 1..n. Some appear twice and some not at all. Return every value in 1..n that does not appear.
1..n home formula. The value check handles duplicates. A value that finds a copy of itself at home stops trying.index + 1 for each.public static class DisappearedNumbers
{
/// <summary>Every value of 1..n missing from nums.</summary>
/// <param name="nums">n integers in 1..n, repeats allowed. Mutated in place.</param>
/// <returns>The absent values, in increasing order.</returns>
/// <example><c>Find([4, 3, 2, 7, 8, 2, 3, 1])</c> returns [5, 6].</example>
public static List<int> Find(int[] nums)
{
int n = nums.Length; // n slots for values 1..n
int i = 0; // 0: start at the first slot
// Invariant: slots 0..i-1 hold their own value, or a duplicate.
while (i < n)
{
int home = nums[i] - 1; // - 1: value v lives at index v - 1
// Equal values mean home is taken, or this IS home. A swap would loop.
if (nums[i] != nums[home])
{
(nums[i], nums[home]) = (nums[home], nums[i]); // seat one value
}
else
{
i++; // settled or a duplicate. Move on
}
}
// A slot that does not hold index + 1 is the home of a missing value.
List<int> missing = [];
for (int index = 0; index < n; index++) // 0..n-1: scan every slot once
{
if (nums[index] != index + 1) // + 1: slot index should hold index + 1
{
missing.Add(index + 1); // + 1: back to the 1-based value
}
}
return missing;
}
}
[4, 3, 2, 7, 8, 2, 3, 1] becomes [1, 2, 3, 4, 3, 2, 7, 8] after placement. Indices 4 and 5 hold 3 and 2 instead of 5 and 6. So the answer is [5, 6]. The leftover values in those slots are the duplicates. That is the next problem for free.
Reading the figure. Green slots hold their own value, v at index v - 1. Red slots hold a value that belongs elsewhere. After placement only two red slots remain. Each one reads off as index + 1, the value that never showed up.
By the usual rule, the output list does not count as extra space. Say that out loud.
public static class DisappearedByMarking
{
/// <summary>Mark seen values by negating the number at their home index.</summary>
/// <param name="nums">n integers in 1..n, repeats allowed. Signs are changed.</param>
/// <returns>The absent values, in increasing order.</returns>
/// <example><c>DisappearedByMarking.Find([1, 1, 2])</c> returns [3].</example>
public static List<int> Find(int[] nums)
{
// index is the slot we read. Invariant: for every value read so far,
// the number at its home index is negative.
for (int index = 0; index < nums.Length; index++)
{
// Math.Abs: an earlier pass may have negated this slot already.
// - 1: value v lives at index v - 1.
int home = Math.Abs(nums[index]) - 1;
if (nums[home] > 0) // > 0: not marked yet
{
nums[home] = -nums[home]; // negate = "home of v was seen"
}
}
// A slot still > 0 was never marked, so its value index + 1 never appeared.
List<int> missing = [];
for (int index = 0; index < nums.Length; index++) // 0..n-1: every slot
{
if (nums[index] > 0) // > 0: never marked
{
missing.Add(index + 1); // + 1: back to the 1-based value
}
}
return missing;
}
}
Same cost. Reach for it when the values are positive and you want a one-pass mark. It flips signs but keeps sizes, so you can undo it with Math.Abs. Know it as the sibling trick. A LINQ one-liner like Enumerable.Range(1, n).Except(nums) also works. But it builds a hash set inside, so it is O(n) extra space.
[1, 1, 1]: returns [2, 3].nums has n + 1 integers, each in 1..n. Exactly one value repeats, maybe many times. Return it.
n + 1 slots but only n homes. By the pigeonhole principle, at least one slot must end up holding a value that is not its own.public static class FindDuplicate
{
/// <summary>
/// The one repeated value in n + 1 integers from 1..n. Mutates nums.
/// If the array must stay read-only, use Floyd's cycle detection instead.
/// </summary>
/// <param name="nums">n + 1 integers in 1..n with one repeated value.</param>
/// <returns>The repeated value.</returns>
/// <exception cref="ArgumentException">No duplicate is present.</exception>
/// <example><c>FindDuplicate.Find([1, 3, 4, 2, 2])</c> returns 2.</example>
public static int Find(int[] nums)
{
int i = 0; // 0: start at the first slot
// Invariant: slots 0..i-1 hold their own value, or the duplicate.
while (i < nums.Length)
{
int home = nums[i] - 1; // - 1: value v lives at index v - 1
// Equal values: home is taken, so nums[i] is settled or the duplicate.
if (nums[i] != nums[home])
{
(nums[i], nums[home]) = (nums[home], nums[i]); // seat one value
}
else
{
i++; // nothing to swap. Move on
}
}
// Exactly one slot is left holding a value that is not its own.
for (int index = 0; index < nums.Length; index++) // 0-based slots
{
if (nums[index] != index + 1) // + 1: slot index should hold index + 1
{
return nums[index]; // the extra copy that found no home
}
}
throw new ArgumentException("no duplicate found", nameof(nums));
}
}
[1, 3, 4, 2, 2] settles to [1, 2, 3, 4, 2]. Index 4 should hold 5. That value is out of range and never existed. Instead it holds 2, which is the duplicate.
Reading the figure. The amber box is slot i. Green values are home, red values are not. The purple arrow sends a value to index v - 1. In the last row, the 2 at index 4 tries to go home. It finds a 2 already there, so it stays. It is the only red cell, so it is the answer.
ReadOnlySpan<int>.[2, 2, 2, 2, 2]: still correct. The swap loop stops as soon as a copy is home.[1, 1]: answer 1.[1]: the method throws ArgumentException.Given an unsorted array of integers, find the smallest positive integer that is not present. It must run in O(n) time with O(1) extra space. Values may be negative, zero, or far larger than n.
n slots, the answer must lie in 1 .. n + 1. If the array held exactly 1, 2, …, n, the answer would be n + 1. Any other case leaves a gap below that. So every value outside 1..n does not matter. Negatives, zeros, and anything above n can be ignored. That one sentence turns an unbounded problem into a cyclic-sort problem.1..n at its home index. Guard the home index first, so out-of-range values are skipped. Without the guard, C# throws IndexOutOfRangeException.nums[index] != index + 1. That index plus one is the answer.1..n is present. Return n + 1.public static class FirstMissingPositive
{
/// <summary>Smallest positive integer absent from nums, O(n) time, O(1) space.</summary>
/// <param name="nums">Any integers, in any order. Mutated in place.</param>
/// <returns>The smallest missing positive. Always in 1..nums.Length + 1.</returns>
/// <example><c>FirstMissingPositive.Find([3, 4, -1, 1])</c> returns 2.</example>
public static int Find(int[] nums)
{
int n = nums.Length; // n slots: only values 1..n can matter
int i = 0; // 0: start at the first slot
// Invariant: slots 0..i-1 hold their own value, or junk that has no home.
while (i < n)
{
// - 1: value v lives at index v - 1. No overflow: int.MinValue - 1 would
// wrap, but a home that negative fails the bounds check either way.
int home = nums[i] - 1;
// Only values in 1..n have a home. The bounds check makes this safe
// for negatives, zeros and huge values. It must come first.
// 0 <= home && home < n is the same as 1 <= value <= n.
if (0 <= home && home < n && nums[i] != nums[home])
{
(nums[i], nums[home]) = (nums[home], nums[i]); // seat one value
}
else
{
i++; // junk, duplicate, or settled. Next
}
}
// The first slot not holding index + 1 names the answer.
for (int index = 0; index < n; index++) // 0..n-1: check every slot
{
if (nums[index] != index + 1) // + 1: slot index should hold index + 1
{
return index + 1; // + 1: back to the 1-based value
}
}
return n + 1; // 1..n all present, so n + 1 is missing
}
}
One honest wrinkle: int.MinValue - 1 wraps to int.MaxValue in C#. That huge home still fails home < n, so the code stays correct. In a checked context it would throw instead. If an interviewer asks, say you would compare the value with nums[i] >= 1 && nums[i] <= n to avoid the subtraction.
nums = [3, 4, -1, 1], n = 4:
i = 0, [3, 4, -1, 1]: home of 3 is 2, swap with -1.i = 0, [-1, 4, 3, 1]: -1 has no home, advance.i = 1, [-1, 4, 3, 1]: home of 4 is 3, swap with 1.i = 1, [-1, 1, 3, 4]: home of 1 is 0, swap with -1.i = 1, [1, -1, 3, 4]: -1 has no home, advance.i = 2, 3, [1, -1, 3, 4]: 3 and 4 are already home, advance.Scan: index 0 holds 1, fine. Index 1 holds -1, not 2. Answer 2.
Reading the figure. The amber box is slot i. Green values are home at index v - 1. Grey marks -1, which has no home, so the bounds check skips it. The purple arrow sends a value home. In the scan row, red marks the first slot that does not hold index + 1. Its index plus one is the smallest missing positive.
0 <= home, a value of -5 gives home = -6. In C#, nums[-6] throws IndexOutOfRangeException. That is louder than Python, which quietly reads from the end of the list. But a crash is still a failed test. The && operator short-circuits, so put the bounds checks to the left of nums[home]. Then the array read never runs for a bad index. Say why out loud.A common C# speed trick folds both bounds into one compare. Casting to uint turns any negative into a huge number:
// (uint)home < (uint)n is true only for 0 <= home < n.
// A negative home becomes a value above 2^31, which is never < n.
if ((uint)home < (uint)n && nums[i] != nums[home]) { /* swap */ }The BCL uses this trick inside List<T>. In an interview the two plain compares read better. Mention the trick only if asked about speed.
[1, 2, 3]: nothing missing below n, so the answer is 4, from the final return.[7, 8, 9]: no value has a home. Nothing moves, and the answer is 1.n = 0, both loops skip, returns 1. Correct.[1, 1]: the value check stops the swap loop. Answer 2.int.MinValue: answer 1.v lives at index v - 1 for a 1..n range, and at index v for a 0..n range.nums[i] != nums[home], never indices. Comparing indices loops forever on duplicates.i only when no swap happened. Use while, not for. The value swapped in still needs a check.n swaps, because every swap seats a value for good.&&. In C#, also watch int overflow in sum tricks.Pattern 6, In-Place Reversal of a Linked List, is the last of the pointer-surgery patterns. Same spirit and no extra memory. But the state you carry is three references instead of an index.