Arrays & Slices

Contiguous Memory

An array stores its elements side by side in one block of memory. Everything that makes arrays fast — and everything that makes some operations slow — follows from that single fact.

Why Indexing Is O(1)

Element i of an array starting at address base with elements of size bytes lives at base + i × size. Computing that address is one multiplication and one addition, whatever the value of i — that is constant time. A linked list has no such formula: to reach element i it must follow i pointers.

Cache Locality

CPUs do not read single bytes from memory; they load whole cache lines (typically 64 bytes) at a time. Scanning an []int therefore loads eight elements per memory access, and the hardware prefetcher predicts the next line. This is why a linear scan over a slice often beats a "better" structure whose nodes are scattered across the heap. Big O counts steps; cache behavior decides how long each step takes.

Slice Operations and Their Cost

Go slices are dynamic arrays: a header (pointer, length, capacity) over a backing array, as shown in the Data Structures Map. The table lists what the common operations cost and why.

Insert and Delete in the Middle

Inserting makes room by shifting the tail one place right; deleting closes the gap by shifting it left. The built-in copy handles overlapping ranges correctly, so each operation is a few lines:

// insertAt returns s with v inserted at index i (0 <= i <= len(s)).
func insertAt(s []int, i, v int) []int {
	s = append(s, 0)     // grow by one (may reallocate)
	copy(s[i+1:], s[i:]) // shift the tail right — O(n-i)
	s[i] = v
	return s
}

// deleteAt removes s[i], keeping the order of the other elements.
func deleteAt(s []int, i int) []int {
	copy(s[i:], s[i+1:]) // shift the tail left over s[i]
	return s[:len(s)-1]  // drop the now-duplicated last slot
}

// deleteUnordered removes s[i] in O(1) when order does not matter.
func deleteUnordered(s []int, i int) []int {
	s[i] = s[len(s)-1]
	return s[:len(s)-1]
}

Filtering in Place

A write index that trails the read index lets you filter a slice without allocating a new one. Elements to keep are copied down to the write position; because the write index never passes the read index, nothing unread is overwritten. This read/write pattern is the simplest form of the same-direction two-pointer technique below.

// filterInPlace keeps elements for which keep returns true.
// O(n) time, O(1) extra space; the result shares s's memory.
func filterInPlace(s []int, keep func(int) bool) []int {
	w := 0 // next write position
	for _, v := range s {
		if keep(v) {
			s[w] = v
			w++
		}
	}
	return s[:w]
}

The slices Package

Go 1.21 added the generic slices package, which implements these operations for any element type. Use it in production code, and remember the costs when calling it inside loops:

All operations above, hand-written and via the package, with a three-reversal rotation: 11_slice_operations.go.

Two Pointers

Many pair problems look like they need a nested loop: "is there a pair that…", "find two positions such that…". The two-pointer technique uses two indices that each move in only one direction. Each index moves at most n times, so the whole scan is O(n). The key is a rule that proves the skipped positions cannot contain the answer.

Top: on sorted data, each step moves one pointer and permanently discards one candidate. Bottom: a sliding window updates its sum with one addition and one subtraction instead of re-adding the whole window.

Opposite Ends

Start at both ends of a sorted slice. If the sum of the two values is too small, the left value cannot pair with anything — every remaining partner is even smaller — so move left inward. If the sum is too large, the symmetric argument moves right inward.

// pairWithSum finds two values in a sorted slice that add up to target.
func pairWithSum(sorted []int, target int) (int, int, bool) {
	lo, hi := 0, len(sorted)-1
	for lo < hi {
		switch sum := sorted[lo] + sorted[hi]; {
		case sum == target:
			return sorted[lo], sorted[hi], true
		case sum < target:
			lo++ // sorted[lo] is too small for every remaining partner
		default:
			hi-- // sorted[hi] is too large for every remaining partner
		}
	}
	return 0, 0, false
}

Same Direction

A slow pointer marks the end of the part of the slice already processed; a fast pointer explores ahead. Removing duplicates from a sorted slice in place is the classic example: the invariant is that s[0..slow] holds every distinct value seen so far.

// dedupeSorted removes repeats from a sorted slice in place: O(n), O(1) space.
func dedupeSorted(s []int) []int {
	if len(s) == 0 {
		return s
	}
	slow := 0
	for fast := 1; fast < len(s); fast++ {
		if s[fast] != s[slow] { // new value: extend the unique prefix
			slow++
			s[slow] = s[fast]
		}
	}
	return s[:slow+1]
}

Why Skipping Is Safe

The technique is only correct when you can justify every skip. Consider "container with most water": lines of height h[i] at positions i; choose two lines to hold the most water, min(h[lo], h[hi]) × (hi − lo). Moving the taller line inward can only shrink the width while the height stays limited by the shorter line, so the area cannot grow. Therefore always move the shorter line. Without such an argument, a two-pointer solution is a guess. The demo checks this solution against the O(n²) brute force on 2,000 random inputs, together with in-place deduplication, merging, and Dijkstra's three-way "Dutch flag" partition: 12_two_pointers.go.

Sliding Window

When a problem asks about contiguous ranges — subarrays or substrings — neighboring ranges overlap almost completely. A sliding window keeps a summary of the current range (a sum, a count, a set of characters) and updates it as the window moves, instead of recomputing it.

Fixed-Size Window

For the largest sum of k consecutive elements, the brute force sums each window separately — O(n·k). Sliding the window adds the element that enters and subtracts the one that leaves — O(n).

// maxSumFixed returns the largest sum of k consecutive elements (1 <= k <= len).
func maxSumFixed(nums []int, k int) int {
	sum := 0
	for i := 0; i < k; i++ { // the first window
		sum += nums[i]
	}
	best := sum
	for right := k; right < len(nums); right++ {
		sum += nums[right] - nums[right-k] // enter right, leave left
		best = max(best, sum)
	}
	return best
}

Variable-Size Window

For "longest" and "shortest" problems the window grows on the right and shrinks on the left as needed. For the longest substring without repeated characters, extend the right edge; when the new character already occurs inside the window, jump the left edge past its previous position. Each index enters and leaves the window at most once, so the total work is O(n).

// longestUnique returns the length of the longest substring with no repeated byte.
func longestUnique(s string) int {
	var lastSeen [256]int // most recent index of each byte value
	for i := range lastSeen {
		lastSeen[i] = -1
	}
	best, left := 0, 0
	for right := 0; right < len(s); right++ {
		if lastSeen[s[right]] >= left { // duplicate inside the window
			left = lastSeen[s[right]] + 1
		}
		lastSeen[s[right]] = right
		best = max(best, right-left+1)
	}
	return best
}

When the Window Fails

Shrinking a window greedily is correct only if the window's property changes monotonically: growing it always moves the summary one way, shrinking always the other. "Shortest subarray with sum ≥ target" works for positive numbers, but with negative numbers adding an element can decrease the sum, and the greedy shrink misses answers. Those problems need prefix sums. Fixed, variable, and minimum-length windows, each checked against brute force: 13_sliding_window.go.

Prefix Sums

A prefix sum array precomputes running totals once, in O(n), and then answers any range-sum question in O(1). It trades a little memory for turning a loop into two array reads.

Range Sum Queries

Define prefix[0] = 0 and prefix[i] = nums[0] + … + nums[i−1]. The sum of the half-open range nums[l:r] is prefix[r] − prefix[l]. The leading zero removes the special case for ranges that start at index 0.

// buildPrefix returns p with p[i] = sum of nums[:i]; len(p) == len(nums)+1.
func buildPrefix(nums []int) []int {
	p := make([]int, len(nums)+1)
	for i, v := range nums {
		p[i+1] = p[i] + v
	}
	return p
}

// rangeSum returns the sum of nums[l:r] in O(1).
func rangeSum(p []int, l, r int) int {
	return p[r] - p[l]
}

Prefix Sums with a Map

How many contiguous ranges sum to exactly k? A range ending at position r sums to k exactly when some earlier prefix equals prefix[r] − k. Counting earlier prefixes in a map turns each check into an O(1) lookup, giving O(n) overall. Unlike a sliding window, this works with negative numbers.

// countSubarraysWithSum counts contiguous ranges whose sum equals k.
func countSubarraysWithSum(nums []int, k int) int {
	seen := map[int]int{0: 1} // the empty prefix has sum 0
	count, running := 0, 0
	for _, v := range nums {
		running += v
		count += seen[running-k] // earlier prefixes that complete a range
		seen[running]++
	}
	return count
}

Difference Arrays and 2D Sums

Two extensions follow from the same idea. A difference array — the inverse of a prefix sum — applies "add v to every element of [l, r)" in O(1) by writing +v at l and −v at r; one prefix pass at the end materializes all updates. A 2D prefix sum answers rectangle sums in a matrix in O(1) using inclusion–exclusion. Both, plus the map technique checked against brute force: 14_prefix_sums.go.

Common Pitfalls

Slice bugs in Go usually come from forgetting that slices share memory or that range copies values.

Modifying the Range Variable

In for _, v := range s { v *= 2 }, v is a copy of each element; the slice does not change. Write through the index instead: for i := range s { s[i] *= 2 }.

Small Slices Keeping Large Arrays Alive

A sub-slice keeps the entire backing array reachable. Returning data[:10] from a 100 MB buffer keeps all 100 MB in memory for as long as the small slice lives. Copy the part you need with slices.Clone when the source is large and short-lived.

Mixing Inclusive and Exclusive Bounds

Go slice expressions are half-open: s[l:r] contains r − l elements and excludes s[r]. Algorithms written with inclusive [l, r] ranges need r − l + 1 and <= in loop conditions. Pick one convention per function, write it in a comment, and test empty and single-element ranges.

Practice Lab

Each exercise has a brute-force solution; write it first and use it to test your faster version.

Run the Demos

1. In 12_two_pointers.go, change maxWater to move the taller line and watch the random cross-check report mismatches.
2. In 13_sliding_window.go, call minLenAtLeast on [1, -1, 5] with target 5. It returns 3, but [5] alone has length 1 — explain which shrink step went wrong.

Exercises

1. Three sum. Find all unique triplets that sum to zero. Sort, fix the first element, then run opposite-end two pointers on the rest: O(n²) instead of O(n³).
2. Minimum window substring. Find the shortest substring of s containing every character of t (with multiplicity). Use a variable window and a count of characters still missing.
3. Equilibrium index. Find an index where the sum of elements to its left equals the sum to its right, in one pass with a running total.
4. Product except self. Return out[i] = product of all elements except nums[i], without division, using prefix and suffix products.

Next lesson: Linked Lists.