LeetCode Algorithm Notes

General Problem-Solving Strategies Overview

What features to look for → which algorithm to use

How to Recognize DP

Universal Linked List Playbook

I. Arrays and Hash Tables

0001. Two Sum Easy

Problem: Given an array, find two numbers whose sum equals target and return their indices.

Core idea: As you traverse, record each visited value and its index in a hash table; for each nums[i], check whether target - nums[i] is already in the table.

1
func twoSum(nums []int, target int) []int {
2
    mp := map[int]int{}
3
    for i, val := range nums {
4
        if index, exist := mp[target-val]; exist {
5
            return []int{index, i} // found a pair
6
        }
7
        mp[val] = i // record current value
8
    }
9
    return []int{}
10
}

• Key insight: A hash table reduces the pairing lookup from O(n) to O(1), giving total O(n) complexity.
• Pitfall: Query before storing, to avoid nums[i] pairing with itself (e.g. target=6, nums=[3,...]).

Execution example: nums = [2,7,11,15], target = 9

• ⚠️ Common failure: Writing to the map before looking up, causing val == target-val to match itself (e.g. nums=[3,2,4], target=6 returns [0,0] instead of [1,2]). You must query before storing.

0013. Roman to Integer Easy

Problem: Convert a Roman numeral to an integer (IV=4, VI=6).

Core idea: While traversing, if the current value is less than the next value (e.g. I in IV), subtract the current value; otherwise add it.

1
func romanToInt(s string) int {
2
    ans := 0
3
    for i := range s {
4
        value := symbolValues[s[i]]
5
        if i < n-1 && value < symbolValues[s[i+1]] {
6
            ans -= value // smaller precedes larger → subtract (e.g. I in IV)
7
        } else {
8
            ans += value
9
        }
10
    }
11
    return ans
12
}

• Key insight: In Roman numerals, a smaller symbol before a larger one means subtraction (IV = 5 - 1 = 4).
• Pitfall: Only compare the relative order of two adjacent characters.

0041. First Missing Positive Hard

Problem: Find the smallest missing positive integer in an unsorted array in O(n) time and O(1) space.

Core idea: In-place hashing — place value v at index v-1. After traversing, the first position where nums[i] != i+1 is the answer.

1
for i := 0; i < n; i++ {
2
    for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
3
        nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] // swap into correct position
4
    }
5
}
6
// find the first one out of place
7
for i := 0; i < n; i++ {
8
    if nums[i] != i+1 { return i + 1 }
9
}
10
return n + 1

• Key insight: Use the array itself as a hash table, where value v maps to index v-1.
• Pitfall: The swap condition must be nums[i] != nums[nums[i]-1] (to avoid infinite loops on duplicates), not nums[i] != i+1.

Execution example: nums = [3,4,-1,1], the goal is to place value v at index v-1.

Scan result: nums[1] = -1 ≠ 2, return 2.

graph TD
  A["Traverse each position i"] --> B{"nums[i] in [1,n] and
nums[i] ≠ nums[nums[i]-1]?"}
  B -->|Yes| C["Swap nums[i] ↔ nums[nums[i]-1]"]
  C --> B
  B -->|No| D["i++"]
  D --> E{"i < n?"}
  E -->|Yes| B
  E -->|No| F["Scan for the first nums[i] ≠ i+1"]
  style C fill: #fff9c4, color: #1a1a1a
  style F fill: #c8e6c9, color: #1a1a1a

0049. Group Anagrams Medium

Problem: Group words that contain the same letters but in a different order.

Core idea: Sort each string and use it as the hash key; group strings with the same key together.

1
for _, str := range strs {
2
    arr := strings.Split(str, "")
3
    sort.Strings(arr)
4
    key := strings.Join(arr, "") // sorted string as key
5
    m[key] = append(m[key], str)
6
}

• Key insight: After sorting, anagrams become the same string, which is naturally suitable as a hash key.
• Pitfall: You can also use a character-count array (convert [26]int to a string) as the key, costing O(k) instead of O(k log k).

0128. Longest Consecutive Sequence Medium

Problem: Find the length of the longest consecutive sequence of numbers in an unsorted array in O(n).

Core idea: Put everything into a hash set, and only count forward starting from a “sequence start” (where num-1 is not in the set).

1
mp := map[int]bool{}
2
for _, v := range nums { mp[v] = true }
3
for key := range mp {
4
    if !mp[key-1] { // only count starting from the start
5
        count := 1
6
        for mp[key+1] { count++; key++ }
7
        res = max(res, count)
8
    }
9
}

• Key insight: Only count from sequence starts (where num-1 is absent), guaranteeing each number is visited at most twice.
• Pitfall: Counting from every number gives O(n²); you must skip non-starts.

Execution flow (nums = [100,4,200,1,3,2]):

Result = 4 (sequence [1,2,3,4]). We only count from 3 starts, skipping the other 3.

0136. Single Number Easy

Problem: Find the number that appears exactly once (all others appear twice) in O(n) time and O(1) space.

Core idea: XOR everything; paired values cancel to 0, and what remains is the answer.

1
single := 0
2
for _, num := range nums { single ^= num }
3
return single

• Key insight: XOR self-inverse: a ^ a = 0, a ^ 0 = a.
• Pitfall: The initial value must be 0.

0169. Majority Element Easy

Problem: Find the element that appears more than n/2 times in O(n) time and O(1) space.

Core idea: Boyer-Moore voting — a candidate plus a counter; increment on the same, decrement on different, and switch candidate when the count hits zero.

1
count := 0; maj := nums[0]
2
for i := 1; i < n; i++ {
3
    if count == 0 { maj = nums[i] }       // switch candidate
4
    if nums[i] == maj { count++ } else { count-- }
5
}

• Key insight: The majority element is over half, so it must be the last one standing after cancellation.
• Pitfall: When the count hits zero, switch candidate first, then compare.

0238. Product of Array Except Self Medium

Problem: Without using division, compute answer[i] = the product of all elements except nums[i] in O(n).

Core idea: Two passes — left to right to store the left cumulative product, right to left to multiply by the right cumulative product.

1
answer[0] = 1
2
for i := 1; i < n; i++ { answer[i] = answer[i-1] * nums[i-1] } // left cumulative
3
temp := 1
4
for i := n-1; i >= 0; i-- {
5
    answer[i] *= temp // multiply by right cumulative
6
    temp *= nums[i]   // update right cumulative
7
}

• Key insight: answer[i] = product of all on the left × product of all on the right, done in two passes.
• Pitfall: In the second (right-to-left) pass, temp starts at 1; update answer before updating temp.

0283. Move Zeroes Easy

Problem: Move all 0s in the array to the end, keeping the relative order of non-zero elements.

1
l := 0
2
for r := 0; r < len(nums); r++ {
3
    if nums[r] != 0 { nums[l], nums[r] = nums[r], nums[l]; l++ }
4
}

• Key insight: The slow pointer marks where the next non-zero element should go.

0560. Subarray Sum Equals K Medium

Problem: Count the number of contiguous subarrays whose sum equals k.

Core idea: Prefix sum + hash table. When at position j, the number of times pre[j] - k has appeared before equals the number of subarrays ending at j whose sum is k.

Why prefix sum: The sum of a contiguous subarray nums[i..j] = pre[j] - pre[i-1]. For it to equal k, we need pre[i-1] = pre[j] - k. So when at j, we just need to count how many prefix sums equal pre[j] - k appeared before.

1
m := map[int]int{0: 1}; pre := 0; count := 0
2
for _, num := range nums {
3
    pre += num
4
    count += m[pre-k] // how many prefix sums = pre-k appeared before
5
    m[pre]++          // record how many times the current prefix sum appears
6
}

Execution example (nums = [1,1,1], k = 2):

Step 2: pre=2, found 1 prefix sum of 0 (subarray nums[0..1]=[1,1]); Step 3: pre=3, found 1 prefix sum of 1 (subarray nums[1..2]=[1,1]). Total 2.

• Key insight: The difference of two prefix sums equals k, i.e. count how many previous prefix sums equal pre - k.
• Pitfall: Initialize m[0]=1 to handle subarrays that start from the beginning (when pre is exactly k, pre-k=0 must be found); the array contains negatives, so you cannot use a sliding window — you must use prefix sum + hash table.

0724. Find Pivot Index Easy

Problem: Find an index where the sum of the left side equals the sum of the right side.

1
for _, num := range nums { right += num }
2
for i, num := range nums {
3
    right -= num        // first subtract current element
4
    if left == right { return i }
5
    left += num         // then add it to the left
6
}

• Key insight: Get the right-side sum by subtracting from the total, no extra array needed.

1207. Unique Number of Occurrences Easy

Problem: Determine whether the occurrence counts of each number are all distinct.

1
mp := map[int]int{}
2
for _, v := range arr { mp[v]++ }      // first pass: count frequencies
3
mp2 := map[int]bool{}
4
for _, v := range mp {                  // second pass: check for duplicate frequencies
5
    if mp2[v] { return false }
6
    mp2[v] = true
7
}

1431. Kids With the Greatest Number of Candies Easy

Problem: Whether each kid can reach the maximum after receiving extra candies.

1
maxVal := candies[0]
2
for _, v := range candies { if v > maxVal { maxVal = v } }
3
for i, v := range candies { res[i] = v + extraCandies >= maxVal }

1679. Max Number of K-Pairs Medium

Problem: Remove pairs that sum to k each step; return the maximum number of operations.

1
cnt := map[int]int{}
2
for _, x := range nums {
3
    if cnt[k-x] > 0 { cnt[k-x]--; ans++ } // found a pair
4
    else { cnt[x]++ }
5
}

1732. Find the Highest Altitude Easy

Problem: gain[i] is the change in altitude from point i to i+1. Starting from altitude 0, return the highest altitude reached along the way.

1
h := 0
2
for _, g := range gain { h += g; ans = max(ans, h) }

2215. Find the Difference of Two Arrays Easy

Problem: Return two lists: elements in nums1 but not in nums2, and elements in nums2 but not in nums1 (deduplicated).

Core idea: Two hash sets, take the set difference of each from the other.

1
func findDifference(nums1 []int, nums2 []int) [][]int {
2
    m1 := make(map[int]bool)
3
    for _, num := range nums1 { m1[num] = true }  // nums1 → set
4
    m2 := make(map[int]bool)
5
    for _, num := range nums2 { m2[num] = true }  // nums2 → set
6
    ans := make([][]int, 2)
7
    for k := range m1 { if !m2[k] { ans[0] = append(ans[0], k) } }  // unique to nums1
8
    for k := range m2 { if !m1[k] { ans[1] = append(ans[1], k) } }  // unique to nums2
9
    return ans
10
}

• Key insight: Hash set O(1) lookup, naturally suited for set difference.
• Pitfall: Map keys auto-deduplicate, no extra handling needed.

2352. Equal Row and Column Pairs Medium

Problem: Number of pairs of rows and columns that are completely identical in an n×n matrix.

Core idea: Serialize rows into strings and store in a hash table; query columns for the number of matches.

1
func equalPairs(grid [][]int) int {
2
    mp := make(map[string]int)
3
    for i := 0; i < len(grid); i++ {        // serialize each row
4
        s := ""
5
        for j := 0; j < len(grid[0]); j++ { s += strconv.Itoa(grid[i][j]) + " " }
6
        mp[s]++
7
    }
8
    ans := 0
9
    for j := 0; j < len(grid[0]); j++ {     // query each column
10
        s := ""
11
        for i := 0; i < len(grid); i++ { s += strconv.Itoa(grid[i][j]) + " " }
12
        ans += mp[s]  // add the number of matching rows
13
    }
14
    return ans
15
}

• Key insight: Comparing rows and columns becomes string matching, with hash table O(1) lookup.
• Pitfall: Add a separator (e.g. space) between elements when serializing, to prevent [1,23] and [12,3] from mismatching.

3345. Minimum Divisible Digit Product I Easy

Problem: Find the smallest integer ≥ n whose digit product is divisible by t.

1
func smallestNumber(n int, t int) int {
2
    for {
3
        n1 := 1; num := n
4
        for num > 0 {
5
            n1 = num % 10 * n1   // multiply each digit
6
            num /= 10
7
            if n1 == 0 { break } // contains 0 → product is 0, definitely divisible
8
        }
9
        if n1 % t == 0 { return n }
10
        n++
11
    }
12
}

• Key insight: When a digit is 0, the product is 0 and the condition is satisfied directly; the data range is small so brute force enumeration works.

3731. Find Missing Elements Easy

Problem: Numbers missing from a range of consecutive integers, returned as a sorted list.

1
func findMissingElements(nums []int) []int {
2
    slices.Sort(nums)  // sort
3
    ans := []int{}
4
    for i := 0; i < len(nums)-1; i++ {
5
        for j := nums[i]; j != nums[i+1]-1; j++ {  // fill the missing gaps
6
            ans = append(ans, j+1)
7
        }
8
    }
9
    return ans
10
}

Execution example: nums = [1,4,2,5]

• Key insight: After sorting, check the gaps where adjacent elements differ by more than 1.

II. Two Pointers

0011. Container With Most Water Medium

Problem: Two vertical lines plus a base form a container; find the maximum capacity.

Core idea: Left and right pointers move inward from the two ends; the shorter side moves (because moving the taller side can never increase the area).

1
l, r := 0, len(height)-1
2
for l < r {
3
    if height[l] < height[r] {
4
        res = max(res, (r-l)*height[l]); l++
5
    } else {
6
        res = max(res, (r-l)*height[r]); r--
7
    }
8
}

• Key insight: Area = base × height; the base is shrinking, so only increasing the height can grow the area → move the shorter side.
• Pitfall: When both sides are equal, it doesn’t matter which moves.

graph LR
    A[Left and right pointers start at the two ends] --> B{Which side is shorter?}
    B -->|Left shorter| C[Compute area, move left pointer right]
    B -->|Right shorter| D[Compute area, move right pointer left]
    C --> E{l < r?}
    D --> E
    E -->|Yes| B
    E -->|No| F[Return max area]

0015. 3Sum Medium

Problem: Find all unique triplets that sum to 0.

Core idea: After sorting, fix one number and use two pointers to find the other two. Deduplicate: if the fixed number equals the previous one, skip it.

1
sort.Ints(nums)
2
for l := 0; l < n; l++ {
3
    if nums[l] > 0 { break }                    // min > 0 → no solution possible
4
    if l > 0 && nums[l] == nums[l-1] { continue } // deduplicate
5
    m, r := l+1, n-1
6
    for m < r {
7
        sum := nums[l] + nums[m] + nums[r]
8
        if sum == 0 {
9
            res = append(res, []int{nums[l], nums[m], nums[r]})
10
            m++; r--
11
            for m < r && nums[m] == nums[m-1] { m++ }   // deduplicate
12
            for m < r && nums[r] == nums[r+1] { r-- }   // deduplicate
13
        } else if sum > 0 { r-- } else { m++ }
14
    }
15
}

• Key insight: Sort + fix one + two pointers for the other two, turning the triple loop into O(n²).
• Pitfall: Three levels of deduplication (fixed number, left pointer, right pointer must all skip duplicates).

Execution flow (nums = [-1,0,1,2,-1,-4], sorted = [-4,-1,-1,0,1,2]):

Result = [[-1,-1,2], [-1,0,1]]

• ⚠️ Common failure: In the sum == 0 branch, mistakenly executing l++ (outer loop variable) instead of m++ (inner left pointer), causing valid solutions to be skipped.

0027. Remove Element Easy

Problem: Remove all elements with value val in place.

1
cur, lst := 0, len(nums)-1
2
for cur <= lst {
3
    if nums[lst] == val { lst-- }
4
    else if nums[cur] == val { nums[cur] = nums[lst]; lst-- }
5
    else { cur++ }
6
}
7
return lst + 1

• Key insight: Two-end pointers; find val on the left, find non-val on the right, swap them.
• Why cur does not advance after swapping: The swap is nums[cur] = nums[lst], and the element coming from the right might also be val (e.g. nums=[3,2,2,3], val=3). If cur++ is done here, this swapped val stays at the front and is not removed. So in the swap branch we only do lst--, keeping cur in place to re-check the newly arrived element next round; only the “else branch” where nums[cur] != val does cur++.
• ⚠️ Common failure: When lst <= 0 (array length 1) directly returning 0, but if nums[0] != val it should return 1; or wrongly doing cur++ after a swap, leaving the swapped val behind.

0042. Trapping Rain Water Hard

Problem: Given an array of bar heights, compute how much rainwater can be trapped.

Core idea: Two pointers + left/right maximums. The shorter side determines the water level at that position.

Key intuition (why the shorter side determines the water level): The rainwater at position i = min(left tallest wall, right tallest wall) - height[i] (barrel principle — water overflows from the shorter side). The trick of the two pointers is: when height[l] < height[r], there must be a wall ≥ height[r] to the right of position l (at least height[r] itself), so l’s “right max” is necessarily ≥ height[r] > height[l] ≥ maxLeft, meaning the water at l depends only on maxLeft, regardless of how tall the right side actually is! Similarly, when height[l] ≥ height[r], the water at r depends only on maxRight. That’s why the shorter side moves first.

1
l, r := 0, len(height)-1
2
maxLeft, maxRight := 0, 0
3
for l < r {
4
    maxLeft = max(maxLeft, height[l])   // first update the left max at current position
5
    maxRight = max(maxRight, height[r]) // first update the right max at current position
6
    if height[l] < height[r] {
7
        res += maxLeft - height[l]; l++   // left is shorter → water level decided by maxLeft
8
    } else {
9
        res += maxRight - height[r]; r--  // right is shorter/equal → water level decided by maxRight
10
    }
11
}

• Key insight: Rainwater at each position = min(left max, right max) - own height; two pointers let the shorter side move first.
• Pitfall: Update max first, then compute rain (use the latest maxLeft/maxRight, including current height[l]/height[r]).

Bars and rainwater visualization (height = [0,1,0,2,1,0,1,3,2,1,2,1]):

Black = bar height, blue = trapped rainwater. Total rainwater = 6.

Execution example (two-pointer process):

graph TD
    S["Init: l=0, r=n-1, maxL=0, maxR=0"] --> C{"height[l] < height[r] ?"}
    C -->|"Yes: left is shorter
right must have a wall ≥ height[r]
→ right max > left max"| L["Water at l depends only on maxL
res += maxL - height[l]
l++, update maxL"]
    C -->|"No: right shorter or equal
left must have a wall ≥ height[l]
→ left max ≥ right max"| R["Water at r depends only on maxR
res += maxR - height[r]
r--, update maxR"]
    L --> C
    R --> C
    C -->|"End when l >= r"| E["Return total rainwater = 6"]
    style S fill: #e3f2fd, color: #1a1a1a
    style E fill: #c8e6c9, color: #1a1a1a

0088. Merge Sorted Array Easy

Problem: Merge nums2 into nums1 (nums1 has empty space at the end).

Core idea: Fill from the back; place the larger one at the back.

1
// p1 points to the end of nums1's valid elements, p2 points to the end of nums2, tail points to the write position
2
for p1, p2, tail := m-1, n-1, m+n-1; p1 >= 0 || p2 >= 0; tail-- {
3
    if p1 == -1 {                       // nums1 exhausted, can only fill nums2
4
        nums1[tail] = nums2[p2]; p2--
5
    } else if p2 == -1 {                // nums2 exhausted, can only fill nums1
6
        nums1[tail] = nums1[p1]; p1--
7
    } else if nums1[p1] > nums2[p2] {   // both have elements, fill the larger (back-to-front keeps order)
8
        nums1[tail] = nums1[p1]; p1--
9
    } else {
10
        nums1[tail] = nums2[p2]; p2--
11
    }
12
}

• Key insight: Filling from the back avoids overwriting nums1 elements not yet processed.

0189. Rotate Array Medium

Problem: Rotate the array right by k positions (move the last k elements to the front), in place.

Core idea: Three reversals — reverse the whole array → reverse the first k → reverse the last n-k.

How to think of reversals: Rotating right by k = moving the last k elements as a block to the front. Reversal has a “symmetric” property: first reverse the whole array, which flips the last k elements to the front (but in reverse order); then reverse the first k and the last n-k back into correct order, yielding the right result. Three reversals neatly avoid an extra array.

1
k %= len(nums)      // prevent k > n; rotating by k equals rotating by k%n
2
reverse(nums)       // ① reverse the whole array: the last k are flipped to the front (in reverse order)
3
reverse(nums[:k])   // ② reverse the first k back into order
4
reverse(nums[k:])   // ③ reverse the last n-k back into order

Example (nums = [1,2,3,4,5,6,7], k = 3):

The last 3 (5,6,7) successfully moved to the front.

• Key insight: reverse(nums) + reverse(nums[:k]) + reverse(nums[k:]) is equivalent to rotating right by k.

0345. Reverse Vowels of a String Easy

Problem: Reverse all vowels in the string (aeiou, case-insensitive).

1
l, r := 0, len(s)-1
2
b := []byte(s)
3
for l < r {
4
    for l < r && !vowels[b[l]] { l++ }
5
    for l < r && !vowels[b[r]] { r-- }
6
    b[l], b[r] = b[r], b[l]; l++; r--
7
}

0392. Is Subsequence Easy

Problem: Determine whether s is a subsequence of t.

1
i, j := 0, 0
2
for j < len(t) {
3
    if i < len(s) && s[i] == t[j] { i++ }
4
    j++
5
    if i == len(s) { return true }
6
}

• Key insight: t’s pointer only advances, never moves back.

0763. Partition Labels Medium

Problem: Partition the string so that each letter appears in at most one segment.

Core idea: First record the last occurrence of each letter; while traversing, keep extending the right boundary to “the final occurrence of every letter in the current segment”; once you reach the segment’s right boundary, that letter won’t appear again, so you can cut.

1
mp := map[rune]int{}
2
for idx, ch := range s { mp[ch] = idx }  // ① record the last index of each letter
3
start, end := 0, 0
4
for idx, ch := range s {
5
    if mp[ch] > end { end = mp[ch] }      // ② extend right boundary: if this letter goes further, the segment must reach there
6
    if idx == end {                        // ③ reached boundary: letters in segment won't appear again, can cut
7
        ans = append(ans, idx+1-start)    //    length = right boundary - left boundary + 1
8
        start = idx + 1                    //    next segment starts at left boundary + 1
9
    }
10
}

• Key insight: Segment right boundary = max of the “final occurrence positions” of all letters in the segment; cut when reaching the boundary, ensuring each letter lands in only one segment.
• Why it works: As long as the right boundary keeps extending, the current segment hasn’t “closed up” yet — its letters have more to come, so we must continue; once idx catches up to end, this segment is self-consistent and cutting it off doesn’t affect what follows.

1768. Merge Strings Alternately Easy

Problem: Merge word1 and word2 alternately, appending the remainder to the end.

1
i, j := 0, 0
2
for i < m && j < n { sb.WriteByte(word1[i]); sb.WriteByte(word2[j]); i++; j++ }
3
if m > n { sb.WriteString(word1[i:]) } else if n > m { sb.WriteString(word2[j:]) }

III. Sliding Window

General template: Right pointer expands window → check window validity → left pointer shrinks window → update answer.

graph LR
  A["right expands window"] --> B{"Window invalid?"}
  B -->|Yes| C["left shrinks window"]
  C --> B
  B -->|No| D["Update answer"]
  D --> A

0003. Longest Substring Without Repeating Characters Medium

Problem: Find the length of the longest substring without repeating characters.

Core idea: Sliding window + hash table recording character positions. When a duplicate character is encountered, jump the left pointer to just after the duplicate.

1
mp := map[byte]int{}; l, res := 0, 0
2
for r := 0; r < len(s); r++ {
3
    if idx, exists := mp[s[r]]; exists && idx >= l {
4
        l = idx + 1  // jump left pointer just after the duplicate
5
    }
6
    mp[s[r]] = r
7
    res = max(res, r-l+1)
8
}

• Key insight: The left pointer doesn’t step one by one, but jumps directly to just after the duplicate character.
• Pitfall: Check idx >= l, because the position in the hash table may be before the left pointer (no longer in the window).
• ⚠️ Common failure: Writing res = max(res, r-1-l) instead of r-l+1 when updating the result, causing an off-by-one that counts 1 short.

0076. Minimum Window Substring Hard

Problem: Find the shortest substring in s that contains all characters of t (with sufficient counts), and return it.

Core idea: Sliding window + a count variable tracking how many character types still need matching.

1
tmap := map[byte]int{}            // how many of each char in t are needed
2
for _, ch := range t { tmap[ch]++ }
3
count := len(tmap)               // number of character types still to satisfy
4
smap := map[byte]int{}
5
l, ansL, ansR := 0, 0, len(s)
6
for r := 0; r < len(s); r++ {
7
    smap[s[r]]++
8
    if smap[s[r]] == tmap[s[r]] { count-- }   // this char just met its quota → one fewer to satisfy
9
    for count == 0 {                          // window valid, shrink as much as possible
10
        if r-l < ansR-ansL { ansL, ansR = l, r } // update shortest
11
        smap[s[l]]--
12
        if smap[s[l]] < tmap[s[l]] { count++ }  // after shrinking, this char is insufficient → one more to satisfy
13
        l++
14
    }
15
}

Example (s = “ADOBECODEBANC”, t = “ABC”): count initially = 3 (A/B/C types). When right expands to r=5 (“ADOBEC”), A, B, C are all met → count=0, window valid; shrink left to l=3 (“BEC”) still valid and shorter; shrink further to l=4 (“EC”) missing A → count=1, stop shrinking, keep expanding right. Final shortest = “BANC”.

• Key insight: Use a single count variable (instead of scanning the hash table every round) to check validity in O(1).
• Pitfall: When shrinking, the condition for “breaking validity” is smap[s[l]] < tmap[s[l]] (count goes from enough to not enough), not ==.

0239. Sliding Window Maximum Hard

Problem: For a sliding window of size k, return the maximum within each window in order.

Core idea: Monotonically decreasing deque storing indices; the front is always the current window’s maximum.

Why a monotonic deque (key intuition): When the window moves right, if an old element is smaller than the new element val, it can never be the maximum again — because val is larger and further right (stays in the window longer). So whenever a new element arrives, pop all old elements smaller than it from the back, keeping the deque monotonically decreasing from front to back. The front is popped once it slides out of the window’s left boundary.

1
q := []int{} // store indices (not values! makes expiry easy to check)
2
for i, val := range nums {
3
    // ① pop all old indices ≤ current value from the back: they can never be max again
4
    for len(q) > 0 && nums[q[len(q)-1]] <= val { q = q[:len(q)-1] }
5
    q = append(q, i)                 // ② current index enters the back
6
    if q[0] < i-k+1 { q = q[1:] }    // ③ front index has slid out of window, pop it
7
    if i >= k-1 { ans = append(ans, nums[q[0]]) } // ④ window full, front is the max
8
}

• Key insight: Monotonically decreasing deque — old elements smaller than the new one are permanently eliminated, front is always the window maximum.
• Pitfall: Store indices in the deque, not values, so q[0] < i-k+1 can check whether it slid out of the window.

Execution flow (nums = [1,3,-1,-3,5,3,6,7], k = 3):

Output = [3,3,5,5,6,7], each time popping old elements smaller than the new one to keep the deque monotonically decreasing.

0438. Find All Anagrams in a String Medium

Problem: An anagram = strings with the exact same characters and counts, just arranged differently (e.g. “abc” and “cba”). Return the starting indices of all substrings in s of length len(p) that are anagrams of p.

Core idea: Fixed-length window + difference counting. Use cnt[ch] = (count of char in window) - (count of char in p), and diff = number of char types where cnt is non-zero. diff == 0 means the window matches p character-for-character, i.e. it’s an anagram.

1
cnt := [26]int{}; diff := 0
2
// ① initialize: compare the first len(p) chars window of s with p
3
for i := 0; i < len(p); i++ {
4
    cnt[s[i]-'a']++   // one more in window
5
    cnt[p[i]-'a']--   // one more in p (subtract to get the difference)
6
}
7
for i := 0; i < 26; i++ { if cnt[i] != 0 { diff++ } }
8
if diff == 0 { res = append(res, 0) }
9
// ② slide window right: left out, right in, incrementally update cnt and diff
10
for i := len(p); i < len(s); i++ {
11
    out := s[i-len(p)] - 'a' // character sliding out
12
    cnt[out]--
13
    if cnt[out] == 0 { diff-- } else if cnt[out] == -1 { diff++ } // from unbalanced → balanced / from balanced → more lacking
14
    in := s[i] - 'a'          // character sliding in
15
    cnt[in]++
16
    if cnt[in] == 0 { diff-- } else if cnt[in] == 1 { diff++ }    // from more → balanced / from balanced → more
17
    if diff == 0 { res = append(res, i-len(p)+1) }               // balanced means anagram
18
}

• Key insight: Use a difference array + diff (count of non-zero entries) to avoid comparing 26 letters every slide (O(1) check).
• ⚠️ Common failure: Wrong diff update logic — diff should only change when cnt crosses the “0 ↔ non-zero” boundary; going from 1→2 or -2→-1 doesn’t count (already unbalanced, the change in quantity doesn’t change balance).

0643. Maximum Average Subarray I Easy

Problem: Find the maximum average of a contiguous subarray of length k.

1
for i := 0; i < k; i++ { sum += nums[i] }
2
ans := float64(sum) / float64(k)
3
for i := k; i < len(nums); i++ { sum += nums[i] - nums[i-k]; ans = max(ans, float64(sum)/float64(k)) }

1004. Max Consecutive Ones III Medium

Problem: Flip at most k 0s to 1s in the array, and find the length of the longest consecutive-1 subarray achievable. Equivalent to: find the longest window containing at most k 0s.

Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 → flip any 2 of the 3 middle 0s to 1, connecting to the right-side 1s, giving longest consecutive-1 length = 6 (indices 0~5 all 1).

Core idea: Sliding window; valid while the number of 0s in the window ≤ k; shrink the left boundary once 0s exceed k.

1
for right := 0; right < n; right++ {
2
    if nums[right] == 0 { zeroCnt++ }
3
    for zeroCnt > k { if nums[left] == 0 { zeroCnt-- }; left++ }
4
    maxLen = max(maxLen, right-left+1)
5
}

• Key insight: “Flip at most k 0s” = “at most k 0s in the window”.

1456. Maximum Number of Vowels in a Substring of Given Length Medium

1
for i := 0; i < k; i++ { if vowels[s[i]] { count++ } }
2
ans := count
3
for i := k; i < len(s); i++ {
4
    if vowels[s[i-k]] { count-- }
5
    if vowels[s[i]] { count++ }
6
    ans = max(ans, count)
7
}

• ⚠️ Common failure: Loop condition written as i < len(s)-k instead of i <= len(s)-k, missing the last window. E.g. s="aeiou", k=5 would skip the loop and return 0.

1493. Longest Subarray of 1’s After Deleting One Element Medium

Core idea: At most 1 zero in the window; the answer is window length - 1 (must delete one element).

1
for right := 0; right < n; right++ {
2
    if nums[right] == 0 { zeroCnt++ }
3
    for zeroCnt > 1 { if nums[left] == 0 { zeroCnt-- }; left++ }
4
    maxLen = max(maxLen, right-left)  // note right-left not +1
5
}

• Key insight: Since you must delete one element, the answer is right - left, not right - left + 1.

IV. Binary Search

General template: left + (right-left)/2 to avoid overflow, loop condition left <= right.

When can you use binary search (prerequisite: monotonicity): The fundamental prerequisite for binary search to “halve the search space each time” is that the search space is monotonic — there is a critical point splitting the interval into two segments (one satisfying a property, the other not, either left-satisfies/right-doesn’t or vice versa).

• An array itself being ascending is the most intuitive monotonicity (e.g. 0035, 0074).
• The more general “binary search on answer” requires the objective function to be monotonic in the variable, e.g. in 0875 the larger the speed the less time it takes (total(k) decreases with k), so “whether it can finish within h hours” has a clear “left illegal / right legal” boundary.
• If the data itself is unordered and no monotonic relationship with the index can be found, binary search has no basis and will miss solutions — don’t force it in such cases.

Why sometimes use left < right:

• left <= right (closed-interval template): [left, right] is always a valid closed interval, mid may itself be the answer, return on hit; when the loop exits left > right (they cross). Suitable for “find the exact index equal to target / the element definitely exists” (e.g. ordinary search besides 0033, 0287).
• left < right (boundary / lower-bound template): Loop exits only when left == right, at which point left (i.e. right) is the answer, no extra check needed. Commonly used for “find the first position satisfying a property” — e.g. the left boundary leftBound in 0034, the insertion position in 0035. Note that in this style mid takes left + (right-left)/2 (floor division), and updates usually right = mid (keep mid as a candidate), otherwise left = mid + 1, to avoid infinite loops.
• One-line memory: Use <= to “hit a specific value”; use < to “approach a boundary / lower bound”.

0033. Search in Rotated Sorted Array Medium

Problem: Find target in a rotated sorted array.

Core idea: In binary search, determine which half is sorted, then check whether target is in the sorted half.

1
left, right := 0, n-1
2
for left <= right {
3
    mid := left + (right-left)/2
4
    if nums[mid] == target { return mid }
5
    if nums[mid] >= nums[left] {              // left half sorted
6
        if target >= nums[left] && target < nums[mid] { right = mid - 1 }
7
        else { left = mid + 1 }
8
    } else {                                   // right half sorted
9
        if target > nums[mid] && target <= nums[right] { left = mid + 1 }
10
        else { right = mid - 1 }
11
    }
12
}

• Key insight: A rotated array always has one sorted half; check whether target is in the sorted half.
• Pitfall: Use >= in nums[mid] >= nums[left] because mid may equal left.

Execution flow (nums = [4,5,6,7,0,1,2], target = 0):

graph TD
    A["binary search mid"] --> B{"nums[mid] == target?"}
    B -->|Yes| C["return mid"]
    B -->|No| D{"nums[mid] >= nums[left]?"}
    D -->|Yes| E["left half sorted"]
    D -->|No| F["right half sorted"]
    E --> G{"target in left half?"}
    F --> H{"target in right half?"}
    G -->|Yes| I["right = mid-1"]
    G -->|No| J["left = mid+1"]
    H -->|Yes| J
    H -->|No| I

0034. Find First and Last Position of Element in Sorted Array Medium

Problem: In an ascending array, find the start and end indices (both inclusive) of target; if absent, return [-1,-1].

Core idea: Two binary searches — find the position of “first ≥ target” (left boundary) and “first > target” (right boundary = that position − 1).

How to maintain the boundary (binary search template): Use the standard “left = first ≥ target” form: when nums[mid] < target shrink the left half (left = mid+1), otherwise shrink the right half (right = mid-1). When done, left points to the first index ≥ target.

1
// left boundary = position of first >= target
2
leftBound := func() int {
3
    l, r := 0, len(nums)-1
4
    for l <= r {
5
        mid := l + (r-l)/2
6
        if nums[mid] < target { l = mid+1 } else { r = mid-1 }
7
    }
8
    return l   // first >= target
9
}
10
// right boundary = position of first > target - 1 = position of first >= target+1 - 1
11
rightBound := func() int {
12
    l, r := 0, len(nums)-1
13
    for l <= r {
14
        mid := l + (r-l)/2
15
        if nums[mid] <= target { l = mid+1 } else { r = mid-1 } // note <=
16
    }
17
    return l - 1
18
}

Example (nums = [5,7,7,8,8,10], target = 8):

• Left boundary: first ≥ 8 → index 3; right boundary: first > 8 (i.e. first ≥ 9) → index 5, then −1 = 4. Result [3,4] ✓

• Key insight: Sorted + O(log n) → must use binary search; one search for each boundary, avoiding linear scan after finding that degrades to O(n).

• Pitfall: The two searches use different conditions — left boundary uses nums[mid] < target, right boundary uses nums[mid] <= target.

0035. Search Insert Position Easy

Problem: Find target in a sorted array; return its index if found, otherwise return where it should be inserted.

1
for left <= right {
2
    mid := left + (right-left)/2
3
    if nums[mid] == target { return mid }
4
    else if nums[mid] > target { right = mid - 1 }
5
    else { left = mid + 1 }
6
}
7
return left // left is the insertion position

• Key insight: At the end of binary search, left points exactly to the insertion position.

0074. Search a 2D Matrix Medium

Problem: Each row of the matrix is ascending left to right, and the first element of each row is greater than the last element of the previous row (so the whole thing can be seen as one ascending 1D array). Determine whether target is in it.

Core idea: Two binary searches — treat the matrix as a 1D ascending array, first binary search for “the row target might be in”, then binary search within that row for target.

1
// map (r,c) to 1D index idx = r*cols + c, binary search the whole
2
m, n := len(matrix), len(matrix[0])
3
l, r := 0, m*n-1
4
for l <= r {
5
    mid := l + (r-l)/2
6
    val := matrix[mid/n][mid%n]   // restore 2D coordinates from 1D index
7
    if val == target { return true }
8
    else if val < target { l = mid+1 } else { r = mid-1 }
9
}
10
return false

Why it can be treated as 1D: Because of the “each row’s first > previous row’s last” condition, the matrix’s lexicographic order is exactly the same as its size order when flattened to 1D, so searching the whole is equivalent to finding the row first, then the column.

• Key insight: When the matrix satisfies the condition it is equivalent to a 1D ascending array; binary searching the whole is cleaner.
• Pitfall: Use mid/n (row) and mid%n (column) to restore coordinates; watch for out-of-bounds.

0153. Find Minimum in Rotated Sorted Array Medium

Problem: An originally ascending array is rotated at some “pivot” (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Find the minimum element. This version guarantees no duplicate elements in the array.

Core idea: After rotation, the array is split by the minimum into two segments — the left half is all >= the original first element, the right half is all < the original first element. When binary searching, comparing nums[mid] with nums[left] tells you which segment mid falls in:

• nums[mid] >= nums[left] → mid is in the left (sorted) segment, so the minimum must be to the right of mid (inclusive of mid+1), so left = mid + 1, and treat nums[left] as a candidate minimum.
• nums[mid] < nums[left] → mid is in the right (unsorted) segment, so the minimum must be to the left of mid (possibly mid itself), so right = mid - 1, and treat nums[mid] as a candidate minimum.

1
if nums[mid] >= nums[left] { left = mid + 1; ans = min(ans, nums[left]) }
2
else { right = mid - 1; ans = nums[mid] }

Example nums = [3,4,5,1,2] (first element nums[0]=3, minimum should be 1):

Return ans = 1.

• Key insight: A rotated array’s “sortedness” is broken at only one place (the pivot); binary search cuts away the sorted half each time.
• Pitfall: This version has no duplicates, so comparing with nums[left] works; if the array has duplicates (problem 154) you must compare with nums[right] instead, or it will misjudge.

0240. Search a 2D Matrix II Medium

Problem: Find target in an m×n matrix where each row increases left to right and each column increases top to bottom.

Core idea: Start from the top-right corner; if too big, move left; if too small, move down.

1
r, c := 0, len(matrix[0])-1
2
for r < len(matrix) && c >= 0 {
3
    if matrix[r][c] == target { return true }
4
    if matrix[r][c] > target { c-- } else { r++ }
5
}

• Key insight: The top-right corner has the BST property “smaller on the left, larger below”, eliminating a row or column each step.
• Pitfall: Can’t start from the top-left, because both right and down are larger so direction is ambiguous.
• ⚠️ Common failure: When binary searching row by row, conditions written as target < matrix[r][0] and target > matrix[r][0]; when target == matrix[r][0] neither is satisfied, so the row is skipped. Should use >=.

0287. Find the Duplicate Number Medium

Problem: Given an array nums of length n+1, elements range over [1, n] (i.e. the value range is one less than the index range). Exactly one number repeats (possibly multiple times). Find the duplicate. Constraints: may not modify the original array, use only O(1) extra space, and run faster than O(n²).

What is cycle detection (Floyd’s Tortoise and Hare): Treat the array as a “directed graph”: i → nums[i] means an edge from index i to the index where the value nums[i] lives. Since values range over 1..n and indices are 0..n, starting from 0 you must enter some cycle — and that cycle’s entrance is exactly the repeating number.

Why must there be a cycle, and why is the entrance = the duplicate?

• Since the value range is only 1..n, every value except 0 maps to a valid index, so the path can’t diverge forever and must loop.
• The repeating number dupe is pointed to by at least two different indices (because two positions hold dupe), so the node dupe has two incoming edges → it’s the cycle entrance.

Cycle detection has two phases:

1. Find the meeting point (slow steps 1, fast steps 2): slow = nums[slow], fast = nums[nums[fast]]. If a cycle exists, they must meet at some point inside it.
2. Find the cycle entrance: one pointer starts from the start head=0, slow starts from the meeting point, both step 1 each time; where they meet again is the cycle entrance = the duplicate.

Mathematical intuition: Let distance from “start to entrance” be a, distance from “entrance to meeting point” be b, cycle length be c. At meeting, slow walked a+b, fast walked 2(a+b)=a+b+k·c, giving a+b=k·c. This means walking a more steps from the meeting point lands exactly back at the entrance (k full loops); walking a steps from the start also reaches the entrance, so the two pointers must meet at the entrance.

1
slow, fast := 0, 0
2
for { slow = nums[slow]; fast = nums[nums[fast]]; if slow == fast { break } }
3
head := 0
4
for slow != head { slow = nums[slow]; head = nums[head] }
5
return slow

Example nums = [1,3,4,2,2] (duplicate is 2):

Pointer path: 0 → 1 → 3 → 2 → 4 → 2 → 4 → … (2→4→2 forms a cycle, entrance is node 2)

• Phase 1: slow=0,fast=0 → slow=1,fast=3 → slow=3,fast=4 → slow=2,fast=4 → slow=4,fast=4 (meet at node 4)
• Phase 2: head=0,slow=4 → head=1,slow=2 → head=3,slow=4 → head=2,slow=2 (meet at node 2)

Return 2, the duplicate.

• Key insight: Treat the “value” as a “pointer to an index”; the duplicate value = the cycle entrance.
• Pitfall: Cannot sort the array or use a hash table (violates “don’t modify array / O(1) space”); cycle detection is the only approach satisfying both constraints.

0374. Guess Number Higher or Lower Easy

Problem: Guess a number between 1 and n, call guess() to get a hint (-1 too small / 0 correct / 1 too big), return the guessed number.

1
for {
2
    mid := left + (right-left)/2
3
    res := guess(mid)
4
    if res == 0 { return mid }
5
    else if res == 1 { left = mid + 1 } else { right = mid - 1 }
6
}

0875. Koko Eating Bananas Medium

Problem: There are n piles of bananas, piles[i] is the count in the i-th pile. Koko must finish all bananas within h hours; each hour she picks one pile and eats k bananas (if fewer than k remain, she finishes that pile), and cannot eat from another pile that hour. Find the minimum speed k at which she can finish.

Why binary search works: The key property is “the larger the speed, the less total time” — total time total(k) is a monotonically decreasing function of k. This gives two conclusions:

• There is a threshold K: when k ≥ K, total(k) ≤ h (can finish); when k < K, total(k) > h (can’t finish).
• Since the boundary is monotonically clear (“everything left of the answer is illegal, everything right is legal”), we can binary search directly toward this critical point K instead of trying from 1.

Search range: k is at least 1, at most maxPiles (slower than that still works, but no need to be larger).

1
left, right := 1, maxPile // speed range [1, max pile]
2
for left <= right {
3
    mid := left + (right-left)/2
4
    total := 0
5
    for _, p := range piles { total += (p + mid - 1) / mid } // round up
6
    if total <= h { ans = mid; right = mid - 1 } else { left = mid + 1 }
7
}

Example piles = [3,6,7,11], h = 8:

Minimum legal speed is 4.

• Key insight: Banana-eating time decreases monotonically with speed → the answer has a “left illegal / right legal” boundary → binary search on answer.
• Pitfall: Time per pile must round up (p+mid-1)/mid, not p/mid directly, or you’ll undercount a pile’s time.

0004. Median of Two Sorted Arrays Hard

Problem: Find the median of two sorted arrays, in O(log(m+n)).

Core idea: Median = the k-th smallest problem. Each binary search skips the smaller half of k/2, which can’t contain the k-th smallest.

1
func getKth(a, b []int, k int) int {
2
    if len(a) == 0 { return b[k-1] }  // a exhausted
3
    if len(b) == 0 { return a[k-1] }  // b exhausted
4
    if k == 1 { return min(a[0], b[0]) }  // only 1 left
5
    midA := min(k/2-1, len(a)-1)  // prevent overflow
6
    midB := min(k/2-1, len(b)-1)
7
    if a[midA] < b[midB] {
8
        return getKth(a[midA+1:], b, k-(midA+1))  // skip first half of a
9
    } else {
10
        return getKth(a, b[midB+1:], k-(midB+1))  // skip first half of b
11
    }
12
}
13

14
func findMedianSortedArrays(a, b []int) float64 {
15
    total := len(a) + len(b)
16
    if total%2 == 1 {
17
        return float64(getKth(a, b, (total+1)/2))  // odd: take middle
18
    }
19
    return float64(getKth(a,b,total/2)+getKth(a,b,total/2+1)) / 2.0  // even: take average
20
}