Arrays & Hashing

In-place Index Tricks

Use the array itself as a hash map when values are in 1..n: cyclic sort and sign marking.

Medium, about 75 minutes to practise.

1Understand

The idea

When values lie in 1..n, the array can serve as its own hash map: value v "belongs" at index v, 1. Swap each value into its home (cyclic sort), or flip the sign at its home to mark it as seen. Missing and duplicate values then show up as indices that are out of place, in O(n) time and O(1) extra space.

Intuition

When values lie in 1..n, the array can be its own hash map: value v "belongs" at index v, 1. Cyclic sort swaps each value toward home; sign marking flips the sign at the home index to mean "seen".

Missing and duplicate values then show up as indices that are out of place or never marked. You get O(n) time and O(1) extra space, the interview constraint that rules out a separate set.

Skip or special-case values outside 1..n before using them as indices.

What you will be able to do

  • Place each value at its index with swaps
  • Mark seen values by negating
  • Read the answer from misplaced positions

When to use it

  • Values are in the range 1..n (or 0..n)
  • Find missing or duplicate numbers
  • O(1) extra space required

2See it

Walkthrough

Mark presence with sign

nums = [1, 3, 1] in 1..n, negate index nums[i]−1 to mark seen.

1 / 6

i
1
3
1
012
i → index 0

In-place marking: values live in 1..n, so index abs(x)−1 is the slot for value x.

idx = abs(nums[i]) - 1

Live template

Line 1 active

1i = 0
2while i < n:
3 j = nums[i] - 1
4 if 0 <= j < n and nums[i] != nums[j]:
5 nums[i], nums[j] = nums[j], nums[i]
6 else:
7 i += 1

Complexity: time O(n), space O(1)

Time O(n); extra space O(1) aside from the answer list. You mutate the input, if that is forbidden, fall back to a hash set O(n) space. Sign marking needs nonzero values; cyclic sort needs care with duplicates and out-of-range entries.

Read the walkthrough as text

Find all duplicates. nums = [4, 3, 2, 7, 8, 2, 3, 1] (values in 1..n).

  1. For each value v, look at index v - 1. If nums[v-1] is positive, negate it (first visit).
  2. If it is already negative, v is a duplicate, record it.
  3. After one pass, duplicates are [2, 3].

Cyclic-sort variant: while nums[i] != i+1, swap nums[i] with nums[nums[i]-1], but only advance i when the current slot is correct, otherwise equal swaps loop forever.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Cyclic sort

    Example. Values 1..n, place each value at index value-1.

    How. While nums[i] out of place, swap nums[i] with nums[nums[i]-1]; only advance when fixed or invalid.

  • Missing number(s)

    Example. One missing in 1..n or multiple missing in a range.

    How. After cyclic sort, scan for index where nums[i] != i+1.

  • Find all duplicates

    Example. All values that appear twice in 1..n.

    How. Cyclic sort or negate nums[abs(x)-1] to mark seen indices.

  • First missing positive

    Example. Smallest positive integer not in the array.

    How. Cyclic sort only values in [1, n]; first i with nums[i] != i+1 answers i+1.

  • Sign marking for seen values

    Example. O(1) extra space duplicate detection when values map to indices.

    How. Flip sign of nums[abs(x)-1]; positive afterward means first repeat.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Swap loop never ends

    Why it happens. You swap on every mismatch without checking whether the target slot already holds the value.

    How it fails. nums = [1,1]: swap nums[0] with nums[0] forever, infinite loop.

    Fix. Only swap when 0 <= j < n and nums[i] != nums[j]; otherwise advance i.

  • Advances too early

    Why it happens. After a swap, moving i++ feels like progress.

    How it fails. Swap 3 into index 0 but i becomes 1 before re-checking index 0, 3 never gets placed at index 2.

    Fix. After swapping, do not increment i until nums[i] is correct or proven unplaceable.

  • Out-of-range values

    Why it happens. Cyclic sort assumes all values are in 1..n.

    How it fails. nums = [7,8,9], n=3: index nums[7-1] is out of range, must skip values outside [1,n].

    Fix. If val < 1 or val > n, only i++, never index with val-1 outside the range.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons