ASkills Playground
DATA STRUCTURES / 02
LIVE DEMONSTRATION

How it works, from first principles

Implementing a
Dynamic Array

Dynamic array implementation

Timed TypeScript practice

Dynamic array implementation

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

Dynamic array implementation

append when space remains

O(1)

The decision is one count-versus-capacity comparison, followed by one direct write and one count increment.

append when the buffer is full

O(n)

Doubling capacity allocates a new buffer and copies every existing value. The new value is still only one final write.

the doubling decision

Amortized O(1)

A resize is expensive, but it creates many free slots. Across many appends, the total copied values grow linearly, so the average append cost stays constant.

get(index) and set(index, value)

O(1)

After one bounds check against count, the array can jump directly to the requested index.

size()

O(1)

The array maintains count as it changes, so size returns a stored number instead of scanning elements.

popBack and occasional shrinking

O(1), amortized

Removing the logical last value only decrements count. A rare shrink copies values into a smaller buffer, but the 25-percent threshold prevents resize thrashing.

space usage

O(n)

The backing buffer may reserve unused slots, but doubling on growth and halving below 25 percent keep that extra space within a constant factor of stored values.

Purpose: understand how an array can preserve fast indexed access while growing beyond its original fixed capacity.

LESSON02Resizable storage

CONTROL CONSOLE

COUNT3CAPACITY4

Keep appending. Watch what changes only when the buffer is full.

MEMORY BUFFER3 used · 1 free
08data
113data
221data
3free
DEMONSTRATOR SAYSOne slot is free. An append takes one direct write.

The algorithm’s little promise

Fast most of the time.
Prepared for the rare expensive moment.

A dynamic array holds two facts: count is how many values are actually stored, and capacity is how many drawers have been reserved. Appending normally writes once at dynamic[count].

When count === capacity, the current buffer cannot stretch. We reserve a new one with double the capacity, copy every existing value in order, then switch the reference to that new buffer.

APPEND PROCEDUREO(1) AMORTIZED
01append(value) {02  if (count === capacity) {03    resize();04  }05  dynamic[count] = value;06  count++;07}
01
CheckIs count equal to capacity?
02
Grow if neededAllocate double the space.
03
CopyMove the old values once.
04
WritePlace the new value at count.
WHY DOUBLE?

Doubling makes resize events increasingly rare. The total work spread across many appends stays constant on average: amortized O(1).

THE TRADE-OFF

Some reserved drawers stay empty. That small memory cushion buys quick appends without allocating storage every time.

KEY INVARIANT

Only indexes 0 through count − 1 contain valid elements. Capacity is the physical room, not the logical size.

Dynamic arrays / quick reference

What the reference pages explain

The basic structure

A dynamic array uses a fixed-size backing array, plus size for stored values and capacity for total slots. Only indexes from 0 through size − 1 are valid.

Appending and growing

Append directly while space remains. When full, create a backing array with double the capacity, copy the existing values, and add the new value.

Removing and shrinking

pop_back() reduces the size. If the array becomes about 25% full, halve its capacity to reclaim space without constantly switching between growing and shrinking.

Performance

get, set, and size are O(1). A resize is O(n), but appends and end removals are amortized O(1) across many operations.

Extra operations

pop(i), insert(i, x), and remove(x) shift items, so they take O(n). contains(x) searches through the values.

Based on the images in the reference folder.

Solution files
solution.ts
1export default class DynamicArray {
2    dynamic: number[];
3    capacity: number;
4    count: number;
5
6    constructor() {
7        this.capacity = 10;
8        this.count = 0;
9
10        this.dynamic =  new Array<number>(this.capacity);
11    }
12
13    append(value: number): void {
14        if(this.count === this.capacity) {
15            this.resize();
16        }
17
18        this.dynamic[this.count] = value;
19        this.count++;
20    }
21
22    get(index: number): number {
23        this.validateIndex(index);
24
25        return this.dynamic[index];
26    }
27
28    set(index: number, value: number): void {
29        this.validateIndex(index);
30        this.dynamic[index] = value;
31    }
32
33    size(): number {
34        return this.count;
35    }
36
37    popBack(): void {
38        if(this.count === 0) {
39            throw new RangeError("Cannot pop from an empty array");
40        }
41
42        this.count--;
43    }
44
45    private resize(): void {
46        this.capacity *= 2;
47
48        const newDynamic = new Array<number>(this.capacity);
49
50        for (let i = 0; i < this.count; i++) {
51            newDynamic[i] = this.dynamic[i];
52        }
53
54        this.dynamic = newDynamic;
55    }
56
57    private validateIndex(index: number): void {
58        if (index < 0 || index >= this.count) {
59            throw new RangeError("Index is out of bounds");
60        }
61    }
62}
63
64
65
66
solution2.ts
1// Practice sample 2: a clear helper-based implementation.
2export default class DynamicArrayWithHelpers {
3  dynamic: number[];
4  capacity = 10;
5  count = 0;
6
7  constructor() {
8    this.dynamic = new Array<number>(this.capacity);
9  }
10
11  append(value: number): void {
12    if (this.count === this.capacity) this.grow();
13    this.dynamic[this.count++] = value;
14  }
15
16  get(index: number): number {
17    this.assertValidIndex(index);
18    return this.dynamic[index];
19  }
20
21  set(index: number, value: number): void {
22    this.assertValidIndex(index);
23    this.dynamic[index] = value;
24  }
25
26  size(): number { return this.count; }
27
28  popBack(): number {
29    if (this.count === 0) throw new RangeError("Cannot pop from an empty array");
30    return this.dynamic[--this.count];
31  }
32
33  private grow(): void {
34    const next = new Array<number>(this.capacity * 2);
35    for (let index = 0; index < this.count; index++) next[index] = this.dynamic[index];
36    this.dynamic = next;
37    this.capacity *= 2;
38  }
39
40  private assertValidIndex(index: number): void {
41    if (index < 0 || index >= this.count) throw new RangeError("Index is out of bounds");
42  }
43}
44
solution3.ts
1// Practice sample 3: a compact interview-style implementation.
2export default class DynamicArrayInterviewStyle {
3  private data: number[] = new Array(4);
4  private length = 0;
5
6  append(value: number): void {
7    if (this.length === this.data.length) {
8      const grown = new Array<number>(this.data.length * 2);
9      for (let index = 0; index < this.length; index++) grown[index] = this.data[index];
10      this.data = grown;
11    }
12    this.data[this.length++] = value;
13  }
14
15  get(index: number): number {
16    if (index < 0 || index >= this.length) throw new RangeError("Index is out of bounds");
17    return this.data[index];
18  }
19
20  set(index: number, value: number): void {
21    if (index < 0 || index >= this.length) throw new RangeError("Index is out of bounds");
22    this.data[index] = value;
23  }
24
25  size(): number { return this.length; }
26
27  popBack(): number {
28    if (this.length === 0) throw new RangeError("Cannot pop from an empty array");
29    return this.data[--this.length];
30  }
31}
32