02. Arrays, Strings and Slices

Arrays are the most fundamental data structure. Everything else is built on top of them or exists because arrays aren't good enough for a specific use case. Understanding how contiguous memory works explains why arrays are fast, when they're slow, and why Go's slices behave the way they do.

Contiguous Memory

An array stores elements side by side in memory. Element 0 is at address X, element 1 is at X+size, element 2 is at X+2*size. This is why index access is O(1) — the CPU calculates the exact memory address with simple arithmetic.

nums := [5]int{10, 20, 30, 40, 50}
// Memory: [10][20][30][40][50]
//          ^        ^
//          0        2  ← jump directly, no scanning

This contiguous layout also means arrays are cache-friendly. When the CPU loads element 0, it pulls nearby memory into cache. Elements 1, 2, 3 are already there. Linked lists scatter nodes across memory — every access is a cache miss.

Go Slices

Go doesn't use raw arrays much. Slices are the workhorse — a thin wrapper over an array with three fields:

// What a slice actually is
type slice struct {
    ptr *[...]T  // pointer to underlying array
    len int      // number of elements in use
    cap int      // total allocated capacity
}

This design gives you dynamic sizing with O(1) access:

s := make([]int, 0, 4) // len=0, cap=4
s = append(s, 1)       // len=1, cap=4 — no allocation
s = append(s, 2, 3, 4) // len=4, cap=4 — still fits
s = append(s, 5)       // len=5, cap=8 — doubled, copied

When capacity runs out, Go allocates a new array (roughly 2x the size) and copies everything. That's why append is O(1) amortized but occasionally O(n).

make() — Length vs Capacity

The two arguments after the type in make control very different things. Mixing them up is a common source of bugs.

s1 := make([]int, 3, 5)
// len=3, cap=5 → [0, 0, 0] — 3 zero-valued elements exist
// s1[0], s1[1], s1[2] are valid immediately

s2 := make([]int, 0, 5)
// len=0, cap=5 → [] — empty, no elements
// s2[0] would panic (index out of range)

The classic bug is combining a non-zero length with append:

s := make([]int, 3, 5)
s = append(s, 42)
fmt.Println(s) // [0, 0, 0, 42] — appended after the zeros

Rule of thumb: if you're using append, set length to 0. If you're using index assignment, set length to the size you need.

Shared Backing Arrays

When you slice a slice, the new slice shares the same backing array. Mutations propagate.

original := []int{1, 2, 3, 4, 5}
sub := original[1:3] // [2, 3]

sub[0] = 99
fmt.Println(original) // [1, 99, 3, 4, 5] — original changed!

If you need an independent copy:

// 1. copy() — explicit
dst := make([]int, len(original))
copy(dst, original)

// 2. append trick — one-liner
dst2 := append([]int{}, original...)

// 3. slices.Clone() — clearest intent (Go 1.21+)
dst3 := slices.Clone(original)

Common Slice Operations

// Delete element at index i (order preserved)
a = append(a[:i], a[i+1:]...)

// Merge two slices
merged := append(s1, s2...)

// Insert val at index i
a = append(a[:i], append([]int{val}, a[i:]...)...)

// Or with Go 1.21+ (cleaner):
a = slices.Insert(a, i, val)

Delete and insert are O(n) because elements shift. Append to the end is O(1) amortized.

Operation Costs

The key insight: arrays are fast for reading, slow for inserting/deleting in the middle. If you need frequent insertions at arbitrary positions, arrays are the wrong choice.

Strings in Go

Strings in Go are immutable byte slices. You can't change individual characters.

s := "hello"
// s[0] = 'H' // compile error: cannot assign to s[0]

String concatenation in a loop is O(n²) because each + creates a new string. Use strings.Builder for O(n):

// O(n²) — each iteration copies the growing string
result := ""
for _, word := range words {
    result += word
}

// O(n) — writes to a buffer, one allocation at the end
var b strings.Builder
for _, word := range words {
    b.WriteString(word)
}
result := b.String()

Converting between []byte and string is how you mutate string content:

s := "hello"
b := []byte(s)  // copy into mutable byte slice
b[0] = 'H'
s = string(b)   // convert back → "Hello"

Rune vs Byte

A byte is 8 bits. A rune is a Unicode code point (up to 4 bytes). ASCII characters are 1 byte, but emoji and international characters are multi-byte.

s := "Go🚀"
fmt.Println(len(s))          // 6 — bytes, not characters
fmt.Println(len([]rune(s)))  // 3 — actual characters

range over a string iterates by rune. A classic for loop with s[i] gives raw bytes:

for i, r := range "Go🚀" {
    fmt.Printf("index=%d rune=%c\n", i, r)
}
// index=0 rune=G
// index=1 rune=o
// index=2 rune=🚀  ← range handles multi-byte correctly

Use range when you care about characters. Use s[i] when you know it's ASCII-only.

Frequency Counting

Counting character frequencies is a core pattern. For lowercase English letters, a [26]int array is faster than a map.

LeetCode 242 - Valid Anagram

func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }
    var freq [26]int
    for i := 0; i < len(s); i++ {
        freq[s[i]-'a']++
        freq[t[i]-'a']--
    }
    for _, count := range freq {
        if count != 0 {
            return false
        }
    }
    return true
}

O(n) time, O(1) space — the array is always size 26 regardless of input.

Common Patterns

Two pointers and sliding window — covered in depth in the next lesson. The key idea: use two indices to avoid nested loops, turning O(n²) into O(n).

Read/write pointer — scan with one pointer, write with another. Compacts in-place.

LeetCode 26 - Remove Duplicates from Sorted Array

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    w := 1
    for r := 1; r < len(nums); r++ {
        if nums[r] != nums[r-1] {
            nums[w] = nums[r]
            w++
        }
    }
    return w // new length
}

Prefix sum — precompute cumulative sums so any range sum is O(1). See the Prefix Sum example for a complete implementation with range queries.

prefix := make([]int, len(nums)+1)
for i, n := range nums {
    prefix[i+1] = prefix[i] + n
}
// Sum of nums[l..r] = prefix[r+1] - prefix[l]

Rotate array — three reverses, O(n) time, O(1) space.

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

func rotate(nums []int, k int) {
    k %= len(nums)
    reverse(nums)            // reverse all
    reverse(nums[:k])        // reverse first k
    reverse(nums[k:])        // reverse the rest
}
// [1,2,3,4,5,6,7] rotated by 3 → [5,6,7,1,2,3,4]

LeetCode 88 - Merge Sorted Array

Fill from the end to avoid overwriting.

// Example:
//   nums1 = [1, 3, 5, 0, 0, 0], m = 3
//   nums2 = [2, 4, 6],           n = 3
//
//   Step 1: compare 5 vs 6 → write 6 at index 5 → [1,3,5,0,0,6]
//   Step 2: compare 5 vs 4 → write 5 at index 4 → [1,3,5,0,5,6]
//   Step 3: compare 3 vs 4 → write 4 at index 3 → [1,3,5,4,5,6]
//   Step 4: compare 3 vs 2 → write 3 at index 2 → [1,3,3,4,5,6]
//   Step 5: compare 1 vs 2 → write 2 at index 1 → [1,2,3,4,5,6]
//   Step 6: j < 0, done                          → [1,2,3,4,5,6]

func merge(nums1 []int, m int, nums2 []int, n int) {
    i, j, k := m-1, n-1, m+n-1
    for j >= 0 {
        if i >= 0 && nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
}

When to Use Arrays

• You need O(1) random access by index
• Data size is known or grows at the end (append-heavy)
• You want cache-friendly iteration
• You're doing sliding window or two-pointer problems

When NOT to Use Arrays

• Frequent insertions/deletions in the middle → linked list or tree
• Need O(1) lookup by value → hash map
• Need sorted order with fast insert → balanced BST or heap

Practice Problems

Key Takeaways

• Arrays give O(1) access because elements are contiguous in memory
• Go slices are pointer + length + capacity — dynamic arrays with amortized O(1) append
• make([]T, 0, n) + append for building up. make([]T, n) + index for fixed-size fills. Don't mix them.
• Slicing a slice shares the backing array — mutations propagate. Use copy for independence.
• Insert/delete in the middle is O(n) because elements must shift
• Strings are immutable byte slices. range iterates by rune, len() counts bytes.
• Use strings.Builder for concatenation, [26]int for frequency counting
• Two pointers, sliding window, prefix sum, and read/write pointer are the core patterns
• Choose arrays when you need fast access; choose something else when you need fast insertion