L1–L6 Linear Patterns

Each subsection is one part of the video: the idea, the dry run from the lesson, then the Go.

L1. Two Pointers

Definition: keep two indices over the same array or string. They can start at opposite ends and walk inward, or start together and move at different speeds. The goal is to replace a nested loop with one linear pass.

Real-world use:

1. Two Sum II — sorted array

numbers is nondecreasing. Return 1-based indices of a pair that sums to target.

Real-world use: two ranked players whose scores add to a prize target, or two invoice lines that must total a payment.

Dry run: [2,7,11,15], target 9.

leftrightsumaction
21517too big, right--
21113too big, right--
279found, indices 1,2
func TwoSumSorted(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		sum := numbers[left] + numbers[right]
		if sum == target {
			return []int{left + 1, right + 1}
		}
		if sum < target {
			left++
		} else {
			right--
		}
	}
	return nil
}

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

2. Remove Duplicates from Sorted Array

Write unique values into a compact prefix. Return the new length k. The caller only reads nums[:k].

Real-world use: compact a sorted photo-id list or a sorted log of user ids in place so the extra copies do not take another array.

Dry run: [0,0,1,1,1,2,2,3,3,4] → prefix [0,1,2,3,4], k=5.

write is the slot for the next unique value. read scans ahead. Copy only when nums[read] != nums[write-1].

func RemoveDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	write := 1
	for read := 1; read < len(nums); read++ {
		if nums[read] != nums[write-1] {
			nums[write] = nums[read]
			write++
		}
	}
	return write
}

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

3. Valid Palindrome

Skip punctuation and spaces. Compare lowercase letters and digits from both ends.

Real-world use: check a vanity plate, a product SKU, or a cleaned-up sentence after stripping punctuation.

func IsPalindrome(s string) bool {
	runes := []rune(s)
	left, right := 0, len(runes)-1
	for left < right {
		for left < right && !unicode.IsLetter(runes[left]) && !unicode.IsDigit(runes[left]) {
			left++
		}
		for left < right && !unicode.IsLetter(runes[right]) && !unicode.IsDigit(runes[right]) {
			right--
		}
		if unicode.ToLower(runes[left]) != unicode.ToLower(runes[right]) {
			return false
		}
		left++
		right--
	}
	return true
}

Complexity: time O(n), extra space O(n) for the []rune copy. A byte-index walk on ASCII is O(1) extra space.

4. Container With Most Water

Area is min(height[left], height[right]) * (right-left). The only move that can improve the area is to drop the shorter wall.

Real-world use: pick two walls of a tank so the water held between them is maximum, or two buildings that shade the largest plaza.

Dry run: [1,8,6,2,5,4,8,3,7] → max area 49 between indices 1 and 8 (min(8,7)*7).

func MaxArea(height []int) int {
	left, right, best := 0, len(height)-1, 0
	for left < right {
		h := height[left]
		if height[right] < h {
			h = height[right]
		}
		if area := h * (right - left); area > best {
			best = area
		}
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}
	return best
}

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

L2. Fast and Slow Pointers

Definition: two walkers share a path. Slow moves one step, fast moves two. If they ever stand on the same node, the path loops. Resetting one walker to the start finds where the loop begins. The same walk works on any “next state” function, not only linked lists.

Real-world use:

1. Linked List Cycle

Example: 3 → 2 → 0 → -4 and -4 points back to 2. Compare pointers, not values.

Real-world use: a job queue that accidentally points next-job back to an earlier job, or a circular redirect.

func HasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

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

2. Linked List Cycle II — entry node

After they meet, put one pointer back at head. Walk both one step at a time. They meet at the cycle start.

Real-world use: find the first repeated stop on a bus loop, or the first page where a wiki redirect cycle begins.

func DetectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow != fast {
			continue
		}
		slow = head
		for slow != fast {
			slow = slow.Next
			fast = fast.Next
		}
		return slow
	}
	return nil
}

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

3. Middle of the Linked List

When fast hits the end, slow is in the middle. Even length returns the second middle.

Real-world use: split a playlist or a print queue in half without counting the items first.

func MiddleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

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

4. Happy Number

next(n) is the sum of squared digits. 19 → 82 → 68 → 100 → 1 is happy. 2 → 4 → … → 4 is a cycle.

Real-world use: any process that maps a state to the next state — detect whether it finishes or loops (retry backoff, checksum toy problems).

func IsHappy(n int) bool {
	slow, fast := n, nextHappy(n)
	for fast != 1 && slow != fast {
		slow = nextHappy(slow)
		fast = nextHappy(nextHappy(fast))
	}
	return fast == 1
}

func nextHappy(n int) int {
	sum := 0
	for n > 0 {
		d := n % 10
		sum += d * d
		n /= 10
	}
	return sum
}

Complexity: time O(log n) per nextHappy step and O(1) states before a cycle, extra space O(1).

L3. Sliding Window

Definition: a window is a contiguous slice of an array or string. Expand the right edge to include a new item, shrink the left edge when the window becomes invalid. Update a running sum or frequency instead of rescanning.

Real-world use:

1. Maximum sum of a distinct length-k window (fixed)

Example: [1,5,4,2,9,9,9], k=3.

Real-world use: best 3-day sales streak where no SKU repeats, or a checkout that allows only k distinct items.

windowdistinct?sum
1,5,4yes10
5,4,2yes11
4,2,9yes15
2,9,9noignore
9,9,9noignore

Answer 15. Keep a frequency map; a window is valid only when len(freq) == k.

func MaxSumDistinctK(nums []int, k int) int64 {
	freq := map[int]int{}
	var sum, best int64
	for i, v := range nums {
		sum += int64(v)
		freq[v]++
		if i >= k {
			left := nums[i-k]
			sum -= int64(left)
			freq[left]--
			if freq[left] == 0 {
				delete(freq, left)
			}
		}
		if i >= k-1 && len(freq) == k && sum > best {
			best = sum
		}
	}
	return best
}

Complexity: time O(n), extra space O(k) for the values inside one window.

2. Longest substring without repeating characters (variable)

"abcabcbb" → 3 ("abc"). If a character repeats inside the window, jump left past its previous index.

Real-world use: longest password fragment or chat token with no repeated character; unique-character coupon codes.

func LengthOfLongestSubstring(s string) int {
	last := map[rune]int{}
	left, best, i := 0, 0, 0
	for _, ch := range s {
		if prev, ok := last[ch]; ok && prev >= left {
			left = prev + 1
		}
		last[ch] = i
		if i-left+1 > best {
			best = i - left + 1
		}
		i++
	}
	return best
}

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

3. Minimum size subarray sum (variable, shrink while valid)

Positive numbers. Target 7, [2,3,1,2,4,3] → length 2 from [4,3].

Real-world use: shortest streak of days whose sales hit a quota, or fewest consecutive parcels that fill a truck.

Expand right until sum >= target, then shrink left while that stays true.

func MinSubArrayLen(target int, nums []int) int {
	best, sum, left := len(nums)+1, 0, 0
	for right, value := range nums {
		sum += value
		for sum >= target {
			if right-left+1 < best {
				best = right - left + 1
			}
			sum -= nums[left]
			left++
		}
	}
	if best == len(nums)+1 {
		return 0
	}
	return best
}

This shrink loop is only correct for non-negative values.

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

L4. Prefix Sum

Definition: store running totals so any range sum is one subtraction: prefix[j] - prefix[i-1]. Pair the running total with a map of earlier prefixes to count or detect subarrays.

Real-world use:

1. Build the prefix and answer a range

[1,2,3,4,5,6] → [1,3,6,10,15,21]. Sum of indices 1..3 is 10 - 1 = 9.

Real-world use: a finance dashboard: “revenue from 3 March to 10 March” without adding every day again.

func PrefixSums(nums []int) []int {
	out := make([]int, len(nums))
	if len(nums) == 0 {
		return out
	}
	out[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		out[i] = out[i-1] + nums[i]
	}
	return out
}

func RangeSum(prefix []int, left, right int) int {
	if left == 0 {
		return prefix[right]
	}
	return prefix[right] - prefix[left-1]
}

Complexity: build in time O(n) and space O(n). Each range query is time O(1), extra space O(1).

2. Pivot index

[1,7,3,6,5,6]. Index 3 (6) has left sum 11 and right sum 11.

Real-world use: the hour when traffic (or load) on the left of a checkpoint equals the right.

func PivotIndex(nums []int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	left := 0
	for i, n := range nums {
		if left == total-left-n {
			return i
		}
		left += n
	}
	return -1
}

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

3. Subarray sum equals K

Seed {0:1}. Query freq[sum-k] before inserting the current prefix.

Real-world use: count bank-statement windows whose net is exactly a known amount k (refund, batch, or settlement).

[1,1,1], k=2 → 2. [1,2,3], k=3 → [1,2] and [3].

func SubarraySum(nums []int, k int) int {
	freq := map[int]int{0: 1}
	sum, count := 0, 0
	for _, value := range nums {
		sum += value
		count += freq[sum-k]
		freq[sum]++
	}
	return count
}

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

4. Continuous subarray sum

Need a subarray of length at least 2 whose sum is divisible by k. Store the earliest index of each remainder. [23,2,4,6,7], k=6 is true because [2,4] sums to 6.

Real-world use: find a stretch of transactions that can be packed into boxes of size k (sum divisible by the batch size).

func CheckSubarraySum(nums []int, k int) bool {
	seen := map[int]int{0: -1}
	sum := 0
	for i, n := range nums {
		sum += n
		rem := sum
		if k != 0 {
			rem = sum % k
			if rem < 0 {
				rem += k
			}
		}
		if prev, ok := seen[rem]; ok {
			if i-prev >= 2 {
				return true
			}
			continue
		}
		seen[rem] = i
	}
	return false
}

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

L5. Merge Intervals

Definition: each item is a [start, end] range. Sort by start, then merge or reject overlaps. Two ranges overlap when current.start <= last.end.

Real-world use:

1. Merge intervals

[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].

Real-world use: merge overlapping calendar busy-blocks or Wi-Fi maintenance windows into one range.

Unsorted [[1,4],[6,7],[3,5]] must be sorted first → [[1,5],[6,7]].

func MergeIntervals(intervals [][]int) [][]int {
	if len(intervals) == 0 {
		return nil
	}
	sorted := make([][]int, len(intervals))
	for i, in := range intervals {
		sorted[i] = append([]int(nil), in...)
	}
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][0] < sorted[j][0] })
	out := [][]int{sorted[0]}
	for _, cur := range sorted[1:] {
		last := out[len(out)-1]
		if cur[0] <= last[1] {
			if cur[1] > last[1] {
				last[1] = cur[1]
			}
			continue
		}
		out = append(out, cur)
	}
	return out
}

Complexity: time O(n log n) to sort, then O(n) to merge. Extra space O(n) for the output (and the copy if the caller’s slice must stay intact).

2. Insert interval

Input is already sorted and non-overlapping. Three phases: copy intervals before the new one, merge overlaps into it, copy the rest.

Real-world use: book a new meeting into an already-sorted calendar and absorb any overlap.

[[1,3],[6,9]] insert [2,5] → [[1,5],[6,9]].

func InsertInterval(intervals [][]int, newInterval []int) [][]int {
	out := [][]int{}
	i := 0
	for i < len(intervals) && intervals[i][1] < newInterval[0] {
		out = append(out, intervals[i])
		i++
	}
	for i < len(intervals) && intervals[i][0] <= newInterval[1] {
		if intervals[i][0] < newInterval[0] {
			newInterval[0] = intervals[i][0]
		}
		if intervals[i][1] > newInterval[1] {
			newInterval[1] = intervals[i][1]
		}
		i++
	}
	out = append(out, newInterval)
	return append(out, intervals[i:]...)
}

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

3. Meeting Rooms I

One person. [1,3] and [2,5] overlap → cannot attend both. Touching endpoints ([1,2] and [2,5]) are allowed.

Real-world use: can one interviewer attend every slot, or do two interviews collide?

func CanAttendMeetings(intervals [][]int) bool {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] < intervals[i-1][1] {
			return false
		}
	}
	return true
}

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

Meeting Rooms II is named in the video but not finished. The usual follow-up is a min-heap of end times: the heap size is the room count. Complexity: time O(n log n), extra space O(n).

Definition: repeatedly halve a sorted or monotonic search space. Compare the middle value, then keep the half that can still contain the answer. The same idea searches a numeric range: “is capacity mid enough?”

Real-world use:

[-1,0,3,5,9,12], target 9 → index 4.

Real-world use: jump to a word in a dictionary or a row in a sorted spreadsheet.

func BinarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

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

2. Search a 2D matrix

Each row is sorted and the next row starts after the previous row ends. Flatten mentally: index mid is matrix[mid/cols][mid%cols].

Real-world use: find a seat number in a cinema filled row by row, or a cell in a printed price table.

func SearchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	left, right := 0, rows*cols-1
	for left <= right {
		mid := left + (right-left)/2
		val := matrix[mid/cols][mid%cols]
		if val == target {
			return true
		}
		if val < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

Complexity: time O(log (rows × cols)), extra space O(1).

3. Search in rotated sorted array

[4,5,6,7,0,1,2], target 0. One half of [left,mid] is always sorted. Keep the half that can contain the target. Distinct values only.

Real-world use: a circular buffer or a playlist rotated so the oldest track is no longer first.

func SearchRotated(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else if nums[mid] < target && target <= nums[right] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

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

4. Capacity to ship packages within D days

Binary search the answer. Lower bound is the heaviest package. Upper bound is the total weight. Packages stay in order.

Real-world use: smallest truck capacity that still delivers every package in order within D days.

Weights [1..10], 5 days → capacity 15. [3,2,2,4,1,4], 3 days → 6.

func ShipWithinDays(weights []int, days int) int {
	low, high := 0, 0
	for _, w := range weights {
		if w > low {
			low = w
		}
		high += w
	}
	for low < high {
		mid := low + (high-low)/2
		if canShip(weights, days, mid) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

Feasibility: start a new day whenever load+w exceeds capacity. If you need more than days days, mid is too small.

Complexity: time O(n log S), extra space O(1). S is sum(weights) - max(weights).