Data Structures & Algorithms · Module 01 of 10

Arrays

The foundation. Contiguous memory, O(1) indexing, and the slice machinery Go builds on top of it.

Build: Dynamic array with doubling
Solve: Rotation, Kadane, prefix sums, two pointers

The finish line — what go test shows once every exercise in this module passes

$ go test -v ./01-arrays/ | grep '^--- ' --- PASS: TestDynamicArrayPushGet (0.00s) --- PASS: TestDynamicArrayInsertRemove (0.00s) --- PASS: TestReverse (0.00s) --- PASS: TestRotateRight (0.00s) --- PASS: TestMoveZeroes (0.00s) --- PASS: TestMaxSubarraySum (0.00s) --- PASS: TestPrefixAndRangeSum (0.00s) --- PASS: TestTwoSumSorted (0.00s)

Module 1 · tests 8

WHY

Why it matters.

An array is a block of same-sized slots laid out back to back in memory. Because every slot is the same size, the address of element i is just base + i × size, which is why indexing is O(1) no matter how big the array is. That layout is also cache-friendly: walking an array touches memory in order, and modern CPUs reward that heavily.

Almost everything later in this course sits on arrays. Strings are byte arrays. Hash tables are arrays of buckets. Heaps are trees packed into an array. DP tables are 2-D arrays. Get comfortable here and the rest gets easier.

IDEAS

The core ideas.

Fixed vs. dynamic. A raw array has a fixed size. A dynamic array hides that by keeping a backing array with spare capacity; when it fills up, it allocates a bigger one (typically double) and copies everything over.

Amortized O(1) append. Copying on growth sounds expensive, but with doubling the copies form a series 1 + 2 + 4 + … + n < 2n. Spread across n appends, that's a constant amount of work each. Any single append can be O(n); the average is O(1).

Shifting is the real cost. Inserting or deleting in the middle means sliding every later element over by one slot. That's O(n), and it's the main reason other structures exist.

COST

Cost of operations.

Operation	Cost	Why
Read/write `a[i]`	O(1)	Address arithmetic
Append at end	O(1) amortized	Occasional O(n) copy on growth
Insert/delete at front or middle	O(n)	Everything after it shifts
Search unsorted	O(n)	Must look at each element
Search sorted	O(log n)	Binary search

IN GO

Go specifics.

Go has both, and the difference matters:

Arrays ([5]int) are values. The length is part of the type, and assigning or passing one copies every element. You'll rarely use them directly, except as map keys or fixed buffers.
Slices ([]int) are a three-word header — pointer, length, capacity — that views a backing array. Passing a slice copies the header, not the data.
append grows the backing array when len == cap. For small slices it roughly doubles; for large ones the growth factor tapers toward 1.25×.
Slicing shares memory. b := a[2:5] doesn't copy; writes through b show up in a. Use slices.Clone when you need independence, or a full slice expression a[2:5:5] to cap b so a later append can't scribble on a.

EXAMPLE

Worked example: the aliasing trap.

a := make([]int, 3, 4) // len 3, cap 4 — one spare slot
b := append(a, 99)     // fits in cap: writes a's backing array[3]
c := append(a, 42)     // also fits: overwrites the same slot!
fmt.Println(b[3], c[3]) // 42 42

Both b and c share a's backing array, so the second append clobbered the first. When a function appends to a slice it didn't create, either clone it first or return the result and let the caller own it.

PATTERNS

Patterns to recognize.

Two pointers from both ends — reversing, pair sums in sorted data, palindromes.
Read/write pointers — compacting in place (remove duplicates, move zeros) with O(1) extra space.
Prefix sums — precompute running totals once, answer any range-sum query in O(1).
Kadane's algorithm — best contiguous subarray in one pass: at each element, either extend the current run or start fresh.

EXERCISES

Your exercises.

Open exercises.go. Part A has you build DynamicArray without append, so the growth and shifting are yours to write. Part B is seven classic slice problems.

go test ./01-arrays/                          # all tests in the module
go test -run TestRotateRight -v ./01-arrays/  # one test, verbose

Suggested order: Get → Push → InsertAt → RemoveAt, then Reverse (you'll reuse it in RotateRight), MoveZeroes, PrefixSums/RangeSum, TwoSumSorted, and MaxSubarraySum last.

The files for this module

Everything below is also in the course download, in 01-arrays/. Work in exercises.go; the tests decide when you’re done.

▶ types.go the structs and helpers you’re given · 35 lines›

// Package arrays is Module 1: arrays and slices.
//
// Work in exercises.go. Run `go test ./01-arrays/` to check your work, or
// `go test -tags solutions ./01-arrays/` to run the tests against the
// reference solutions in solution.go.
package arrays

// DynamicArray is a growable array of ints built on a fixed-size backing
// store — the same idea Go's append uses under the hood.
//
// Rules for the exercises: len(data) is the capacity, size is how many slots
// are in use. Don't call append() inside your methods; the point is to do the
// growing and shifting yourself.
type DynamicArray struct {
	data []int // backing store; len(data) == capacity
	size int   // number of elements in use
}

// NewDynamicArray returns an empty array with capacity 2.
func NewDynamicArray() *DynamicArray {
	return &DynamicArray{data: make([]int, 2)}
}

// Len returns the number of elements stored.
func (a *DynamicArray) Len() int { return a.size }

// Cap returns the current capacity of the backing store.
func (a *DynamicArray) Cap() int { return len(a.data) }

// Values returns a copy of the elements in use.
func (a *DynamicArray) Values() []int {
	out := make([]int, a.size)
	copy(out, a.data[:a.size])
	return out
}

exercises.go — your work: every function is a stub marked TODO88 lines

//go:build !solutions

package arrays

// ============================================================
// Part A — build a dynamic array (see types.go for the struct)
// ============================================================

// Get returns the element at index i, or (0, false) if i is out of range.
// Target: O(1).
func (a *DynamicArray) Get(i int) (int, bool) {
	// TODO
	return 0, false
}

// Push appends v. When the backing store is full, allocate one twice as
// large and copy the elements over. Target: amortized O(1).
func (a *DynamicArray) Push(v int) {
	// TODO
}

// InsertAt inserts v at index i (0 <= i <= Len()), shifting later elements
// one slot to the right. Returns false if i is out of range. Target: O(n).
func (a *DynamicArray) InsertAt(i, v int) bool {
	// TODO
	return false
}

// RemoveAt removes and returns the element at index i, shifting later
// elements left. Returns (0, false) if i is out of range. Target: O(n).
func (a *DynamicArray) RemoveAt(i int) (int, bool) {
	// TODO
	return 0, false
}

// ============================================================
// Part B — slice problems
// ============================================================

// Reverse reverses nums in place. Pattern: two pointers from the ends.
// Target: O(n) time, O(1) space.
func Reverse(nums []int) {
	// TODO
}

// RotateRight rotates nums right by k steps in place.
// [1 2 3 4 5], k=2 -> [4 5 1 2 3]. k may be larger than len(nums).
// Hint: three reversals. Target: O(n) time, O(1) space.
func RotateRight(nums []int, k int) {
	// TODO
}

// MoveZeroes moves all zeros to the end, keeping the order of the
// non-zero elements. [0 1 0 3 12] -> [1 3 12 0 0].
// Pattern: read/write pointers. Target: O(n) time, O(1) space.
func MoveZeroes(nums []int) {
	// TODO
}

// MaxSubarraySum returns the largest sum of any non-empty contiguous
// subarray (Kadane's algorithm). Returns 0 for an empty slice.
// [-2 1 -3 4 -1 2 1 -5 4] -> 6 (from [4 -1 2 1]). Target: O(n).
func MaxSubarraySum(nums []int) int {
	// TODO
	return 0
}

// PrefixSums returns p where p[0] = 0 and p[i+1] = nums[0] + ... + nums[i].
// len(p) == len(nums)+1. Target: O(n).
func PrefixSums(nums []int) []int {
	// TODO
	return nil
}

// RangeSum returns nums[i] + ... + nums[j] (inclusive) using a slice made by
// PrefixSums. Target: O(1).
func RangeSum(prefix []int, i, j int) int {
	// TODO
	return 0
}

// TwoSumSorted finds indices i < j with nums[i]+nums[j] == target in a
// slice sorted ascending. Returns (0, 0, false) if no pair exists.
// Pattern: two pointers moving inward. Target: O(n) time, O(1) space.
func TwoSumSorted(nums []int, target int) (int, int, bool) {
	// TODO
	return 0, 0, false
}

▶ arrays_test.go the tests — the same file checks yours or the reference · 168 lines›

package arrays

import (
	"slices"
	"testing"
)

func TestDynamicArrayPushGet(t *testing.T) {
	a := NewDynamicArray()
	for i := 0; i < 100; i++ {
		a.Push(i * 10)
	}
	if a.Len() != 100 {
		t.Fatalf("Len() = %d, want 100", a.Len())
	}
	if a.Cap() < 100 || a.Cap() > 256 {
		t.Errorf("Cap() = %d, want doubling growth (between 100 and 256)", a.Cap())
	}
	for i := 0; i < 100; i++ {
		if v, ok := a.Get(i); !ok || v != i*10 {
			t.Fatalf("Get(%d) = (%d, %v), want (%d, true)", i, v, ok, i*10)
		}
	}
	if _, ok := a.Get(100); ok {
		t.Error("Get(100) on a 100-element array should return ok=false")
	}
	if _, ok := a.Get(-1); ok {
		t.Error("Get(-1) should return ok=false")
	}
}

func TestDynamicArrayInsertRemove(t *testing.T) {
	a := NewDynamicArray()
	for _, v := range []int{1, 2, 4} {
		a.Push(v)
	}
	if !a.InsertAt(2, 3) {
		t.Fatal("InsertAt(2, 3) returned false")
	}
	if !a.InsertAt(0, 0) {
		t.Fatal("InsertAt(0, 0) returned false")
	}
	if !a.InsertAt(a.Len(), 5) {
		t.Fatal("InsertAt(Len(), 5) should append and return true")
	}
	if got, want := a.Values(), []int{0, 1, 2, 3, 4, 5}; !slices.Equal(got, want) {
		t.Fatalf("after inserts: %v, want %v", got, want)
	}
	if a.InsertAt(99, 1) {
		t.Error("InsertAt out of range should return false")
	}
	if v, ok := a.RemoveAt(0); !ok || v != 0 {
		t.Errorf("RemoveAt(0) = (%d, %v), want (0, true)", v, ok)
	}
	if v, ok := a.RemoveAt(2); !ok || v != 3 {
		t.Errorf("RemoveAt(2) = (%d, %v), want (3, true)", v, ok)
	}
	if got, want := a.Values(), []int{1, 2, 4, 5}; !slices.Equal(got, want) {
		t.Fatalf("after removes: %v, want %v", got, want)
	}
	if _, ok := a.RemoveAt(4); ok {
		t.Error("RemoveAt(Len()) should return ok=false")
	}
}

func TestReverse(t *testing.T) {
	for _, tc := range []struct{ in, want []int }{
		{[]int{1, 2, 3, 4, 5}, []int{5, 4, 3, 2, 1}},
		{[]int{1, 2}, []int{2, 1}},
		{[]int{7}, []int{7}},
		{[]int{}, []int{}},
	} {
		got := slices.Clone(tc.in)
		Reverse(got)
		if !slices.Equal(got, tc.want) {
			t.Errorf("Reverse(%v) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestRotateRight(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		k    int
		want []int
	}{
		{[]int{1, 2, 3, 4, 5}, 2, []int{4, 5, 1, 2, 3}},
		{[]int{1, 2, 3, 4, 5}, 7, []int{4, 5, 1, 2, 3}},
		{[]int{1, 2, 3}, 0, []int{1, 2, 3}},
		{[]int{1, 2, 3}, 3, []int{1, 2, 3}},
		{[]int{}, 4, []int{}},
	} {
		got := slices.Clone(tc.in)
		RotateRight(got, tc.k)
		if !slices.Equal(got, tc.want) {
			t.Errorf("RotateRight(%v, %d) = %v, want %v", tc.in, tc.k, got, tc.want)
		}
	}
}

func TestMoveZeroes(t *testing.T) {
	for _, tc := range []struct{ in, want []int }{
		{[]int{0, 1, 0, 3, 12}, []int{1, 3, 12, 0, 0}},
		{[]int{0, 0, 1}, []int{1, 0, 0}},
		{[]int{1, 2}, []int{1, 2}},
	} {
		got := slices.Clone(tc.in)
		MoveZeroes(got)
		if !slices.Equal(got, tc.want) {
			t.Errorf("MoveZeroes(%v) = %v, want %v", tc.in, got, tc.want)
		}
	}
}

func TestMaxSubarraySum(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		want int
	}{
		{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, 6},
		{[]int{5, 4, -1, 7, 8}, 23},
		{[]int{-3, -1, -2}, -1},
		{[]int{1}, 1},
		{[]int{}, 0},
	} {
		if got := MaxSubarraySum(tc.in); got != tc.want {
			t.Errorf("MaxSubarraySum(%v) = %d, want %d", tc.in, got, tc.want)
		}
	}
}

func TestPrefixAndRangeSum(t *testing.T) {
	nums := []int{3, -1, 4, 1, 5, 9}
	p := PrefixSums(nums)
	if want := []int{0, 3, 2, 6, 7, 12, 21}; !slices.Equal(p, want) {
		t.Fatalf("PrefixSums(%v) = %v, want %v", nums, p, want)
	}
	for _, tc := range []struct{ i, j, want int }{
		{0, 5, 21}, {1, 3, 4}, {2, 2, 4}, {4, 5, 14},
	} {
		if got := RangeSum(p, tc.i, tc.j); got != tc.want {
			t.Errorf("RangeSum(p, %d, %d) = %d, want %d", tc.i, tc.j, got, tc.want)
		}
	}
}

func TestTwoSumSorted(t *testing.T) {
	for _, tc := range []struct {
		nums   []int
		target int
		ok     bool
	}{
		{[]int{1, 2, 4, 7, 11, 15}, 15, true},
		{[]int{2, 7, 11, 15}, 9, true},
		{[]int{-3, 0, 2, 5}, 2, true},
		{[]int{1, 2, 3}, 100, false},
		{[]int{}, 0, false},
	} {
		i, j, ok := TwoSumSorted(tc.nums, tc.target)
		if ok != tc.ok {
			t.Errorf("TwoSumSorted(%v, %d) ok = %v, want %v", tc.nums, tc.target, ok, tc.ok)
			continue
		}
		if ok && (i >= j || tc.nums[i]+tc.nums[j] != tc.target) {
			t.Errorf("TwoSumSorted(%v, %d) = (%d, %d): not a valid pair", tc.nums, tc.target, i, j)
		}
	}
}

Before you open the solution

Try not to open solution.go until your tests pass, or until you’ve been stuck for a solid half hour. Then compare: different-but-correct is fine; notice where the reference is simpler. go test -tags solutions ./01-arrays/ runs the same tests against it.

▶ solution.go reference solutions — build tag solutions · 133 lines›

//go:build solutions

package arrays

// ---------- DynamicArray ----------

func (a *DynamicArray) Get(i int) (int, bool) {
	if i < 0 || i >= a.size {
		return 0, false
	}
	return a.data[i], true
}

func (a *DynamicArray) grow() {
	newCap := len(a.data) * 2
	if newCap == 0 {
		newCap = 2
	}
	bigger := make([]int, newCap)
	copy(bigger, a.data[:a.size])
	a.data = bigger
}

func (a *DynamicArray) Push(v int) {
	if a.size == len(a.data) {
		a.grow()
	}
	a.data[a.size] = v
	a.size++
}

func (a *DynamicArray) InsertAt(i, v int) bool {
	if i < 0 || i > a.size {
		return false
	}
	if a.size == len(a.data) {
		a.grow()
	}
	// Shift right, starting from the end so nothing is overwritten.
	for j := a.size; j > i; j-- {
		a.data[j] = a.data[j-1]
	}
	a.data[i] = v
	a.size++
	return true
}

func (a *DynamicArray) RemoveAt(i int) (int, bool) {
	if i < 0 || i >= a.size {
		return 0, false
	}
	v := a.data[i]
	for j := i; j < a.size-1; j++ {
		a.data[j] = a.data[j+1]
	}
	a.size--
	a.data[a.size] = 0 // clear the stale slot
	return v, true
}

// ---------- Slice problems ----------

func Reverse(nums []int) {
	for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

func RotateRight(nums []int, k int) {
	n := len(nums)
	if n == 0 {
		return
	}
	k %= n
	if k < 0 {
		k += n
	}
	Reverse(nums)
	Reverse(nums[:k])
	Reverse(nums[k:])
}

func MoveZeroes(nums []int) {
	w := 0 // write position for the next non-zero
	for _, v := range nums {
		if v != 0 {
			nums[w] = v
			w++
		}
	}
	for ; w < len(nums); w++ {
		nums[w] = 0
	}
}

func MaxSubarraySum(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	best, cur := nums[0], nums[0]
	for _, v := range nums[1:] {
		cur = max(v, cur+v)
		best = max(best, cur)
	}
	return best
}

func PrefixSums(nums []int) []int {
	p := make([]int, len(nums)+1)
	for i, v := range nums {
		p[i+1] = p[i] + v
	}
	return p
}

func RangeSum(prefix []int, i, j int) int {
	return prefix[j+1] - prefix[i]
}

func TwoSumSorted(nums []int, target int) (int, int, bool) {
	lo, hi := 0, len(nums)-1
	for lo < hi {
		switch s := nums[lo] + nums[hi]; {
		case s == target:
			return lo, hi, true
		case s < target:
			lo++
		default:
			hi--
		}
	}
	return 0, 0, false
}

FURTHER

Going further.

Write a benchmark comparing your DynamicArray.Push with plain append (go test -bench .). Then try growing by 1.5× instead of 2× and compare.
LeetCode practice: Remove Duplicates from Sorted Array, Product of Array Except Self, Container With Most Water.

QUIZ

Check yourself.

Four questions. Answer each one in your head — or out loud — before you open the answer.

Question 1

A dynamic array doubles its capacity whenever it's full. What's the total cost of n appends, counting the copying?

AO(n)
BO(n log n)
CO(n²)
DO(log n)

Show the answer

A — The copies form 1 + 2 + 4 + … + n, which is less than 2n. Spread over n appends that's O(1) each, amortized.

Question 2

a := []int{1, 2, 3, 4}; b := a[1:3]; b[0] = 9. What is a now?

A[1 2 3 4]
B[1 9 3 4]
C[9 2 3 4]
DIt depends on cap(a)

Show the answer

B — Slicing doesn't copy. b views a's backing array starting at index 1, so b[0] is a[1].

Question 3

MaxSubarraySum([-3, -1, -2]) should return…

A0 (take nothing)
B-1
C-6
D-3

Show the answer

B — The subarray must be non-empty, so the best you can do is the single element -1. A Kadane's that starts best at 0 gets this wrong.

Question 4

Inserting at index 0 of a 1,000,000-element dynamic array costs about…

AO(1)
BO(log n)
CO(n) — every element shifts right
DO(n) only when it needs to grow

Show the answer

C — Every existing element moves one slot to make room, whether or not the array grows.

Where to next.

Commit your work before you move on to module 2, so git log shows your own progress through the course.

Next →: Module 2 — Strings

Character manipulation, counting, sliding windows, and pattern search — with Go's bytes-versus-runes twist.

⌂

Course home

All ten modules, the course download, and how to track your progress.