8.02Beginner / Intermediate11 topics20 min9 interactive animations

Core operations

The eleven core operations on an array: access, update, insert, delete, search, append, shifting, rotating, reversing, resizing and copying. Each has a precise cost, and most of the cost comes from moving elements.

Learning goals

State the cost of each core operation
Insert and delete by shifting elements correctly
Rotate and reverse in place
Resize and copy without aliasing bugs

Prerequisites

Array fundamentals

8.02.1

Access

Access reads the element at an index: a[i] in O(1). Always validate the index when it comes from outside the method, because Java throws on out-of-range reads rather than returning garbage.

A defensive wrapper makes the contract explicit.

Java

1static int get(int[] a, int i) {
2    if (i < 0 || i >= a.length) throw new IndexOutOfBoundsException("index " + i + ", length " + a.length);
3    return a[i];
4}

8.02.2

Update

Update overwrites one slot: a[i] = x, O(1). Updating never moves other elements. For a batch of updates over a range, prefer one loop or Arrays.fill, and use a difference array when there are many range updates and few reads.

Remember that updating an object array replaces the reference only.

Java

1int[] a = {1, 2, 3, 4};
2a[2] = 30;                      // {1, 2, 30, 4}
3Arrays.fill(a, 1, 3, 0);        // range update: {1, 0, 0, 4}

8.02.3

Insert

Inserting into the middle of an array means opening a gap: every element from the insertion index to the end moves one slot to the right, starting from the back so nothing is overwritten. That costs n - index moves, so O(n) in the worst case (inserting at the front).

Choose Insert and a different index in the animation and compare the shift counts.

Java

1static void insert(int[] a, int size, int index, int x) {   // requires a.length > size
2    for (int j = size; j > index; j--) a[j] = a[j - 1];     // shift right, from the back
3    a[index] = x;
4}

Insert, delete and append in an array

Interactive · edit the input

int[] arr · length 6

012345

Being movedJust writtenSpare / freed slot

Setup

Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.

Step 1 / 6

Java

1static void insert(int[] arr, int size, int index, int x) {   // arr.length > size
2    for (int j = size; j > index; j--) {
3        arr[j] = arr[j - 1];                // shift right, from the back
4    }
5    arr[index] = x;
6}
7static void delete(int[] arr, int size, int index) {
8    for (int j = index; j < size - 1; j++) {
9        arr[j] = arr[j + 1];                // shift left, from the front
10    }
11    arr[size - 1] = 0;                      // clear the freed slot
12}
13static void append(int[] arr, int size, int x) { arr[size] = x; }

Live state

0 shifts

size

index

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L1	size=5 index=1 x=99	Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.
2	L3	j=5 shifts=1	arr[5] = arr[4] (50). 1 element shifted so far.
3	L3	j=4 shifts=2	arr[4] = arr[3] (40). 2 elements shifted so far.
4	L3	j=3 shifts=3	arr[3] = arr[2] (30). 3 elements shifted so far.
5	L3	j=2 shifts=4	arr[2] = arr[1] (20). 4 elements shifted so far.
6	L5	size=6 shifts=4	Write 99 into the gap at index 1. Inserting at index 1 shifted 4 elements: n - index, so O(n) in the worst case (index 0).

8.02.4

Delete

Deleting closes the gap: elements after the index move one slot left, starting from the front, and the freed last slot is cleared. The cost is size - index - 1 moves: O(n) worst case, O(1) when deleting the last element.

Switch the operation to Delete in the animation.

Java

1static void delete(int[] a, int size, int index) {
2    for (int j = index; j < size - 1; j++) a[j] = a[j + 1];  // shift left, from the front
3    a[size - 1] = 0;
4}

Insert, delete and append in an array

Interactive · edit the input

int[] arr · length 6

012345

Being movedJust writtenSpare / freed slot

Setup

Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.

Step 1 / 6

Java

1static void insert(int[] arr, int size, int index, int x) {   // arr.length > size
2    for (int j = size; j > index; j--) {
3        arr[j] = arr[j - 1];                // shift right, from the back
4    }
5    arr[index] = x;
6}
7static void delete(int[] arr, int size, int index) {
8    for (int j = index; j < size - 1; j++) {
9        arr[j] = arr[j + 1];                // shift left, from the front
10    }
11    arr[size - 1] = 0;                      // clear the freed slot
12}
13static void append(int[] arr, int size, int x) { arr[size] = x; }

Live state

0 shifts

size

index

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L1	size=5 index=1 x=99	Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.
2	L3	j=5 shifts=1	arr[5] = arr[4] (50). 1 element shifted so far.
3	L3	j=4 shifts=2	arr[4] = arr[3] (40). 2 elements shifted so far.
4	L3	j=3 shifts=3	arr[3] = arr[2] (30). 3 elements shifted so far.
5	L3	j=2 shifts=4	arr[2] = arr[1] (20). 4 elements shifted so far.
6	L5	size=6 shifts=4	Write 99 into the gap at index 1. Inserting at index 1 shifted 4 elements: n - index, so O(n) in the worst case (index 0).

8.02.5

Search

Searching an unsorted array means checking elements one by one: O(n) in the worst case, with early exit when found. On a sorted array binary search brings it down to O(log n).

Run the linear search on your own array and target, then compare with binary search on sorted input.

Java

1static int indexOf(int[] a, int target) {
2    for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
3    return -1;
4}

Linear search

Interactive · edit the input

int[] arr · length 7

0123456

Being comparedNot a matchAlready checkedMatch / answer

Setup

Call linearSearch(arr, 5). Nothing has been checked yet, so start at index 0.

Step 1 / 12

Java

1public static int linearSearch(int[] arr, int target) {
2    for (int i = 0; i < arr.length; i++) {
3        if (arr[i] == target) {
4            return i;
5        }
6    }
7    return -1;
8}

Live state

0 comparisons

target

arr.length

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1	target=5 arr.length=7	Call linearSearch(arr, 5). Nothing has been checked yet, so start at index 0.
2	L2	target=5 i=0	0 < 7, so the loop body runs for index 0.
3	L3	target=5 i=0 arr[i]=7	7 != 5. Not a match, move on.
4	L2	target=5 i=1	1 < 7, so the loop body runs for index 1.
5	L3	target=5 i=1 arr[i]=3	3 != 5. Not a match, move on.
6	L2	target=5 i=2	2 < 7, so the loop body runs for index 2.
7	L3	target=5 i=2 arr[i]=9	9 != 5. Not a match, move on.
8	L2	target=5 i=3	3 < 7, so the loop body runs for index 3.
9	L3	target=5 i=3 arr[i]=14	14 != 5. Not a match, move on.
10	L2	target=5 i=4	4 < 7, so the loop body runs for index 4.
11	L3	target=5 i=4 arr[i]=5	5 == 5. This is the element we are looking for.
12	L4	target=5 i=4 return=4	return 4. Found after 5 comparisons.

8.02.6

Append

Appending writes to the first unused slot: a[size++] = x, O(1) as long as capacity remains, with nothing to shift. When the array is full a dynamic array allocates a larger one first.

Choose Append in the animation: one write, no shifts.

Java

1static boolean append(int[] a, int size, int x) {
2    if (size == a.length) return false;     // full: caller must grow the array
3    a[size] = x;
4    return true;
5}

Insert, delete and append in an array

Interactive · edit the input

int[] arr · length 6

012345

Being movedJust writtenSpare / freed slot

Setup

Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.

Step 1 / 6

Java

1static void insert(int[] arr, int size, int index, int x) {   // arr.length > size
2    for (int j = size; j > index; j--) {
3        arr[j] = arr[j - 1];                // shift right, from the back
4    }
5    arr[index] = x;
6}
7static void delete(int[] arr, int size, int index) {
8    for (int j = index; j < size - 1; j++) {
9        arr[j] = arr[j + 1];                // shift left, from the front
10    }
11    arr[size - 1] = 0;                      // clear the freed slot
12}
13static void append(int[] arr, int size, int x) { arr[size] = x; }

Live state

0 shifts

size

index

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L1	size=5 index=1 x=99	Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.
2	L3	j=5 shifts=1	arr[5] = arr[4] (50). 1 element shifted so far.
3	L3	j=4 shifts=2	arr[4] = arr[3] (40). 2 elements shifted so far.
4	L3	j=3 shifts=3	arr[3] = arr[2] (30). 3 elements shifted so far.
5	L3	j=2 shifts=4	arr[2] = arr[1] (20). 4 elements shifted so far.
6	L5	size=6 shifts=4	Write 99 into the gap at index 1. Inserting at index 1 shifted 4 elements: n - index, so O(n) in the worst case (index 0).

8.02.7

Shift elements

Shifting is the engine behind insert and delete. System.arraycopy shifts a block with one native, overlap-safe call that is usually faster than a Java loop. Shift right by one to open a gap, left by one to close it.

The cost is the number of elements moved, which is why front insertions into big arrays are slow.

Java

1int[] a = {1, 2, 3, 4, 5, 0};            // size 5, spare slot at the end
2System.arraycopy(a, 1, a, 2, 4);          // shift a[1..4] right by one: {1, 2, 2, 3, 4, 5}
3a[1] = 99;                                // {1, 99, 2, 3, 4, 5}

Insert, delete and append in an array

Interactive · edit the input

int[] arr · length 6

012345

Being movedJust writtenSpare / freed slot

Setup

Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.

Step 1 / 6

Java

1static void insert(int[] arr, int size, int index, int x) {   // arr.length > size
2    for (int j = size; j > index; j--) {
3        arr[j] = arr[j - 1];                // shift right, from the back
4    }
5    arr[index] = x;
6}
7static void delete(int[] arr, int size, int index) {
8    for (int j = index; j < size - 1; j++) {
9        arr[j] = arr[j + 1];                // shift left, from the front
10    }
11    arr[size - 1] = 0;                      // clear the freed slot
12}
13static void append(int[] arr, int size, int x) { arr[size] = x; }

Live state

0 shifts

size

index

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L1	size=5 index=1 x=99	Insert 99 at index 1. Everything from index 1 onward must move one slot right, starting from the last element, or it would be overwritten.
2	L3	j=5 shifts=1	arr[5] = arr[4] (50). 1 element shifted so far.
3	L3	j=4 shifts=2	arr[4] = arr[3] (40). 2 elements shifted so far.
4	L3	j=3 shifts=3	arr[3] = arr[2] (30). 3 elements shifted so far.
5	L3	j=2 shifts=4	arr[2] = arr[1] (20). 4 elements shifted so far.
6	L5	size=6 shifts=4	Write 99 into the gap at index 1. Inserting at index 1 shifted 4 elements: n - index, so O(n) in the worst case (index 0).

8.02.8

Rotate

Rotating right by k moves every element k positions to the right, wrapping around. The in-place trick uses three reversals: reverse the whole array, then the first k elements, then the rest. It takes O(n) time and O(1) extra space, with no temporary array. Always reduce k modulo n first.

Step through it and watch the three reversals; rotate left by k is rotate right by n - k.

Java

1static void rotateRight(int[] a, int k) {
2    int n = a.length; k %= n;
3    reverse(a, 0, n - 1);
4    reverse(a, 0, k - 1);
5    reverse(a, k, n - 1);
6}
7static void reverse(int[] a, int lo, int hi) {
8    while (lo < hi) { int t = a[lo]; a[lo++] = a[hi]; a[hi--] = t; }
9}

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.02.9

Reverse

Reversing swaps the first and last elements, then the second and second-to-last, and so on, moving two pointers toward each other. It performs floor(n / 2) swaps in O(n) time and O(1) space.

Reversal is a building block for rotation, next permutation and many string problems.

Java

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

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.02.10

Resize

An array cannot change length. To resize, allocate a new array and copy the old elements across: O(n). Arrays.copyOf(a, newLength) does both and pads with zeros when growing or cuts when shrinking. Growing by a constant factor keeps appends amortised O(1).

Watch the capacity change as the buffer fills in the animation.

Java

1int[] a = {1, 2, 3};
2int[] bigger = Arrays.copyOf(a, 6);     // {1, 2, 3, 0, 0, 0}
3int[] smaller = Arrays.copyOf(a, 2);   // {1, 2}
4// a itself is unchanged and still has length 3

Dynamic array: capacity, growth and shrinking

Interactive · edit the input

size elements in the buffer · length 0

Used slot (size)Spare capacity

data[] · capacity 1

Setup

A new dynamic array starts with capacity 1 and no elements.

Step 1 / 21

Java

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

Live state

0 copies0 resizes

size

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	size=0 capacity=1	A new dynamic array starts with capacity 1 and no elements.
2	L2	size=0 capacity=1 x=4	size 0 < capacity 1: there is a spare slot, so adding is O(1).
3	L5	size=1 capacity=1 x=4	Write 4 into data[0] and increase size to 1.
4	L2	size=1 capacity=1 x=8	size 1 equals capacity 1: no room for 8, so the buffer must grow.
5	L3	size=1 capacity=2	Allocate capacity 2 and copy the 1 element (1 copy so far).
6	L5	size=2 capacity=2 x=8	Write 8 into data[1] and increase size to 2.
7	L2	size=2 capacity=2 x=15	size 2 equals capacity 2: no room for 15, so the buffer must grow.
8	L3	size=2 capacity=4	Allocate capacity 4 and copy the 2 elements (3 copys so far).
9	L5	size=3 capacity=4 x=15	Write 15 into data[2] and increase size to 3.
10	L2	size=3 capacity=4 x=16	size 3 < capacity 4: there is a spare slot, so adding is O(1).
11	L5	size=4 capacity=4 x=16	Write 16 into data[3] and increase size to 4.
12	L2	size=4 capacity=4 x=23	size 4 equals capacity 4: no room for 23, so the buffer must grow.
13	L3	size=4 capacity=8	Allocate capacity 8 and copy the 4 elements (7 copys so far).
14	L5	size=5 capacity=8 x=23	Write 23 into data[4] and increase size to 5.
15	L2	size=5 capacity=8 x=42	size 5 < capacity 8: there is a spare slot, so adding is O(1).
16	L5	size=6 capacity=8 x=42	Write 42 into data[5] and increase size to 6.
17	L2	size=6 capacity=8 x=7	size 6 < capacity 8: there is a spare slot, so adding is O(1).
18	L5	size=7 capacity=8 x=7	Write 7 into data[6] and increase size to 7.
19	L2	size=7 capacity=8 x=9	size 7 < capacity 8: there is a spare slot, so adding is O(1).
20	L5	size=8 capacity=8 x=9	Write 9 into data[7] and increase size to 8.
21	L11	size=8 capacity=8 copies=7	Final: size 8, capacity 8 (0 spare slots), 3 resizes that copied 7 elements in total. Doubling keeps total copies below 2n.

8.02.11

Copy

Assigning an array variable copies the reference, not the data. To copy the elements use clone(), Arrays.copyOf or System.arraycopy; for arrays of arrays you must copy every row yourself, or you get a shallow copy that still shares the rows.

Step through the alias, clone and deep-copy cases to see which cells are shared.

Java

1int[] a = {1, 2, 3};
2int[] alias = a;             // same array
3int[] copy = a.clone();      // independent: O(n)
4copy[0] = 99;                // a[0] is still 1

Aliasing and copying arrays

Interactive · edit the input

variables

a → @1

@1 int[]

100

201

302

403

Setup

new int[] creates one object on the heap; the variable a holds only a reference to it.

Step 1 / 4

Java

1int[] a = { 10, 20, 30, 40 };               // options 0 and 1 use this 1D array
2int[] b = a;                                // option 0: copies the reference only
3int[] b = a.clone();                        // option 1: copies the elements
4int[][] a2 = { { 10, 20 }, { 30, 40 } };    // options 2 and 3 use this 2D array
5int[][] b2 = a2.clone();                    // option 2: new outer array, SAME row objects
6int[][] b2 = Arrays.stream(a2).map(int[]::clone).toArray(int[][]::new);   // option 3: rows copied too
7b[idx] = v;                                 // (b2[0][idx] = v for options 2 and 3)
8System.out.println(Arrays.toString(a));     // does a see the change?

Live state

0 writes

a.length

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L1	a.length=4	new int[] creates one object on the heap; the variable a holds only a reference to it.
2	L2	same=true	b = a copies the reference, not the array. Both variables now point at the same object (@1).
3	L7	idx=1 v=99	b[1] = 99 writes into the object b points at.
4	L8	a=[10, 99, 30, 40] b=[10, 99, 30, 40]	a shows the change too ([10, 99, 30, 40]), because a and b are two names for one object.

Practice ladder

Now try it yourself

Easy

How many elements move when inserting at index 2 in an array of size 10?
Reverse {1, 2, 3, 4} by hand with two pointers

Medium

Rotate {1, 2, 3, 4, 5, 6, 7} right by 3 using three reversals and list each step
Implement delete that keeps the order and one that does not (swap with the last element)

Advanced

Prove that the three-reversal rotation is correct for any k

Key takeaways

Access and update are O(1); insert and delete are O(n) because of shifting.
Rotation and reversal run in place in O(n) with two pointers.
Resizing and copying always allocate a new array; clone is shallow for nested arrays.