23 All Problems: Pseudocode Reference

Use this page as a compact review sheet. Each section states the problem, the central idea, and language-neutral pseudocode. Use the table of contents to jump directly to a problem; follow the problem title link for the complete explanation, tests, complexity analysis, and Java, Python, and Rust implementations.

23.1 Two Sum

Problem. Given an integer array nums and an integer target, return the indices of two elements whose values add up to target.

Idea. Scan once while mapping each value already seen to its index. Before storing the current value, look for its complement so the two returned indices must be distinct.

indexByValue = empty map
for i from 0 through nums.length - 1:
    needed = target - nums[i]
    if needed is in indexByValue:
        return [indexByValue[needed], i]
    indexByValue[nums[i]] = i
throw no-solution exception

23.2 Merge Intervals

Problem. Given a collection of intervals, combine every set of overlapping intervals and return the resulting non-overlapping intervals.

Idea. Sort by start, then maintain one open merged interval. Extend it when the next interval overlaps; otherwise flush it and begin a new one.

if intervals is empty: return empty list
sorted = copy intervals and sort by start
merged = empty list
current = sorted[0]
for each next interval after the first:
    if next.start < current.end:       // half-open overlap
        current = [min(current.start, next.start),
                   max(current.end, next.end)]
    else:
        add current to merged
        current = next
add current to merged
return merged

23.3 Longest Substring Without Repeating Characters

Problem. Given a string, return the length of its longest contiguous substring with no repeated characters.

Idea. Keep a duplicate-free sliding window. A last-seen map lets the left edge jump just beyond a repeated character without ever moving backward.

lastSeen = empty map
start = 0
best = 0
for end from 0 through s.length - 1:
    c = s[end]
    if c has a previous index:
        start = max(start, lastSeen[c] + 1)
    lastSeen[c] = end
    best = max(best, end - start + 1)
return best

23.4 Valid Parentheses

Problem. Given a string of brackets, return whether every opener is closed by the same type in the correct nested order.

Idea. Push the closer expected by each opener. Every actual closer must match the stack top, and no expected closers may remain after the scan.

expectedClosings = empty stack
for each character c in s:
    if c is an opener:
        push its matching closer
    else if stack is empty or pop() is not c:
        return false
return stack is empty

23.5 Binary Search

Problem. Given a sorted integer array and a target, return a matching index or an absence result.

Idea. Maintain an inclusive candidate interval. Compare its midpoint with the target and discard the half that cannot contain a match.

low = 0
high = nums.length - 1
while low <= high:
    mid = low + (high - low) / 2
    if nums[mid] == target: return mid
    if nums[mid] < target: low = mid + 1
    else: high = mid - 1
return not found

23.6 Three Sum

Problem. Given an integer array, return all unique triplets of values whose sum is zero.

Idea. Sort the values, fix one value, and sweep the remaining range with two pointers. Sorted order determines which pointer to move, while skipping equal values prevents duplicates.

sort nums
answer = empty list
for i from 0 through nums.length - 3:
    if i > 0 and nums[i] == nums[i - 1]: continue
    left = i + 1
    right = nums.length - 1
    while left < right:
        sum = nums[i] + nums[left] + nums[right]
        if sum < 0: left++
        else if sum > 0: right--
        else:
            add [nums[i], nums[left], nums[right]]
            move both pointers
            skip repeated left and right values
return answer

23.7 Group Anagrams

Problem. Partition strings so two strings share a group exactly when they contain the same characters with the same frequencies.

Idea. Convert each word to a canonical key by sorting its characters. Anagrams have identical keys and therefore land in the same map bucket.

groupByKey = empty map from string to list of strings
for each word:
    key = word's characters sorted and joined
    if key has no group: create an empty group
    append the original word to that group
return all map groups

23.8 Top K Frequent Words

Problem. Return the k most frequent distinct words, ordered by decreasing frequency and then lexicographically for ties.

Idea. Count each word, sort the distinct words with the contract’s two-part comparator, and take the first k.

frequency = empty map
for each word: frequency[word]++
rankedWords = list of distinct map keys
sort rankedWords by:
    higher frequency first
    then lexicographically smaller word first
return first k ranked words

23.9 Maximum Subarray

Problem. Given an integer array, return the greatest sum among all nonempty contiguous subarrays.

Idea. At each value, the best subarray ending there either starts fresh or extends the previous one. Track that local optimum and the best seen anywhere.

endingHere = nums[0]
best = nums[0]
for each x after nums[0]:
    endingHere = max(x, endingHere + x)
    best = max(best, endingHere)
return best

23.10 Product of Array Except Self

Problem. For each array index, return the product of every other element without using division.

Idea. Store each index’s left-side product in the output, then multiply it by a running right-side product during a reverse pass.

answer = new array of nums.length
prefix = 1
for i from left to right:
    answer[i] = prefix
    prefix = prefix * nums[i]
suffix = 1
for i from right to left:
    answer[i] = answer[i] * suffix
    suffix = suffix * nums[i]
return answer

23.11 Search in a Rotated Sorted Array

Problem. Given a sorted array rotated at an unknown pivot, return the target’s index or an absence result.

Idea. At least one half around the midpoint is sorted. Identify it, test whether the target belongs inside its value range, and retain only the possible half.

low = 0
high = nums.length - 1
while low <= high:
    mid = low + (high - low) / 2
    if nums[mid] == target: return mid
    if left half is sorted:
        if target is within it: high = mid - 1
        else: low = mid + 1
    else:
        if target is within the right half: low = mid + 1
        else: high = mid - 1
return not found

23.12 Reverse a Singly Linked List

Problem. Given the head of a singly linked list, reverse the list and return its new head.

Idea. Walk the list once, saving the untouched suffix before redirecting each node’s link toward the already reversed prefix.

previous = null
current = head
while current is not null:
    next = current.next
    current.next = previous
    previous = current
    current = next
return previous

23.13 Detect a Linked-List Cycle

Problem. Given a linked structure, return whether repeatedly following next eventually revisits a node.

Idea. Advance one pointer one edge and another two edges. In a finite acyclic list the fast pointer exits; inside a cycle the pointers must eventually meet.

slow = head
fast = head
while fast is not null and fast.next is not null:
    slow = slow.next
    fast = fast.next.next
    if slow and fast are the same node: return true
return false

23.14 Merge Two Sorted Linked Lists

Problem. Merge all nodes from two sorted singly linked lists into one sorted list.

Idea. A sentinel removes the special case for the output head. Repeatedly attach the smaller front node, then attach the one remaining suffix.

sentinel = temporary node
tail = sentinel
while a and b are both non-null:
    if a.value <= b.value:
        tail.next = a
        a = a.next
    else:
        tail.next = b
        b = b.next
    tail = tail.next
tail.next = whichever of a or b remains
return sentinel.next

23.15 Binary-Tree Level-Order Traversal

Problem. Return a binary tree’s values grouped by depth from the root downward.

Idea. Breadth-first search naturally visits by depth. Snapshot the queue size before processing a level so children wait for the next output group.

answer = empty list
if root is null: return answer
queue = queue containing root
while queue is not empty:
    levelSize = queue.size
    level = empty list
    repeat levelSize times:
        node = dequeue
        append node.value to level
        enqueue node.left and node.right if present
    append level to answer
return answer

23.16 Validate a Binary Search Tree

Problem. Return whether every node in a binary tree satisfies the ordering constraints of a binary search tree.

Idea. Local parent-child comparisons are insufficient. Carry the strict lower and upper bounds imposed by every ancestor down the recursion.

isValidBst(root):
    return valid(root, negative infinity, positive infinity)
valid(node, low, high):
    if node is null: return true
    if node.value <= low or node.value >= high: return false
    return valid(node.left, low, node.value)
       and valid(node.right, node.value, high)

23.17 Lowest Common Ancestor of a Binary Tree

Problem. Return the deepest binary-tree node whose subtree contains both target nodes.

Idea. Recursively report a target or ancestor found below. If the left and right subtrees both report a result, the current node is their first meeting point.

lca(node, p, q):
    if node is null or node is p or node is q: return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right are both non-null: return node
    if left is non-null: return left
    return right

23.18 Number of Islands

Problem. Count the separate four-directionally connected regions of land in a two-dimensional grid.

Idea. Each unvisited land cell begins one new island. Flood-fill from it and mark the entire connected region so no part of that island is counted again.

islands = 0
for every row and column:
    if cell is land:
        islands++
        visitIsland(row, column)
return islands
visitIsland(row, column):
    if outside grid or cell is not land: return
    mark cell as water
    visit down, up, right, and left neighbors

23.19 Course Schedule

Problem. Return whether every course can be completed while respecting all prerequisite pairs.

Idea. Use Kahn’s topological sort. Repeatedly complete courses with zero remaining prerequisites and unlock their dependents; a cycle exists if some courses never become ready.

create an outgoing adjacency list for every course
prerequisitesLeft = zero-filled array
for each [course, prerequisite]:
    add course to prerequisite's outgoing list
    prerequisitesLeft[course]++
queue every course with zero prerequisitesLeft
completed = 0
while queue is not empty:
    prerequisite = dequeue
    completed++
    for each course unlocked by prerequisite:
        prerequisitesLeft[course]--
        if it becomes zero: enqueue course
return completed == numCourses

23.20 Coin Change

Problem. Given coin denominations and an amount, return the minimum number of coins needed for an exact total, or an absence result.

Idea. Bottom-up dynamic programming computes the optimum for every smaller amount first. For each total, try every coin as the final choice and retain the best reachable predecessor.

impossible = amount + 1
fewest = array indexed 0 through amount
fewest[0] = 0
for current from 1 through amount:
    fewest[current] = impossible
    for each coin:
        if coin <= current:
            fewest[current] = min(
                fewest[current],
                fewest[current - coin] + 1)
return not found if fewest[amount] is impossible
otherwise return fewest[amount]