SSKILLSPLAYGROUNDDATA STRUCTURES / 03
INTERACTIVE LESSON

Take the next step

Extra Dynamic Array
Operations.

Adding and removing from the middle has a cost: values must move to keep the buffer compact.

Extra dynamic array operations

Timed TypeScript practice

Extra dynamic array operations

Write your solution, use the timer, then validate TypeScript types and syntax. Your code is never executed.

30:00
Strict TypeScript validation · no execution

Performance, step by step

Extra dynamic array operations

pop from the final index

O(1)

This is the same as popBack: reduce count and return the final logical value. No other values need to move.

pop(index) in the middle or front

O(n)

Every value after the removed index shifts left to keep the valid values contiguous. A front removal can shift almost the entire array.

contains(value)

O(n)

An unordered array has no shortcut for membership. It compares one stored value at a time until it finds a match or reaches count.

insert(index, value)

O(n)

The algorithm shifts values right, working backward so it does not overwrite them. Inserting at the end is append and is amortized O(1).

remove(value)

O(n)

First it searches for the first matching value, then it shifts the values after that match left. Both steps are linear in the worst case.

bounds and capacity checks

O(1)

Comparing an index with count, or count with capacity, is constant time. These small decisions protect correctness before any movement begins.

space usage

O(n)

The same growth and shrink rules from a base dynamic array keep reserved storage proportional to the number of valid values.

Purpose: understand why searching, inserting, and removing in the middle of an array require extra work to keep values contiguous.

LESSON03Beyond append

TRY AN OPERATION

Both middle operations can require shifting several values. That is why they are O(n).

CONTIGUOUS MEMORY7 used · 3 free
03data
11data
24data
31data
45data
59data
62data
7free
8free
9free
ReadyChoose an operation to see how a dynamic array keeps its values contiguous.

The important distinction

Fast at the end.
Deliberate in the middle.

pop(i) removes by index and closes the gap by shifting later values left. insert(i, x) does the inverse: it shifts values right to make room.

contains(x) searches one value at a time. remove(x) finds the first match, then calls pop on its index.

OPERATION COSTS
pop(i), insert(i, x), remove(x)O(n)
contains(x)O(n)
append(x), get(i), set(i, x)O(1)*
* append is amortized O(1)
POP

Close the gap

Removing the final item is cheap. Removing elsewhere copies every later item left.

INSERT

Make room

Shift values right from the insertion point, then write the new value.

REMOVE

Find, then shift

Search for the first matching value, then remove it using its index.

Dynamic arrays / quick reference

Extra operations

Pop by index

pop(i) removes a value and shifts every later value left. It is O(n) in the worst case.

Contains

contains(x) scans the stored values until it finds a match, so an unordered array needs O(n) time.

Insert and remove

insert(i, x) shifts right to open a slot. remove(x) finds the first matching value, then removes it by index.

Key takeaway

Appending and end removal are amortized O(1). Operations that search or shift through the middle are O(n).

Solution files
solution.ts
1export default class ExtraDynamicArray {
2  dynamic: number[];
3  capacity: number;
4  count: number;
5
6  constructor() {
7    this.capacity = 10;
8    this.count = 0;
9    this.dynamic = new Array<number>(this.capacity);
10  }
11
12  append(value: number): void {
13    if (this.count === this.capacity) this.resize(this.capacity * 2);
14    this.dynamic[this.count++] = value;
15  }
16
17  get(index: number): number {
18    this.validateIndex(index);
19    return this.dynamic[index];
20  }
21
22  set(index: number, value: number): void {
23    this.validateIndex(index);
24    this.dynamic[index] = value;
25  }
26
27  size(): number { return this.count; }
28
29  popBack(): number {
30    if (this.count === 0) throw new RangeError("Cannot pop from an empty array");
31    const value = this.dynamic[--this.count];
32    this.shrinkIfNeeded();
33    return value;
34  }
35
36  pop(index: number): number {
37    this.validateIndex(index);
38    const value = this.dynamic[index];
39    for (let current = index; current < this.count - 1; current++) this.dynamic[current] = this.dynamic[current + 1];
40    this.count--;
41    this.shrinkIfNeeded();
42    return value;
43  }
44
45  contains(value: number): boolean {
46    for (let index = 0; index < this.count; index++) if (this.dynamic[index] === value) return true;
47    return false;
48  }
49
50  insert(index: number, value: number): void {
51    if (index < 0 || index > this.count) throw new RangeError("Index is out of bounds");
52    if (this.count === this.capacity) this.resize(this.capacity * 2);
53    for (let current = this.count; current > index; current--) this.dynamic[current] = this.dynamic[current - 1];
54    this.dynamic[index] = value;
55    this.count++;
56  }
57
58  remove(value: number): number {
59    for (let index = 0; index < this.count; index++) if (this.dynamic[index] === value) {
60      this.pop(index);
61      return index;
62    }
63    return -1;
64  }
65
66  private resize(capacity: number): void {
67    const next = new Array<number>(capacity);
68    for (let index = 0; index < this.count; index++) next[index] = this.dynamic[index];
69    this.dynamic = next;
70    this.capacity = capacity;
71  }
72
73  private shrinkIfNeeded(): void {
74    if (this.capacity > 10 && this.count / this.capacity < 0.25) this.resize(this.capacity / 2);
75  }
76
77  private validateIndex(index: number): void {
78    if (index < 0 || index >= this.count) throw new RangeError("Index is out of bounds");
79  }
80}
81
solution2.ts
1// Alternative solution: keep the movement of values in named helpers.
2// This makes the relationship between pop and insert easier to trace.
3export default class ExtraDynamicArrayAlternative {
4  dynamic: number[];
5  capacity: number;
6  count: number;
7
8  constructor() {
9    this.capacity = 10;
10    this.count = 0;
11    this.dynamic = new Array<number>(this.capacity);
12  }
13
14  append(value: number): void {
15    this.insert(this.count, value);
16  }
17
18  get(index: number): number {
19    this.assertElementIndex(index);
20    return this.dynamic[index];
21  }
22
23  size(): number {
24    return this.count;
25  }
26
27  contains(value: number): boolean {
28    return this.indexOf(value) !== -1;
29  }
30
31  insert(index: number, value: number): void {
32    this.assertInsertIndex(index);
33    this.ensureRoomForOneMore();
34    this.shiftRightFrom(index);
35    this.dynamic[index] = value;
36    this.count++;
37  }
38
39  pop(index: number): number {
40    this.assertElementIndex(index);
41    const removed = this.dynamic[index];
42    this.shiftLeftFrom(index);
43    this.count--;
44    this.shrinkWhenSparse();
45    return removed;
46  }
47
48  remove(value: number): number {
49    const index = this.indexOf(value);
50    if (index === -1) return -1;
51    this.pop(index);
52    return index;
53  }
54
55  private indexOf(value: number): number {
56    for (let index = 0; index < this.count; index++) if (this.dynamic[index] === value) return index;
57    return -1;
58  }
59
60  private shiftRightFrom(index: number): void {
61    for (let current = this.count; current > index; current--) this.dynamic[current] = this.dynamic[current - 1];
62  }
63
64  private shiftLeftFrom(index: number): void {
65    for (let current = index; current < this.count - 1; current++) this.dynamic[current] = this.dynamic[current + 1];
66  }
67
68  private ensureRoomForOneMore(): void {
69    if (this.count === this.capacity) this.resize(this.capacity * 2);
70  }
71
72  private shrinkWhenSparse(): void {
73    if (this.capacity > 10 && this.count / this.capacity < 0.25) this.resize(this.capacity / 2);
74  }
75
76  private resize(nextCapacity: number): void {
77    const next = new Array<number>(nextCapacity);
78    for (let index = 0; index < this.count; index++) next[index] = this.dynamic[index];
79    this.dynamic = next;
80    this.capacity = nextCapacity;
81  }
82
83  private assertElementIndex(index: number): void {
84    if (index < 0 || index >= this.count) throw new RangeError("Index is out of bounds");
85  }
86
87  private assertInsertIndex(index: number): void {
88    if (index < 0 || index > this.count) throw new RangeError("Index is out of bounds");
89  }
90}
91
solution3.ts
1// Practice sample 3: a compact interview-style version of the extra operations.
2export default class ExtraDynamicArrayInterviewStyle {
3  private data: number[] = new Array(4);
4  private length = 0;
5
6  append(value: number): void { this.insert(this.length, value); }
7  size(): number { return this.length; }
8
9  get(index: number): number {
10    this.assertElement(index);
11    return this.data[index];
12  }
13
14  contains(value: number): boolean {
15    for (let index = 0; index < this.length; index++) if (this.data[index] === value) return true;
16    return false;
17  }
18
19  insert(index: number, value: number): void {
20    if (index < 0 || index > this.length) throw new RangeError("Index is out of bounds");
21    if (this.length === this.data.length) this.grow();
22    for (let current = this.length; current > index; current--) this.data[current] = this.data[current - 1];
23    this.data[index] = value;
24    this.length++;
25  }
26
27  pop(index: number): number {
28    this.assertElement(index);
29    const removed = this.data[index];
30    for (let current = index; current < this.length - 1; current++) this.data[current] = this.data[current + 1];
31    this.length--;
32    return removed;
33  }
34
35  remove(value: number): number {
36    for (let index = 0; index < this.length; index++) if (this.data[index] === value) {
37      this.pop(index);
38      return index;
39    }
40    return -1;
41  }
42
43  private grow(): void {
44    const next = new Array<number>(this.data.length * 2);
45    for (let index = 0; index < this.length; index++) next[index] = this.data[index];
46    this.data = next;
47  }
48
49  private assertElement(index: number): void {
50    if (index < 0 || index >= this.length) throw new RangeError("Index is out of bounds");
51  }
52}
53