Free sample

01 Reading a Problem: Choosing the Right Tool 04 Arrays & Strings SD18 Design a URL Shortener

Module 04

Arrays & Strings

Bytes vs runes, slicing without footguns, and the in-place mindset.

By the end of this module you can…

Work fluently with slice indices: bounds, half-open ranges, no negative indexing
Apply the core in-place micro-patterns: reverse, rotate, partition
Use a fixed-size array as a frequency table for strings
Handle 2-D grids: neighbour iteration and in-place marking

The index mindset

Python lets you get sloppy: negative indices, s[::-1], automatic growth. Go makes you think in half-open ranges [start, end) and explicit bounds. Internalise these:

a[i:j] has length j - i and contains indices i … j-1. a[i:i] is empty.
Last element is a[len(a)-1]. There is no a[-1]: written as a literal it doesn't compile, and a negative index in a variable panics at run time.
A window of size k ending at r starts at r - k + 1 and is a[r-k+1 : r+1].
The midpoint without overflow: mid := lo + (hi-lo)/2.

The in-place micro-patterns

These show up as sub-steps inside bigger problems. Know them cold.

1. Reverse a range

Reverse in place — O(1) extra space

1 / 7

step 1: l at 0, r at n-1. Swap them.

Two indices walk toward the middle, swapping. n/2 swaps, no second array.

reverse.go

1func reverse(a []int, lo, hi int) { // reverses a[lo:hi+1] in place
2    for lo < hi {
3        a[lo], a[hi] = a[hi], a[lo]
4        lo++
5        hi--
6    }
7}

2. Rotate by k — the three-reversal trick

Rotating [1 2 3 4 5] right by 2 gives [4 5 1 2 3]. Reverse the whole thing, then reverse the first k, then reverse the rest. O(n) time, O(1) space.

rotate.go

1func rotateRight(a []int, k int) {
2    n := len(a)
3    if n == 0 { return }
4    k %= n
5    reverse(a, 0, n-1)     // 5 4 3 2 1
6    reverse(a, 0, k-1)     // 4 5 3 2 1
7    reverse(a, k, n-1)     // 4 5 1 2 3
8}

3. Partition around a predicate (write index)

partition.go

1// Move all non-zero values to the front, preserving their order. O(n), O(1).
2func moveZeroes(nums []int) {
3    w := 0 // next write position
4    for _, x := range nums {
5        if x != 0 {
6            nums[w] = x
7            w++
8        }
9    }
10    for ; w < len(nums); w++ {
11        nums[w] = 0
12    }
13}

★Key idea

The write index (a.k.a. slow pointer) is the single most reused array idiom: w lags behind the scan and only advances when you keep an element. Dedup, compaction, filtering, in-place partitioning are all this.

Strings as frequency tables

For lowercase-ASCII problems, a [26]int array beats a map: stack-allocated, no hashing, trivially comparable.

anagram.go

1func isAnagram(s, t string) bool {
2    if len(s) != len(t) {
3        return false
4    }
5    var freq [26]int
6    for i := 0; i < len(s); i++ {
7        freq[s[i]-'a']++
8        freq[t[i]-'a']--
9    }
10    return freq == [26]int{} // arrays are comparable with ==
11}

Gos[i] - 'a'

s[i] is a byte; 'a' is a rune constant that fits in a byte. s[i] - 'a' maps 'a'…'z' to 0…25. This only works for known ASCII ranges — guard your inputs.

Building strings

Go strings are immutable, so s += x allocates a new string and copies everything built so far. In a loop that is O(n²) — fine for ten pieces, a timeout for a hundred thousand. strings.Builder appends into one growing buffer: O(n) total.

var b strings.Builder
b.Grow(len(s))          // optional pre-size
for i := len(s) - 1; i >= 0; i-- {
    b.WriteByte(s[i])   // reverse an ASCII string
}
return b.String()

// Unicode-safe reverse:
r := []rune(s)
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
    r[i], r[j] = r[j], r[i]
}
return string(r)

2-D grids

grid.go

1rows, cols := len(grid), len(grid[0])
2
3// 4-directional neighbours — the dirs array is the idiom
4dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
5for _, d := range dirs {
6    nr, nc := r+d[0], c+d[1]
7    if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
8        continue // out of bounds
9    }
10    // visit grid[nr][nc]
11}
12
13// In-place marking to avoid a separate visited array:
14grid[r][c] = '#' // or 0, or a sentinel — restore later if the caller needs it

Reach for this when you see…

The input is a sequence you can index, and the answer is a rearrangement of it rather than new data — “in place”, “without extra space”, “O(1) memory”.
You are asked to move, remove or partition elements while keeping relative order: “move zeroes”, “remove duplicates from a sorted array”, “partition by parity”.
A rotation, reversal, or swap of two regions — very often three reversals in disguise.
The alphabet is small and fixed (lowercase letters, digits, bytes), so a fixed-size count array beats a map.
A 2-D grid where the answer is written back into the grid itself, using the first row and column as scratch space.

Probably NOT this when…

You need to look a value up by key rather than reach it by position — that is a map, not an array.
You are repeatedly inserting or deleting in the middle: every operation shifts the tail, so reach for a linked list or a different structure.
The window or range is contiguous and you want an optimum over all of them — that is Sliding Window, built on top of these mechanics.
You need the smallest or largest item repeatedly as the set changes — that is a heap.

Recap — burn these in

Think in half-open ranges [i,j); no negative indices; last is a[len(a)-1].
Memorise reverse-range, rotate-by-3-reversals, and the write-index partition.
[26]int frequency array for lowercase strings — comparable, no hashing.
Grid neighbours via a dirs array + a bounds check; mark in place to skip a visited set.
Build strings with strings.Builder, never += in a loop.

Next · Practice · 4 exercisesWrite each one cold and run it right in the page.

What the course does between lessons

The part an AI chat can't give you

An LLM will happily explain a monotonic stack — and you should let it. What it won't do is decide what you learn next, remember that you got something wrong three weeks ago, or put it back in front of you today. That machinery is the course.

Review · try it

card 1 / 5

Think in half-open ranges [i,j); no …

Real cards from the two free modules, scheduled by the same SM-2 code the course runs. Every module's key points become cards.

Today

Review 12 cards, then continue 14 Backtracking.

The dashboard picks the one next thing, so you never open the course and wonder what to do.

Problem → pattern

“sorted” + “find a pair”→Two pointers
“longest substring…”→Sliding window
“next greater element”→Monotonic stack
“top k” / “k closest”→Heap
“number of ways”→DP over states

Two full indexes map the phrases you actually see in a problem to the structure or building block they imply. Browse the DSA one free →

The rest of it

That's 3 of 81.

The rest of Data Structures & Algorithms, all of Broader CS, and the full System Design track — including 19 case studies you run as mock interviews — plus every exercise and the spaced-repetition review, are one payment away.

Get lifetime access — £39£69 intro price

Already bought it? Unlock