L7–L12 Data Structures

L7. All Sorting Algorithms

Definition: rearrange values into order. Simple sorts (bubble, selection, insertion) repeatedly fix the next position. Merge and quick divide the work; heap sort uses a heap.

Real-world use:

SortBestAverageWorstExtra spaceStable?
BubbleO(n) with swap flagO(n²)O(n²)O(1)yes
SelectionO(n²)O(n²)O(n²)O(1)no
InsertionO(n)O(n²)O(n²)O(1)yes
MergeO(n log n)O(n log n)O(n log n)O(n)yes if <=
QuickO(n log n)O(n log n)O(n²)O(log n) stackno

1. Bubble sort

Walk adjacent pairs. After pass i, the largest remaining value is at the end. If a pass makes no swaps, stop.

Real-world use: teaching sort, or a tiny almost-sorted list (one swap left) where the early-exit flag helps.

Video array: [5,6,1,3]

  1. 5,6 already ordered. 6,1 swap → [5,1,6,3]. 6,3 swap → [5,1,3,6].
  2. 5,1 swap → [1,5,3,6]. 5,3 swap → [1,3,5,6].
  3. 1,3 already ordered. No more inversions.
func BubbleSort(nums []int) {
	for end := len(nums) - 1; end > 0; end-- {
		swapped := false
		for i := 0; i < end; i++ {
			if nums[i] > nums[i+1] {
				nums[i], nums[i+1] = nums[i+1], nums[i]
				swapped = true
			}
		}
		if !swapped {
			return
		}
	}
}

Complexity: time O(n²) worst/average, O(n) if already sorted. Extra space O(1).

2. Selection sort

For each index i, find the minimum in nums[i:] and swap it into place. Always n-1 + n-2 + … scans, so always O(n²).

Real-world use: pick 1st, 2nd, 3rd place from a small contest when you want few swaps (at most one per position).

Video array: [64,25,12,22,11]

imin of suffixafter swap
011[11,25,12,22,64]
112[11,12,25,22,64]
222[11,12,22,25,64]
325[11,12,22,25,64]
func SelectionSort(nums []int) {
	for i := 0; i < len(nums); i++ {
		minIdx := i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		nums[i], nums[minIdx] = nums[minIdx], nums[i]
	}
}

Complexity: time O(n²) in every case. Extra space O(1).

3. Insertion sort

nums[:i] is already sorted. Pull key = nums[i] left until it sits in order. Good on nearly sorted input.

Real-world use: inserting one new card into a sorted hand, or one new email into an already-sorted inbox.

Video array: [12,11,13,5,6]

keysorted prefix after insert
11[11,12,13,5,6]
13[11,12,13,5,6]
5[5,11,12,13,6]
6[5,6,11,12,13]
func InsertionSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
}

Complexity: time O(n²) worst/average, O(n) if already sorted. Extra space O(1).

4. Merge sort

Split until one element, then merge two sorted halves with two pointers. Reuse one temp slice.

Real-world use: merge two already-sorted customer lists, or an external sort when each half lives in a file.

Video array: [38,27,43,10]

[38,27,43,10]
  [38,27]     [43,10]
 [38] [27]   [43] [10]
  [27,38]     [10,43]
    [10,27,38,43]

<= on the left half keeps equal keys in original order (stable).

func MergeSort(nums []int) {
	tmp := make([]int, len(nums))
	var sortRange func(lo, hi int)
	sortRange = func(lo, hi int) {
		if hi-lo <= 1 {
			return
		}
		mid := lo + (hi-lo)/2
		sortRange(lo, mid)
		sortRange(mid, hi)
		i, j, k := lo, mid, lo
		for i < mid && j < hi {
			if nums[i] <= nums[j] {
				tmp[k] = nums[i]
				i++
			} else {
				tmp[k] = nums[j]
				j++
			}
			k++
		}
		copy(tmp[k:hi], nums[i:mid])
		copy(tmp[k+(mid-i):hi], nums[j:hi])
		copy(nums[lo:hi], tmp[lo:hi])
	}
	sortRange(0, len(nums))
}

Complexity: time O(n log n) always. Extra space O(n) for tmp plus O(log n) recursion.

5. Quick sort (Lomuto, last element is pivot)

The video partitions around a pivot: smaller values left, larger values right, then recurse. Walkthrough: [10,80,30,90,40], pivot 40.

Real-world use: the usual in-memory sort when you can pick a pivot; also “partition around a threshold” (cheap vs expensive items).

  1. Scan 10,80,30,90. Values <= 40 are packed to the front: 10, then 30.
  2. Swap pivot into the hole → [10,30,40,90,80].
  3. Recurse on [10,30] and [90,80].

Worst case is already-sorted input with this pivot rule (O(n²)). Average is O(n log n).

func QuickSort(nums []int) {
	quickSortRange(nums, 0, len(nums)-1)
}

func lomutoPartition(nums []int, lo, hi int) int {
	pivot := nums[hi]
	store := lo
	for i := lo; i < hi; i++ {
		if nums[i] <= pivot {
			nums[store], nums[i] = nums[i], nums[store]
			store++
		}
	}
	nums[store], nums[hi] = nums[hi], nums[store]
	return store
}

Complexity: time O(n log n) average, O(n²) worst (sorted input with this pivot). Extra space O(log n) recursion, O(n) worst.

L8. Hash Maps

Definition: a key-value table. Hash the key to a bucket index, then walk that bucket’s chain. The same key updates its value; different keys that land in the same bucket sit together.

Real-world use:

1. Internal working — separate chaining

Video example: John→25, Tom→30, then update John→40.

Real-world use: a phone book or session store: same name updates the age; two names that hash to one shelf share a chain.

type ChainHashMap struct {
	buckets []*chainEntry
}

func (m *ChainHashMap) Put(key, value string) {
	i := m.bucket(key)
	for e := m.buckets[i]; e != nil; e = e.next {
		if e.key == key {
			e.value = value // update, do not insert a second John
			return
		}
	}
	m.buckets[i] = &chainEntry{key: key, value: value, next: m.buckets[i]}
}

Complexity: average get/put time O(1), extra space O(n + buckets). A bad hash or many collisions degrades to O(n) time.

2. Frequency count

"abcabc" → a:2 b:2 c:2.

Real-world use: how many times each SKU, error code, or word appears in a log.

func CharFrequency(s string) map[rune]int {
	freq := map[rune]int{}
	for _, ch := range s {
		freq[ch]++
	}
	return freq
}

Complexity: time O(n), extra space O(u) for distinct characters.

3. Two Sum (unsorted)

Look up target-current before storing the current index so one element is not used twice.

Real-world use: two cart items that add to a gift-card amount, when the list is not sorted.

func TwoSum(nums []int, target int) []int {
	seen := map[int]int{}
	for i, v := range nums {
		if j, ok := seen[target-v]; ok {
			return []int{j, i}
		}
		seen[v] = i
	}
	return nil
}

Complexity: time O(n), extra space O(n).

4. Word Pattern

Both directions must match. abba / dog cat cat dog is true. abba / dog cat cat fish is false. abba / dog dog dog dog is false (two letters, one word).

Real-world use: a cipher or template: pattern abba must map 1-to-1 onto words, like a rhyme scheme.

func WordPattern(pattern, s string) bool {
	words := strings.Fields(s)
	if len(words) != len(pattern) {
		return false
	}
	p2w := map[byte]string{}
	w2p := map[string]byte{}
	for i := 0; i < len(pattern); i++ {
		p, w := pattern[i], words[i]
		if mapped, ok := p2w[p]; ok && mapped != w {
			return false
		}
		if mapped, ok := w2p[w]; ok && mapped != p {
			return false
		}
		p2w[p], w2p[w] = w, p
	}
	return true
}

Complexity: time O(n), extra space O(n) for the two maps.

5. Valid Anagram

"anagram" and "nagaram". Increment for s, decrement for t. Every bucket must finish at 0.

Real-world use: two product names that use the same letters, or two bags of letter tiles that match.

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

Complexity: time O(n), extra space O(1) — the 26 counters do not grow with n.

6. Group Anagrams

Video uses the sorted word as the key and mentions a 26-count signature as the faster homework. The Go code uses the count key.

Real-world use: put eat, tea, and ate on one pantry shelf; group anagrams in a word game.

Input: eat tea tan ate nat bat → {ate,eat,tea}, {nat,tan}, {bat}.

func GroupAnagrams(strs []string) [][]string {
	groups := map[[26]int][]string{}
	for _, word := range strs {
		var key [26]int
		for i := 0; i < len(word); i++ {
			key[word[i]-'a']++
		}
		groups[key] = append(groups[key], word)
	}
	out := make([][]string, 0, len(groups))
	for _, g := range groups {
		out = append(out, g)
	}
	return out
}

Complexity: time O(T) where T is the total number of letters. Extra space O(T) for the groups.

L9. Stacks

Definition: last-in, first-out. You only add or remove from the top. That matches nested work, undo, and “the nearest larger value still waiting on the right.”

Real-world use:

1. Valid parentheses

Push an opener. A closer must match the top. The stack must be empty at the end.

Real-world use: a linter for (, [, { in code, JSON, or a config file.

func IsValidParentheses(s string) bool {
	pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		if open, ok := pairs[s[i]]; ok {
			if len(stack) == 0 || stack[len(stack)-1] != open {
				return false
			}
			stack = stack[:len(stack)-1]
			continue
		}
		stack = append(stack, s[i])
	}
	return len(stack) == 0
}

Complexity: time O(n), extra space O(n).

2. Next Greater Element I

nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1].

Real-world use: next warmer day for each temperature, or the next higher stock price after today.

Scan nums2 left to right. Keep a decreasing stack. When the current value is larger, it is the next greater of every popped value. Leftovers map to -1.

func NextGreaterElement(nums1, nums2 []int) []int {
	next := map[int]int{}
	stack := []int{}
	for _, x := range nums2 {
		for len(stack) > 0 && stack[len(stack)-1] < x {
			next[stack[len(stack)-1]] = x
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, x)
	}
	for _, leftover := range stack {
		next[leftover] = -1
	}
	out := make([]int, len(nums1))
	for i, v := range nums1 {
		out[i] = next[v]
	}
	return out
}

Complexity: time O(n + m), extra space O(n). n = len(nums2), m = len(nums1).

3. Simplify path

/home/user/documents/../pictures → /home/user/pictures.

Real-world use: resolve .. and extra slashes in a file path or a URL path.

Split on /. Ignore empty and .. .. pops if the stack is not empty (never climb above root).

func SimplifyPath(path string) string {
	stack := []string{}
	for _, p := range strings.Split(path, "/") {
		switch p {
		case "", ".":
		case "..":
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		default:
			stack = append(stack, p)
		}
	}
	return "/" + strings.Join(stack, "/")
}

Complexity: time O(n), extra space O(n).

L10. Queue

Definition: first-in, first-out. New work joins the back; the next job leaves the front. Variants: circular buffer, deque, priority queue.

Real-world use:

1. Queue using two stacks

Push onto in. Pop/peek from out. Transfer in → out only when out is empty, so older values stay in front.

Real-world use: a FIFO ticket line when you only have two stacks (or two undo lists) to work with.

Sequence: push 10,11,12, pop 10, then later push 14.

type MyQueue struct{ in, out []int }

func (q *MyQueue) Push(x int) { q.in = append(q.in, x) }

func (q *MyQueue) shift() {
	if len(q.out) > 0 {
		return
	}
	for len(q.in) > 0 {
		n := len(q.in)
		q.out = append(q.out, q.in[n-1])
		q.in = q.in[:n-1]
	}
}

func (q *MyQueue) Pop() int {
	q.shift()
	n := len(q.out)
	x := q.out[n-1]
	q.out = q.out[:n-1]
	return x
}

Complexity: push/pop/peek amortized time O(1), worst-case transfer O(n). Extra space O(n).

2. Binary tree level order

Tree 3 / 9 20 / 15 7 → [[3],[9,20],[15,7]]. Capture the current queue length before enqueueing children.

Real-world use: print an org chart floor by floor, or list everyone on each storey of a building.

func LevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	queue := []*TreeNode{root}
	var out [][]int
	for head := 0; head < len(queue); {
		size := len(queue) - head
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			node := queue[head]
			head++
			level = append(level, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		out = append(out, level)
	}
	return out
}

Complexity: time O(n), extra space O(w) for the queue plus O(n) for the output. w is the widest level.

3. Kth largest — size-k min-heap

Spoken example: second largest is 5 (array [3,2,1,5,6,4], k=2). The heap root is the kth largest.

Real-world use: the 2nd-highest score, or keep only the top-k bids without sorting the whole list.

func FindKthLargest(nums []int, k int) int {
	h := minIntHeap(append([]int(nil), nums[:k]...))
	heap.Init(&h)
	for _, n := range nums[k:] {
		if n > h[0] {
			heap.Pop(&h)
			heap.Push(&h, n)
		}
	}
	return h[0]
}

Complexity: time O(n log k), extra space O(k).

L11 & L13. Heap and Top-K

Definition: a complete binary tree stored in an array. In a min-heap the parent is never larger than its children, so the root is always the current minimum. Insert heap-ups; remove-root heap-downs.

Real-world use:

Index math: left 2*i+1, right 2*i+2, parent (i-1)/2.

1. Heap-up (insert) and heap-down (remove root)

Video insert: push 2 into a min-heap [1,3,6,5,9,8] and swap it toward the root until the parent is smaller.

Real-world use: a new support ticket bubbles up if it is more urgent; closing the top ticket lets the next one sink into place.

Video remove: move the last leaf to the root, then swap down with the smaller child.

func (h *IntMinHeap) Push(v int) {
	h.data = append(h.data, v)
	h.heapUp(len(h.data) - 1)
}

func (h *IntMinHeap) heapUp(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if h.data[i] >= h.data[parent] {
			return
		}
		h.data[i], h.data[parent] = h.data[parent], h.data[i]
		i = parent
	}
}

func (h *IntMinHeap) heapDown(i int) {
	n := len(h.data)
	for {
		left, right, best := 2*i+1, 2*i+2, i
		if left < n && h.data[left] < h.data[best] {
			best = left
		}
		if right < n && h.data[right] < h.data[best] {
			best = right
		}
		if best == i {
			return
		}
		h.data[i], h.data[best] = h.data[best], h.data[i]
		i = best
	}
}

Complexity: insert or remove-root time O(log n). Peek time O(1). Extra space O(n) for the array.

2. Heap sort

Build a max-heap, then swap the root to the end and heap-down the reduced prefix.

Real-world use: sort in place when you cannot spare a merge-sort buffer, such as a small embedded device.

func HeapSort(nums []int) {
	n := len(nums)
	for i := n/2 - 1; i >= 0; i-- {
		siftDownMax(nums, n, i)
	}
	for end := n - 1; end > 0; end-- {
		nums[0], nums[end] = nums[end], nums[0]
		siftDownMax(nums, end, 0)
	}
}

Complexity: time O(n log n), extra space O(1).

3. Top K frequent

[1,1,1,2,2,3], k=2 → {1,2}. Count frequencies, keep a min-heap of size k ordered by frequency.

Real-world use: top 2 error codes in a log, or the k most-played songs this week.

func TopKFrequent(nums []int, k int) []int { /* see solutions.go */ }

Complexity: time O(n + u log k), extra space O(u + k). u is the number of unique values.

4. Kth smallest in a sorted matrix

Video matrix [[1,5,9],[10,11,13],[12,13,15]]. Push every cell into a size-k max-heap. The root is the kth smallest. For k=8 the answer is 13.

Real-world use: the 8th-cheapest cell in a sorted price grid (rows and columns already increase).

func KthSmallestMatrix(matrix [][]int, k int) int {
	h := maxIntHeap{}
	for _, row := range matrix {
		for _, v := range row {
			heap.Push(&h, v)
			if h.Len() > k {
				heap.Pop(&h)
			}
		}
	}
	return h[0]
}

Complexity: time O(r c log k), extra space O(k). r and c are the matrix dimensions.

L12. K-way Merge

Definition: several sources are already sorted. A min-heap holds one “next” item from each source. Pop the global smallest, then push that source’s following item.

Real-world use:

1. Merge two sorted arrays

[1,2,3] and [2,4,5] → [1,2,2,3,4,5]. Two pointers, take the smaller head.

Real-world use: merge two sorted attendance lists or two sorted price feeds into one timeline.

func MergeTwoSorted(a, b []int) []int {
	out := make([]int, 0, len(a)+len(b))
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			out = append(out, a[i])
			i++
		} else {
			out = append(out, b[j])
			j++
		}
	}
	out = append(out, a[i:]...)
	out = append(out, b[j:]...)
	return out
}

Complexity: time O(n + m), extra space O(n + m) for the output.

2. Merge K sorted lists

Lists [1,4,5], [1,3,4], [2,6]. Min-heap of list heads. Pop the smallest, push its Next. Time O(N log k).

Real-world use: merge logs from k servers, or k sorted customer lists, without concatenating and re-sorting.

func MergeKLists(lists []*ListNode) *ListNode { /* see solutions.go */ }

Complexity: time O(N log k), extra space O(k) for the heap. N is the total number of nodes.

3. K pairs with smallest sums

nums1=[1,7,11], nums2=[2,4,6], k=3 → [1,2],[1,4],[1,6].

Real-world use: the k cheapest hotel + flight pairs when both price lists are already sorted.

Seed (i,0) for the first min(len(nums1),k) rows. Pop the smallest sum, then push (i, j+1).

func KSmallestPairs(nums1, nums2 []int, k int) [][]int {
	h := &pairHeap{}
	limit := len(nums1)
	if k < limit {
		limit = k
	}
	for i := 0; i < limit; i++ {
		heap.Push(h, pairItem{i: i, j: 0, sum: nums1[i] + nums2[0]})
	}
	var out [][]int
	for h.Len() > 0 && len(out) < k {
		cur := heap.Pop(h).(pairItem)
		out = append(out, []int{nums1[cur.i], nums2[cur.j]})
		if cur.j+1 < len(nums2) {
			heap.Push(h, pairItem{i: cur.i, j: cur.j + 1, sum: nums1[cur.i] + nums2[cur.j+1]})
		}
	}
	return out
}

Complexity: time O(k log min(len(nums1), k)), extra space O(min(len(nums1), k)) plus the output.