PK

PKBytes

Explore tracks
Chapter 8: Arrays and Dynamic Arrays
8.08Beginner / Intermediate5 topics18 min5 interactive animations

Array optimizations

When values are bounded by the array length, the values themselves can serve as indexes. This lesson covers in-place cycle decomposition of a permutation, index placement, cyclic sort, pigeonhole indexing with sign flipping, and finding missing or duplicate numbers in O(n) time and O(1) space.

Learning goals

  • Place each value at the index it names
  • Decompose a permutation into cycles
  • Find missing and duplicate numbers without extra space

Prerequisites

Partitioning problems
8.08.1

In-place cycle decomposition

A permutation splits into disjoint cycles. To put a permutation in order in place, follow a cycle: swap the element at index i with the element at the index it points to, until position i holds i. Every swap fixes one element permanently, so a cycle of length L needs L - 1 swaps and the whole permutation needs n minus the number of cycles.

Enter any permutation of 0..n-1 and read the cycle count.

Java
1static int sortPermutation(int[] p) {
2    int cycles = 0;
3    for (int i = 0; i < p.length; i++) {
4        if (p[i] == i) continue;
5        cycles++;
6        while (p[i] != i) { int j = p[i]; int t = p[i]; p[i] = p[j]; p[j] = t; }
7    }
8    return cycles;
9}

Applying a permutation in place by following cycles

Interactive · edit the input

Your input

Try

int[] arr · length 6

2
0
1
4
3
5
012345
Being comparedJust placedIn its home slot
Setup

Each value points to the slot it must move to. Following those pointers walks a cycle; every swap puts one value in its final slot.

Step 1 / 11
Java
1static int sortPermutation(int[] p) {            // p is a permutation of 0..n-1
2    int cycles = 0;
3    for (int i = 0; i < p.length; i++) {
4        if (p[i] == i) continue;                  // fixed point or already placed
5        cycles++;
6        while (p[i] != i) swap(p, i, p[i]);       // every swap fixes one element for good
7    }
8    return cycles;                                // cycles of length >= 2
9}

Live state

0 swaps0 cycles

cycles

0

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L2cycles=0Each value points to the slot it must move to. Following those pointers walks a cycle; every swap puts one value in its final slot.
2L5i=0 p[i]=2 cycles=1Index 0 starts a new cycle (cycle 1).
3L6i=0 j=2 swaps=1Swap p[0] with p[2]: the value 2 lands at index 2, its final slot. Index 0 now holds 1.
4L6i=0 j=1 swaps=2Swap p[0] with p[1]: the value 1 lands at index 1, its final slot. The cycle is closed.
5L4i=1 p[i]=1p[1] = 1: this slot is already correct.
6L4i=2 p[i]=2p[2] = 2: this slot is already correct.
7L5i=3 p[i]=4 cycles=2Index 3 starts a new cycle (cycle 2).
8L6i=3 j=4 swaps=3Swap p[3] with p[4]: the value 4 lands at index 4, its final slot. The cycle is closed.
9L4i=4 p[i]=4p[4] = 4: this slot is already correct.
10L4i=5 p[i]=5p[5] = 5: this slot is already correct.
11L8return=2 swaps=32 cycles of length 2 or more, 3 swaps: a cycle of length L needs exactly L - 1 swaps, so the total is n minus the number of cycles (counting fixed points).
8.08.2

Index placement

Index placement puts each value at the index it names: value v goes to index v - 1 (or v for 0-based data). Swap the current element to its home; the element that arrives is re-examined. Each swap places one value for good, so the total number of swaps is at most n and the whole process is O(n).

Values outside 1..n have no home and are skipped.

Java
1int i = 0;
2while (i < a.length) {
3    int j = a[i] - 1;                                   // home of a[i]
4    if (a[i] >= 1 && a[i] <= a.length && a[j] != a[i]) swap(a, i, j);
5    else i++;
6}

Cyclic sort: put each value at index value - 1

Interactive · edit the input

Your input

Try

int[] arr · length 4

3
4
-1
1
0123
In its home slotBeing comparedJust placedWrong slot (missing or duplicate)
Setup

A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.

Step 1 / 14
Java
1static int firstMissingPositive(int[] a) {
2    int i = 0, n = a.length;
3    while (i < n) {
4        int j = a[i] - 1;                              // home slot of a[i]
5        if (a[i] >= 1 && a[i] <= n && a[j] != a[i]) swap(a, i, j);
6        else i++;
7    }
8    for (i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;   // first slot holding the wrong value
9    return n + 1;
10}

Live state

0 swaps

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L2n=4A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.
2L5i=0 a[i]=3 home=23 belongs at index 2, which holds -1: swap them.
3L5i=0 swaps=13 is now home at index 2. Do not advance i: the value that arrived at index 0 still needs to be checked.
4L5i=0 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
5L5i=1 a[i]=4 home=34 belongs at index 3, which holds 1: swap them.
6L5i=1 swaps=24 is now home at index 3. Do not advance i: the value that arrived at index 1 still needs to be checked.
7L5i=1 a[i]=1 home=01 belongs at index 0, which holds -1: swap them.
8L5i=1 swaps=31 is now home at index 0. Do not advance i: the value that arrived at index 1 still needs to be checked.
9L5i=1 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
10L5i=2 a[i]=3 home=23 is already at its home index 2.
11L5i=3 a[i]=4 home=34 is already at its home index 3.
12L8i=0 a[i]=1Index 0 holds 1.
13L8i=1 a[i]=-1Index 1 should hold 2 but holds -1: 2 is missing.
14L8return=2 swaps=3First missing positive: 2. Each swap places one value for good, so at most n swaps: O(n) time, O(1) space.
8.08.3

Cyclic sort

Cyclic sort sorts an array that holds the numbers 1..n by index placement, in O(n) time and O(1) space, instead of O(n log n). It is the right tool when the values are a permutation of 1..n, or when you only need to know which are missing or repeated. The while loop does not advance after a swap, because a new, unplaced value now sits at i.

The first preset has a missing 2; the second has a duplicate and a missing value.

Java
1static void cyclicSort(int[] a) {              // a is a permutation of 1..n
2    int i = 0;
3    while (i < a.length) {
4        int j = a[i] - 1;
5        if (a[i] != a[j]) swap(a, i, j); else i++;
6    }
7}

Cyclic sort: put each value at index value - 1

Interactive · edit the input

Your input

Try

int[] arr · length 4

3
4
-1
1
0123
In its home slotBeing comparedJust placedWrong slot (missing or duplicate)
Setup

A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.

Step 1 / 14
Java
1static int firstMissingPositive(int[] a) {
2    int i = 0, n = a.length;
3    while (i < n) {
4        int j = a[i] - 1;                              // home slot of a[i]
5        if (a[i] >= 1 && a[i] <= n && a[j] != a[i]) swap(a, i, j);
6        else i++;
7    }
8    for (i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;   // first slot holding the wrong value
9    return n + 1;
10}

Live state

0 swaps

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L2n=4A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.
2L5i=0 a[i]=3 home=23 belongs at index 2, which holds -1: swap them.
3L5i=0 swaps=13 is now home at index 2. Do not advance i: the value that arrived at index 0 still needs to be checked.
4L5i=0 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
5L5i=1 a[i]=4 home=34 belongs at index 3, which holds 1: swap them.
6L5i=1 swaps=24 is now home at index 3. Do not advance i: the value that arrived at index 1 still needs to be checked.
7L5i=1 a[i]=1 home=01 belongs at index 0, which holds -1: swap them.
8L5i=1 swaps=31 is now home at index 0. Do not advance i: the value that arrived at index 1 still needs to be checked.
9L5i=1 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
10L5i=2 a[i]=3 home=23 is already at its home index 2.
11L5i=3 a[i]=4 home=34 is already at its home index 3.
12L8i=0 a[i]=1Index 0 holds 1.
13L8i=1 a[i]=-1Index 1 should hold 2 but holds -1: 2 is missing.
14L8return=2 swaps=3First missing positive: 2. Each swap places one value for good, so at most n swaps: O(n) time, O(1) space.
8.08.4

Pigeonhole indexing

If an array of n values has every value in 1..n, the array doubles as a seen-set: use the sign of a[v - 1] to record whether v appeared. Reading a value, flip a[v - 1] to negative; if it is already negative, v is a duplicate. By the pigeonhole principle a duplicate exists exactly when some value is missing. O(n) time, O(1) space, but the input is modified (restore it by taking absolute values).

Run it and read both the duplicate list and the missing list.

Java
1static List<Integer> findDuplicates(int[] a) {
2    List<Integer> dups = new ArrayList<>();
3    for (int x : a) {
4        int idx = Math.abs(x) - 1;
5        if (a[idx] < 0) dups.add(Math.abs(x)); else a[idx] = -a[idx];
6    }
7    return dups;
8}

Pigeonhole indexing: find duplicates by flipping signs

Interactive · edit the input

Your input

Try

int[] arr · length 8

4
3
2
7
8
2
3
1
01234567
Value being readFlagged (seen)Duplicate detected

duplicates found

none yet
Setup

Every value is a valid index in 1..8, so the array doubles as a seen-set: the sign of a[v - 1] records whether v appeared.

Step 1 / 18
Java
1static List<Integer> findDuplicates(int[] a) {          // every value is in 1..n
2    List<Integer> dups = new ArrayList<>();
3    for (int x : a) {
4        int idx = Math.abs(x) - 1;
5        if (a[idx] < 0) dups.add(Math.abs(x));            // slot already flagged: seen before
6        else a[idx] = -a[idx];                            // flag value idx + 1 as seen
7    }
8    return dups;
9}
10// afterwards a[i] > 0 means i + 1 never appeared

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 18 steps
StepLineStateWhat happens
1L2Every value is a valid index in 1..8, so the array doubles as a seen-set: the sign of a[v - 1] records whether v appeared.
2L5i=0 x=4 idx=3 a[idx]=7a[3] is positive: first time we see 4. Flip its sign.
3L6i=0 x=4a[3] = -7 (flagged).
4L5i=1 x=3 idx=2 a[idx]=2a[2] is positive: first time we see 3. Flip its sign.
5L6i=1 x=3a[2] = -2 (flagged).
6L5i=2 x=2 idx=1 a[idx]=3a[1] is positive: first time we see 2. Flip its sign.
7L6i=2 x=2a[1] = -3 (flagged).
8L5i=3 x=7 idx=6 a[idx]=3a[6] is positive: first time we see 7. Flip its sign.
9L6i=3 x=7a[6] = -3 (flagged).
10L5i=4 x=8 idx=7 a[idx]=1a[7] is positive: first time we see 8. Flip its sign.
11L6i=4 x=8a[7] = -1 (flagged).
12L5i=5 x=2 idx=1 a[idx]=-3a[1] is already negative, so 2 appeared before: it is a duplicate.
13L5i=5 x=2Record 2 as a duplicate.
14L5i=6 x=3 idx=2 a[idx]=-2a[2] is already negative, so 3 appeared before: it is a duplicate.
15L5i=6 x=3Record 3 as a duplicate.
16L5i=7 x=1 idx=0 a[idx]=4a[0] is positive: first time we see 1. Flip its sign.
17L6i=7 x=1a[0] = -4 (flagged).
18L8return=[2, 3] missing=[5, 6]Duplicates: [2, 3]. Slots that stayed positive mean the value index + 1 never appeared: missing [5, 6]. O(n) time and O(1) extra space, but the input is modified.
8.08.5

Missing/duplicate numbers

Typical tasks: find the smallest missing positive, find all missing numbers in 1..n, or find the duplicate. After cyclic sort every index i that does not hold i + 1 reveals a missing value i + 1, and the value found there is a duplicate. Sign marking gives the same information with positive entries marking the missing values.

Compare the two methods: cyclic sort rearranges, sign marking flips signs.

Java
1static int firstMissingPositive(int[] a) {
2    int n = a.length;
3    for (int i = 0; i < n; ) {
4        int j = a[i] - 1;
5        if (a[i] >= 1 && a[i] <= n && a[j] != a[i]) { int t = a[i]; a[i] = a[j]; a[j] = t; }
6        else i++;
7    }
8    for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
9    return n + 1;
10}

Cyclic sort: put each value at index value - 1

Interactive · edit the input

Your input

Try

int[] arr · length 4

3
4
-1
1
0123
In its home slotBeing comparedJust placedWrong slot (missing or duplicate)
Setup

A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.

Step 1 / 14
Java
1static int firstMissingPositive(int[] a) {
2    int i = 0, n = a.length;
3    while (i < n) {
4        int j = a[i] - 1;                              // home slot of a[i]
5        if (a[i] >= 1 && a[i] <= n && a[j] != a[i]) swap(a, i, j);
6        else i++;
7    }
8    for (i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;   // first slot holding the wrong value
9    return n + 1;
10}

Live state

0 swaps

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L2n=4A value v in 1..4 belongs at index v - 1. Keep swapping a[i] to its home until a[i] is out of range or its home already holds the same value.
2L5i=0 a[i]=3 home=23 belongs at index 2, which holds -1: swap them.
3L5i=0 swaps=13 is now home at index 2. Do not advance i: the value that arrived at index 0 still needs to be checked.
4L5i=0 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
5L5i=1 a[i]=4 home=34 belongs at index 3, which holds 1: swap them.
6L5i=1 swaps=24 is now home at index 3. Do not advance i: the value that arrived at index 1 still needs to be checked.
7L5i=1 a[i]=1 home=01 belongs at index 0, which holds -1: swap them.
8L5i=1 swaps=31 is now home at index 0. Do not advance i: the value that arrived at index 1 still needs to be checked.
9L5i=1 a[i]=-1 home=none-1 is outside 1..4, so it has no home. Move on.
10L5i=2 a[i]=3 home=23 is already at its home index 2.
11L5i=3 a[i]=4 home=34 is already at its home index 3.
12L8i=0 a[i]=1Index 0 holds 1.
13L8i=1 a[i]=-1Index 1 should hold 2 but holds -1: 2 is missing.
14L8return=2 swaps=3First missing positive: 2. Each swap places one value for good, so at most n swaps: O(n) time, O(1) space.

Pigeonhole indexing: find duplicates by flipping signs

Interactive · edit the input

Your input

Try

int[] arr · length 8

4
3
2
7
8
2
3
1
01234567
Value being readFlagged (seen)Duplicate detected

duplicates found

none yet
Setup

Every value is a valid index in 1..8, so the array doubles as a seen-set: the sign of a[v - 1] records whether v appeared.

Step 1 / 18
Java
1static List<Integer> findDuplicates(int[] a) {          // every value is in 1..n
2    List<Integer> dups = new ArrayList<>();
3    for (int x : a) {
4        int idx = Math.abs(x) - 1;
5        if (a[idx] < 0) dups.add(Math.abs(x));            // slot already flagged: seen before
6        else a[idx] = -a[idx];                            // flag value idx + 1 as seen
7    }
8    return dups;
9}
10// afterwards a[i] > 0 means i + 1 never appeared

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 18 steps
StepLineStateWhat happens
1L2Every value is a valid index in 1..8, so the array doubles as a seen-set: the sign of a[v - 1] records whether v appeared.
2L5i=0 x=4 idx=3 a[idx]=7a[3] is positive: first time we see 4. Flip its sign.
3L6i=0 x=4a[3] = -7 (flagged).
4L5i=1 x=3 idx=2 a[idx]=2a[2] is positive: first time we see 3. Flip its sign.
5L6i=1 x=3a[2] = -2 (flagged).
6L5i=2 x=2 idx=1 a[idx]=3a[1] is positive: first time we see 2. Flip its sign.
7L6i=2 x=2a[1] = -3 (flagged).
8L5i=3 x=7 idx=6 a[idx]=3a[6] is positive: first time we see 7. Flip its sign.
9L6i=3 x=7a[6] = -3 (flagged).
10L5i=4 x=8 idx=7 a[idx]=1a[7] is positive: first time we see 8. Flip its sign.
11L6i=4 x=8a[7] = -1 (flagged).
12L5i=5 x=2 idx=1 a[idx]=-3a[1] is already negative, so 2 appeared before: it is a duplicate.
13L5i=5 x=2Record 2 as a duplicate.
14L5i=6 x=3 idx=2 a[idx]=-2a[2] is already negative, so 3 appeared before: it is a duplicate.
15L5i=6 x=3Record 3 as a duplicate.
16L5i=7 x=1 idx=0 a[idx]=4a[0] is positive: first time we see 1. Flip its sign.
17L6i=7 x=1a[0] = -4 (flagged).
18L8return=[2, 3] missing=[5, 6]Duplicates: [2, 3]. Slots that stayed positive mean the value index + 1 never appeared: missing [5, 6]. O(n) time and O(1) extra space, but the input is modified.

Practice ladder

Now try it yourself

Easy

  • Cyclic sort {3, 1, 2}
  • How many swaps sort the permutation {1, 2, 0}?

Medium

  • Find the missing number in {3, 0, 1} (values 0..n)
  • Find all duplicates in {4, 3, 2, 7, 8, 2, 3, 1}

Advanced

  • Find the duplicate in an array of n + 1 values in 1..n without modifying it (Floyd's cycle detection)

Key takeaways

  • Bounded values can be used as indexes: place each at its home slot.
  • A cycle of length L needs L - 1 swaps; each swap fixes one value.
  • Sign flipping and cyclic sort find missing and duplicate numbers in O(n) time and O(1) space.