8.04Beginner / Intermediate8 topics18 min8 interactive animations

One-dimensional patterns

The one-dimensional array patterns that show up everywhere: tracking min and max in one pass, finding the second largest, the k-th value that appears once, moving zeroes, removing duplicates, reversing, rotating and rearranging in place.

Learning goals

Solve single-pass scanning problems with O(1) extra state
Use read and write pointers to rewrite an array in place
Choose between in-place and extra-space solutions

Prerequisites

Core operationsFrequency counting

8.04.1

Min and max

Track the smallest and largest value in one pass: initialise from the first element (not from 0, which breaks when all values are negative), then update on each element. That is n - 1 comparisons per extreme, O(n) time and O(1) space.

Run the scan on your own array. The same pass also keeps the second largest.

Java

1static int[] minMax(int[] a) {
2    int min = a[0], max = a[0];
3    for (int i = 1; i < a.length; i++) {
4        if (a[i] < min) min = a[i];
5        if (a[i] > max) max = a[i];
6    }
7    return new int[]{min, max};
8}

One pass: min, max and second largest

Interactive · edit the input

int[] arr · length 6

012345

Being comparedLargest so farSecond largest so farSeen

Setup

Keep three running values while scanning once: the smallest, the largest and the largest value strictly below it.

Step 1 / 8

Java

1static int secondLargest(int[] a) {
2    int max = Integer.MIN_VALUE, second = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
3    for (int x : a) {
4        if (x < min) min = x;
5        if (x > max) { second = max; max = x; }
6        else if (x < max && x > second) second = x;   // strictly smaller: duplicates of max do not count
7    }
8    return second;                                       // MIN_VALUE means there is no second largest
9}

Live state

max

−∞

second

−∞

min

+∞

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	max=−∞ second=−∞ min=+∞	Keep three running values while scanning once: the smallest, the largest and the largest value strictly below it.
2	L5	i=0 x=12 max=12 second=−∞ min=12	12 > max: the old max becomes second, 12 is the new max.
3	L5	i=1 x=35 max=35 second=12 min=12	35 > max: the old max becomes second, 35 is the new max.
4	L6	i=2 x=1 max=35 second=12 min=1	1 is not above second (12): nothing changes.
5	L6	i=3 x=10 max=35 second=12 min=1	10 is not above second (12): nothing changes.
6	L6	i=4 x=34 max=35 second=34 min=1	34 is below max but above second: new second largest.
7	L6	i=5 x=1 max=35 second=34 min=1	1 is not above second (34): nothing changes.
8	L8	max=35 second=34 min=1 return=34	Min 1, max 35, second largest 34, all in one O(n) pass with O(1) space.

8.04.2

Second largest

Keep the largest and the largest value strictly below it. When a new maximum arrives, the old maximum becomes the second; otherwise a value that is below the maximum but above the second replaces the second. Duplicates of the maximum must not count as the second largest.

The preset with a duplicate maximum and the all-equal preset show both traps. Sorting would also work but costs O(n log n).

Java

1static OptionalInt secondLargest(int[] a) {
2    long first = Long.MIN_VALUE, second = Long.MIN_VALUE;   // long sentinel: a may contain Integer.MIN_VALUE
3    for (int x : a) {
4        if (x > first) { second = first; first = x; }
5        else if (x < first && x > second) second = x;
6    }
7    return second == Long.MIN_VALUE ? OptionalInt.empty() : OptionalInt.of((int) second);
8}

One pass: min, max and second largest

Interactive · edit the input

int[] arr · length 6

012345

Being comparedLargest so farSecond largest so farSeen

Setup

Keep three running values while scanning once: the smallest, the largest and the largest value strictly below it.

Step 1 / 8

Java

1static int secondLargest(int[] a) {
2    int max = Integer.MIN_VALUE, second = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
3    for (int x : a) {
4        if (x < min) min = x;
5        if (x > max) { second = max; max = x; }
6        else if (x < max && x > second) second = x;   // strictly smaller: duplicates of max do not count
7    }
8    return second;                                       // MIN_VALUE means there is no second largest
9}

Live state

max

−∞

second

−∞

min

+∞

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	max=−∞ second=−∞ min=+∞	Keep three running values while scanning once: the smallest, the largest and the largest value strictly below it.
2	L5	i=0 x=12 max=12 second=−∞ min=12	12 > max: the old max becomes second, 12 is the new max.
3	L5	i=1 x=35 max=35 second=12 min=12	35 > max: the old max becomes second, 35 is the new max.
4	L6	i=2 x=1 max=35 second=12 min=1	1 is not above second (12): nothing changes.
5	L6	i=3 x=10 max=35 second=12 min=1	10 is not above second (12): nothing changes.
6	L6	i=4 x=34 max=35 second=34 min=1	34 is below max but above second: new second largest.
7	L6	i=5 x=1 max=35 second=34 min=1	1 is not above second (34): nothing changes.
8	L8	max=35 second=34 min=1 return=34	Min 1, max 35, second largest 34, all in one O(n) pass with O(1) space.

8.04.3

Kth distinct

“Distinct” here means a value that appears exactly once; the k-th such value is counted in array order. Count the frequencies with a hash map in one pass, then scan again and count the values whose frequency is 1 until the k-th. That is O(n) time and O(distinct) space.

The second pass is needed to respect the original order, because a hash map has no order.

Java

1static int kthDistinct(int[] arr, int k) {
2    Map<Integer, Integer> freq = new HashMap<>();
3    for (int x : arr) freq.merge(x, 1, Integer::sum);
4    for (int x : arr) {
5        if (freq.get(x) == 1 && --k == 0) return x;
6    }
7    return -1;
8}

k-th value that appears exactly once

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedk-th uniqueRepeatedCounted

freq

empty

Setup

Find the 2-th value that occurs exactly once, in array order. First count every value, then scan again.

Step 1 / 14

Java

1static int kthDistinct(int[] arr, int k) {
2    Map<Integer, Integer> freq = new HashMap<>();
3    for (int x : arr) freq.merge(x, 1, Integer::sum);          // pass 1: count
4    for (int x : arr) {                                        // pass 2: keep original order
5        if (freq.get(x) == 1 && --k == 0) return x;
6    }
7    return -1;                                                 // fewer than k such values
8}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2	k=2	Find the 2-th value that occurs exactly once, in array order. First count every value, then scan again.
2	L3	i=0 x=4	Count 4: it now appears 1 time.
3	L3	i=1 x=7	Count 7: it now appears 1 time.
4	L3	i=2 x=4	Count 4: it now appears 2 times.
5	L3	i=3 x=9	Count 9: it now appears 1 time.
6	L3	i=4 x=2	Count 2: it now appears 1 time.
7	L3	i=5 x=7	Count 7: it now appears 2 times.
8	L3	i=6 x=5	Count 5: it now appears 1 time.
9	L5	i=0 x=4 k=2	4 repeats, so it is skipped.
10	L5	i=1 x=7 k=2	7 repeats, so it is skipped.
11	L5	i=2 x=4 k=2	4 repeats, so it is skipped.
12	L5	i=3 x=9 k=1	9 appears once: k drops to 1.
13	L5	i=4 x=2 k=0	2 is the unique value that brings k to 0: return it.
14	L5	return=2	Return 2. Two passes, O(n) time, O(distinct) space.

8.04.4

Move zeroes

Move every zero to the end while keeping the other values in order, in place. Use a read pointer that scans and a write pointer marking where the next non-zero belongs; swap when they differ. One pass, O(n) time and O(1) space, and the non-zero elements stay stable.

Duplicate values carry a/b tags in the animation so you can verify the order.

Java

1static void moveZeroes(int[] a) {
2    int write = 0;
3    for (int read = 0; read < a.length; read++) {
4        if (a[read] != 0) {
5            int t = a[write]; a[write] = a[read]; a[read] = t;
6            write++;
7        }
8    }
9}

Partition: move zeroes to the end (stable)

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedNon-zero, final orderJust swappedaEqual keys in original order

Setup

Same-direction pointers: read finds non-zeros, write is where the next one belongs.

Step 1 / 13

Java

1public static void moveZeroes(int[] arr) {
2    int write = 0;                        // arr[0..write-1]: non-zeros, original order
3    for (int read = 0; read < arr.length; read++) {
4        if (arr[read] != 0) {
5            swap(arr, write, read);
6            write++;
7        }
8    }
9}

Live state

0 swaps

write

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	write=0	Same-direction pointers: read finds non-zeros, write is where the next one belongs.
2	L4	read=0 write=0 arr[read]=0	Zero: leave it; it will drift to the end.
3	L4	read=1 write=0 arr[read]=1	Non-zero: move it to the write position.
4	L5	read=1 write=1	Swapped arr[0] and arr[1]; write = 1.
5	L4	read=2 write=1 arr[read]=0	Zero: leave it; it will drift to the end.
6	L4	read=3 write=1 arr[read]=3	Non-zero: move it to the write position.
7	L5	read=3 write=2	Swapped arr[1] and arr[3]; write = 2.
8	L4	read=4 write=2 arr[read]=12	Non-zero: move it to the write position.
9	L5	read=4 write=3	Swapped arr[2] and arr[4]; write = 3.
10	L4	read=5 write=3 arr[read]=0	Zero: leave it; it will drift to the end.
11	L4	read=6 write=3 arr[read]=5	Non-zero: move it to the write position.
12	L5	read=6 write=4	Swapped arr[3] and arr[6]; write = 4.
13	L9	write=4	Non-zeros keep their relative order (watch any a/b tags) and the 3 zeros sit at the end. O(n) time, 4 swaps.

8.04.5

Remove duplicates

In a sorted array duplicates are adjacent, so one pass with a write pointer keeps the first copy of each value and overwrites the rest. The method returns the new length; the slots after it are leftovers. O(n) time, O(1) space.

If the array is not sorted, sort first or use a hash set.

Java

1static int removeDuplicates(int[] a) {          // a is sorted
2    if (a.length == 0) return 0;
3    int write = 1;
4    for (int read = 1; read < a.length; read++) {
5        if (a[read] != a[write - 1]) a[write++] = a[read];
6    }
7    return write;
8}

Remove duplicates in place (read / write pointers)

Interactive · edit the input

int[] arr · length 9

012345678

Being comparedUnique prefixJust written

Setup

arr[0] is always kept. write marks the end of the unique prefix; read scans ahead.

Step 1 / 14

Java

1public static int removeDuplicates(int[] arr) {      // arr is sorted
2    if (arr.length == 0) return 0;
3    int write = 1;                                  // arr[0..write-1] is the unique prefix
4    for (int read = 1; read < arr.length; read++) {
5        if (arr[read] != arr[write - 1]) {
6            arr[write] = arr[read];
7            write++;
8        }
9    }
10    return write;
11}

Live state

0 comparisons0 writes

write

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	write=1	arr[0] is always kept. write marks the end of the unique prefix; read scans ahead.
2	L5	read=1 write=1 arr[read]=1 arr[write-1]=1	Same as the last kept value: skip it.
3	L5	read=2 write=1 arr[read]=2 arr[write-1]=1	A new value: append it to the unique prefix.
4	L6	read=2 write=2	arr[1] = 2; write = 2.
5	L5	read=3 write=2 arr[read]=3 arr[write-1]=2	A new value: append it to the unique prefix.
6	L6	read=3 write=3	arr[2] = 3; write = 3.
7	L5	read=4 write=3 arr[read]=3 arr[write-1]=3	Same as the last kept value: skip it.
8	L5	read=5 write=3 arr[read]=3 arr[write-1]=3	Same as the last kept value: skip it.
9	L5	read=6 write=3 arr[read]=4 arr[write-1]=3	A new value: append it to the unique prefix.
10	L6	read=6 write=4	arr[3] = 4; write = 4.
11	L5	read=7 write=4 arr[read]=5 arr[write-1]=4	A new value: append it to the unique prefix.
12	L6	read=7 write=5	arr[4] = 5; write = 5.
13	L5	read=8 write=5 arr[read]=5 arr[write-1]=5	Same as the last kept value: skip it.
14	L10	return=5	return 5: the first 5 slots hold the unique values. One pass, O(1) extra space. Slots after that are leftovers.

8.04.6

Reverse in-place

Reverse with two pointers that swap and move inward: floor(n / 2) swaps, O(1) extra space. Doing it in place matters when the array is large or memory is tight; Collections.reverse does the same for a List.

Reversal is the building block of rotation.

Java

1static void reverseRange(int[] a, int lo, int hi) {
2    while (lo < hi) { int t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; }
3}

Reverse an array in place (two pointers)

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedJust swappedIn final place

Setup

One pointer at each end. Swap the pair, then move both inward until they meet.

Step 1 / 8

Java

1static void reverse(int[] a) {
2    int lo = 0, hi = a.length - 1;
3    while (lo < hi) {
4        int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
5        lo++; hi--;
6    }
7}

Live state

0 swaps

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	lo=0 hi=6	One pointer at each end. Swap the pair, then move both inward until they meet.
2	L3	lo=0 hi=6	0 < 6: swap a[0] = 1 with a[6] = 7.
3	L4	lo=0 hi=6	Swapped. 1 swap so far.
4	L3	lo=1 hi=5	1 < 5: swap a[1] = 2 with a[5] = 6.
5	L4	lo=1 hi=5	Swapped. 2 swaps so far.
6	L3	lo=2 hi=4	2 < 4: swap a[2] = 3 with a[4] = 5.
7	L4	lo=2 hi=4	Swapped. 3 swaps so far.
8	L6	lo=3 hi=3	Pointers met (lo = 3, hi = 3). 3 swaps: floor(n / 2) swaps, O(n) time, O(1) space. An odd middle element stays put.

8.04.7

Rotate by k

A rotation by k can be done with a copy (O(n) space), cyclic replacement, or three reversals (O(1) space). Reduce k modulo n first, so k = 0 and k = n do nothing. Rotating left by k equals rotating right by n - k mod n.

Try the k-larger-than-n preset.

Method	Time	Extra space
Copy to a new array	O(n)	O(n)
Three reversals	O(n)	O(1)
Repeated shift by one	O(n·k)	O(1)

Rotate by k with three reversals

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedJust swappedOutside the current reversal

Setup

k = 3 reduces to 3 (rotating n times is the identity).

Step 1 / 11

Java

1static void rotateRight(int[] a, int k) {
2    int n = a.length; k %= n;
3    reverse(a, 0, n - 1);        // 1) whole array
4    reverse(a, 0, k - 1);        // 2) first k elements
5    reverse(a, k, n - 1);        // 3) the rest
6}
7static void reverse(int[] a, int lo, int hi) {
8    while (lo < hi) { swap(a, lo++, hi--); }
9}
10// rotate left by k == rotate right by n - k % n

Live state

0 swaps

k %= n

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2	n=7 k=3 k %= n=3	k = 3 reduces to 3 (rotating n times is the identity).
2	L3	lo=0 hi=6	Step 1: reverse positions 0 to 6.
3	L8	lo=0 hi=6	Swap positions 0 and 6.
4	L8	lo=1 hi=5	Swap positions 1 and 5.
5	L8	lo=2 hi=4	Swap positions 2 and 4.
6	L4	lo=0 hi=2	Step 2: reverse positions 0 to 2.
7	L8	lo=0 hi=2	Swap positions 0 and 2.
8	L5	lo=3 hi=6	Step 3: reverse positions 3 to 6.
9	L8	lo=3 hi=6	Swap positions 3 and 6.
10	L8	lo=4 hi=5	Swap positions 4 and 5.
11	L6	swaps=6	Rotated with 6 swaps: O(n) time and O(1) extra space, with no temporary array.

8.04.8

Rearrangement

Rearranging means placing elements in a required pattern. A classic: given an equal number of positive and negative values, put positives at even indexes and negatives at odd ones, keeping the order inside each group. Two write pointers (one for even slots, one for odd) fill an output array in one pass.

The in-place version is far harder because of the order requirement; the extra array keeps it simple.

Java

1static int[] rearrange(int[] a) {               // equal counts of positives and negatives
2    int[] out = new int[a.length];
3    int pos = 0, neg = 1;
4    for (int x : a) {
5        if (x > 0) { out[pos] = x; pos += 2; }
6        else       { out[neg] = x; neg += 2; }
7    }
8    return out;
9}

Rearrange to alternate positive and negative

Interactive · edit the input

int[] arr · length 6

-2

-5

-4

012345

Value being placedPlaced

out[]

·0

·1

·2

·3

·4

·5

Setup

Positives fill the even indexes 0, 2, 4 ... and negatives the odd indexes 1, 3, 5 ... Each group keeps its original order.

Step 1 / 8

Java

1static int[] rearrange(int[] a) {          // equal numbers of positives and negatives
2    int[] out = new int[a.length];
3    int pos = 0, neg = 1;                  // positives take even slots, negatives odd slots
4    for (int x : a) {
5        if (x > 0) { out[pos] = x; pos += 2; }
6        else       { out[neg] = x; neg += 2; }
7    }
8    return out;
9}

Live state

pos

neg

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L3	pos=0 neg=1	Positives fill the even indexes 0, 2, 4 ... and negatives the odd indexes 1, 3, 5 ... Each group keeps its original order.
2	L5	i=0 x=3 pos=2 neg=1	3 is positive: out[0] = 3, next positive slot 2.
3	L5	i=1 x=1 pos=4 neg=1	1 is positive: out[2] = 1, next positive slot 4.
4	L6	i=2 x=-2 pos=4 neg=3	-2 is negative: out[1] = -2, next negative slot 3.
5	L6	i=3 x=-5 pos=4 neg=5	-5 is negative: out[3] = -5, next negative slot 5.
6	L5	i=4 x=2 pos=6 neg=5	2 is positive: out[4] = 2, next positive slot 6.
7	L6	i=5 x=-4 pos=6 neg=7	-4 is negative: out[5] = -4, next negative slot 7.
8	L8	return=[3, -2, 1, -5, 2, -4]	Result [3, -2, 1, -5, 2, -4]: one pass, O(n) time and O(n) extra space. The in-place version is much harder because order within each sign is lost or costs shifts.

Practice ladder

Now try it yourself

Easy

Find the minimum and maximum in one pass
Move zeroes to the end of {0, 1, 0, 3, 12}

Medium

Find the second largest distinct value in {5, 5, 4}
Remove duplicates from a sorted array and return the new length

Advanced

Rotate an array by k in O(1) space, then explain why three reversals work

Key takeaways

One pass with a few variables solves min, max and second largest.
Read and write pointers rewrite an array in place in O(n).
Reduce k modulo n, and prefer reversals for in-place rotation.