Coding interview solutions

Two SumVideo

Store each value's index in a hash map and check for the complement (target - num) as you scan

Merge IntervalsVideo

Sort the intervals by start, then merge any interval that overlaps the previous one

Reverse a String

Copy the immutable string into a character array, then swap inward with two pointers

Longest Common PrefixVideo

Scan characters vertically across all strings and stop at the first mismatch (S is the total number of characters)

Palindrome String

Walk two pointers inward from both ends and compare characters

Palindromic Substrings

Expand around each of the 2n-1 centers and count every palindrome you can grow

Longest Palindromic Substring

Expand around each center and keep the widest palindrome window seen

Palindrome Linked List

Under the current array-serialized judge contract, compare values with two indices moving inward

Roman to IntegerVideo

Add each numeral's value, subtracting when a smaller numeral precedes a larger one

Letter Combinations of a Phone Number

Backtrack through the keypad mapping; materializing each length-n combination dominates time and output space

Valid ParenthesesVideo

Push opening brackets onto a stack and pop to match each closing bracket

Find the Index of the First Occurrence in a String

Check each possible start position and compare the candidate substring directly

Length of Last Word

Scan from the end, skipping trailing spaces, then count the final word's characters

Spiral Matrix

Fill the output matrix layer by layer while shrinking top, bottom, left, and right boundaries

FizzBuzz

Loop from 1 to n and test divisibility by 3 and 5 for each number

Contains Duplicate

Track seen values in a hash set and return true on the first repeat

Maximum SubarrayVideo

Apply Kadane's algorithm: extend or restart the running sum, tracking the best seen

Fibonacci Number

Iterate with two rolling variables instead of recomputing overlapping subproblems

Factorial

Multiply the numbers 1 through n iteratively (recursion adds O(n) stack space)

Move Zeroes

Use a write pointer to pack non-zero values forward, then fill the rest with zeros

Single Number

XOR every element together; duplicates cancel and the unique number remains

Best Time to Buy and Sell StockVideo

Track the minimum price so far and the best profit in a single pass

Valid Anagram

Compare character frequency counts of both strings (fixed 26-letter table)

Binary Search

Halve the search range each step by comparing the target to the middle element

Count Vowels

Scan the string once and increment a counter on each vowel

Climbing StairsVideo

DP where ways(n) = ways(n-1) + ways(n-2), kept in two rolling variables (Fibonacci)

Product of Array Except Self

Multiply prefix products left-to-right, then suffix products right-to-left (output excluded from space)

Trapping Rain WaterVideo

Two pointers with running left/right maxima decide the trapped water at each step

Edit Distance

2D DP over prefixes, taking the min of insert, delete, and replace (compressible to one row)

Median of Two Sorted Arrays

Binary search for the correct partition on the smaller array

Longest Valid Parentheses

Track indices on a stack (or two directional counting passes) to measure valid runs

Palindrome Number

Reverse only the second half of the digits and compare with the first half

Plus One

Add one from the least significant digit, propagating the carry

Majority Element

Boyer-Moore voting: keep a candidate and a count that cancels on mismatches

Is Subsequence

Two pointers advance through s and t, matching characters in order

First Unique Character in a String

Count character frequencies, then return the first index with a count of one

Search Insert Position

Binary search for the target, returning the left bound as the insert position

House RobberVideo

DP choosing max(rob current + best two back, skip current), kept in rolling variables

Jump Game

Greedily track the farthest reachable index; fail if a position is unreachable

Coin Change

Bottom-up DP: min coins for each sub-amount using every coin (n is the coin count)

Longest Substring Without Repeating CharactersVideo

Sliding window with a last-seen index map to jump the left edge past repeats

Container With Most WaterVideo

Two pointers from both ends, always moving the shorter line inward

Number of IslandsVideo

DFS/BFS flood fill from each unvisited land cell, marking the whole island

Word Break

DP where each prefix is breakable if some split point plus a dictionary word matches

Longest Increasing Subsequence

Maintain a tails array and binary-search each number's position (patience sorting)

Largest Rectangle in Histogram

Monotonic increasing stack of bar indices computes each bar's widest span

Sliding Window Maximum

Monotonic decreasing deque of indices keeps the current window's max at the front

Jump Game II

Greedy BFS by levels: extend the current jump's reach and count boundary crossings

Reverse Linked List

Iteratively rewire each node's next pointer backward using three tracking pointers (prev/curr/next)

Maximum Depth of Binary Tree

Recursively take 1 + the larger of the left/right subtree depths; space is the call stack, bounded by tree height h (O(log n) balanced, O(n) worst case)

Course ScheduleVideo

Kahn topological sort removes zero-indegree courses

Rotting Oranges

Multi-source BFS expands one minute-layer at a time

Redundant Connection

Disjoint-set union detects an edge joining already-connected nodes

Kth Largest Element in an Array

Maintain a min-heap containing only the k largest values

Top K Frequent Elements

Bucket values by frequency and scan buckets from high to low

Subsets

Backtracking makes an include/exclude decision for each value

Invert Binary TreeVideo

DFS swaps children at every node

Same Tree

Parallel DFS compares corresponding nodes

Validate Binary Search Tree

DFS carries the full valid value range

Binary Tree Level Order Traversal

BFS processes one queue level at a time

Lowest Common Ancestor of a BST

BST ordering identifies where search paths split

Merge Two Sorted Lists

Two pointers splice the smaller next node

Linked List CycleVideo

Floyd slow/fast pointers detect repeated traversal state

Reorder List

Split, reverse the second half, then weave halves

Clone Graph

DFS copies each vertex and adjacency row once

Pacific Atlantic Water Flow

Reverse graph searches grow inward from both oceans

Network Delay Time

Dijkstra settles nodes by earliest signal arrival

Merge K Sorted Lists

A min-heap retains one current value from each list

Find Median from Data Stream

Two heaps balance the lower and upper halves

Permutations

Backtracking chooses each remaining value next

Combination Sum

Backtracking branches between reusing and skipping each candidate

Word Search

DFS backtracks over matching adjacent cells

Implement Trie

Trie edges share prefixes across inserted words

Design Add and Search Words

Trie search backtracks across children for wildcard positions

LRU Cache

Hash lookup plus recency ordering supports O(1) operations

Unique Paths

Closed-form binomial coefficient C(m + n - 2, m - 1), or an O(n)-space rolling DP row

Pascal's Triangle

Build each row from the previous by summing adjacent pairs

Count Primes

Sieve of Eratosthenes, crossing out each prime's multiples from p*p

Sqrt(x)

Binary search the largest r with r*r <= x

Happy Number

Floyd's slow/fast pointers over the digit-square-sum sequence detect the cycle

Excel Sheet Column Number

Horner-style base-26 accumulation with digits 1..26

Insert Interval

A single linear pass copies intervals before the overlap, merges through it, then copies the rest

Non-overlapping Intervals

Sort by end time and greedily keep the interval that frees the schedule soonest

Sort Colors

Dutch National Flag partitioning with low/mid/high pointers in one pass

Number of Provinces

Union-find merges directly connected cities and counts remaining roots

Minimum Size Subarray Sum

A variable-size sliding window expands right and shrinks left once the sum reaches target

3Sum

Sort the array, fix one value, then two-pointer scan the rest while skipping duplicates

Rotate Image

Transpose the matrix along the main diagonal, then reverse each row

Search in Rotated Sorted Array

Binary search while detecting which half of the current window is sorted to decide where to look

Longest Consecutive Sequence

Put every value in a hash set, then only start counting a run from numbers whose predecessor is absent

Sum of Two Integers

Repeatedly XOR for the sum-without-carry and AND+shift for the carry until no carry remains

Symmetric Tree

Parallel DFS mirrors the left subtree against the right subtree at every level

Diameter of Binary Tree

Bottom-up DFS height computation updates a running best (left height + right height) at every node

Kth Smallest Element in a BST

Iterative in-order traversal with an explicit stack, stopping at the k-th node visited

Add Two Numbers

Digit-by-digit simulation of grade-school addition with carry propagation

Remove Nth Node From End of List

Two-pointer gap technique advances a lead pointer n steps ahead, then moves both until the lead hits the end (Rust uses two passes — one to count length — to avoid move/borrow conflicts on Option<Box<ListNode>>; still O(1) auxiliary space)

Path Sum

Root-to-leaf DFS carries a running remaining-sum down the tree, checking it against 0 only at leaves

Convert Sorted Array to Binary Search Tree

Divide and conquer roots each subtree at the middle element of the current subarray so both halves stay balanced

Reverse Linked List II

Dummy-node walk to the node before left, then repeatedly splices the next node to the front of the reversed segment (Rust rebuilds via a Vec instead — O(n) auxiliary — to avoid move/borrow conflicts on Option<Box<ListNode>>)

Swap Nodes in Pairs

Dummy-node walk repoints three links per pair (Rust is written recursively for idiomatic Option<Box<ListNode>> ownership, costing O(n) call-stack space instead)

Binary Tree Right Side View

Level-order BFS keeps only the last node visited at each depth, where w is the widest level

Merge Two Binary Trees

Recursive DFS overlays both trees node-by-node, summing values where both exist and returning the non-null side otherwise

Path Sum II

DFS with backtracking accumulates the current root-to-leaf path and copies it into the result whenever a leaf matches the target sum (copying each valid path is the quadratic-worst-case term)

Construct Binary Tree from Preorder & Inorder

A value-to-inorder-index hash map plus a preorder cursor lets each subtree root be split from its children in O(1), giving one recursive build per node

Linked List Cycle II

Floyd's tortoise-and-hare detects a meeting point inside the cycle, then a second pointer from the head meets it exactly at the cycle's start (encoded as plain next-index array, matching linked-list-cycle)

Odd Even Linked List

Two interleaved pointers splice odd- and even-positioned nodes onto separate chains in one pass, then the even chain is reattached after the odd chain's tail (Rust rebuilds via a Vec of values instead of in-place splicing, to avoid holding two simultaneous mutable borrows into one Option<Box<ListNode>> chain)

Task Scheduler

Count task frequencies, frame the schedule around the most frequent task, and compare that frame length with the raw task count

Connected Components in an Undirected Graph

Union-find starts with n singleton components and decrements the count only when an edge merges two previously separate roots

Palindrome Partitioning

Precompute which substrings are palindromes, then backtrack left-to-right and only recurse on palindromic cuts

Word Search II

Build one trie for all words and DFS the board once, pruning any path that stops matching a trie prefix

Word Ladder

BFS over dictionary words, generating one-letter mutations on the fly and stopping the first time the end word is reached

Daily Temperatures

A decreasing monotonic stack of unresolved indices lets each day answer earlier cooler days the first time a warmer temperature appears

Decode Ways

Right-to-left dynamic programming counts decodings of each suffix while keeping only the next two DP states

Gas Station

Track the total fuel balance plus a running tank, resetting the candidate start whenever the running tank drops below zero

Alien Dictionary

Build precedence edges from adjacent words, then run Kahn's topological sort with a min-priority frontier to make the valid order lexicographically smallest (C total characters, U unique letters)

Binary Tree Maximum Path Sum

Post-order DFS returns the best extendable gain from each node while updating a separate global best for any path that bends through that node

Meeting Rooms II

Sort starts and ends separately, then sweep both lists to count how many rooms are simultaneously needed

Minimum Window Substring

A sliding window expands until it covers every required character count, then shrinks greedily to keep the smallest valid range

Longest Increasing Path in a Matrix

Treat larger-value moves as DAG edges, compute each cell's outdegree, and count topological BFS layers from local peaks

Range Sum Query - Mutable

A Fenwick tree stores partial prefix sums so point updates and inclusive range queries both stay logarithmic

Cheapest Flights Within K Stops

Run Bellman-Ford style relaxations for exactly k+1 edge layers, always writing into a copied distance array to respect the stop budget

Group Anagrams

Hash each word by its 26-letter frequency signature and preserve first-seen group order while collecting members

Min Stack

Mirror the running minimum at every stack depth with a second stack so top and getMin stay constant time

Accounts Merge

Union account rows that share an email, then gather and sort each component's email set for deterministic output

K Closest Points to Origin

Keep the current best k points in a size-k max-heap, then sort the retained points by distance and tie-breakers

Counting Bits

Use DP with answer[i] = answer[i >> 1] + (i & 1) so each bit count reuses a smaller value

Maximum Product Subarray

Track the maximum and minimum product ending at each index because a negative value can swap their roles

Course Schedule II

Kahn topological sort removes zero-indegree courses and appends them to the answer order

Kth Smallest Element in a Sorted Matrix

Binary-search the answer value and count how many entries are <= mid by walking from the bottom-left corner

Missing Number

Subtract the array's actual sum from the expected sum of the full range 0..n

Find All Anagrams in a String

Slide a fixed-length window across s while maintaining 26-letter frequency counts

Find Minimum in Rotated Sorted Array

Binary search toward the unsorted half by comparing the middle value with the rightmost value

Search a 2D Matrix

Treat the matrix as one sorted list of length m*n and binary-search it using index arithmetic

Single Number II

Sum each bit position modulo 3; the leftover bits reconstruct the unique number

Subarray Sum Equals K

Track running prefix sums in a hashmap and count how often prefix - k was seen before

Isomorphic Strings

Track a forward and a backward character map and reject any conflicting pairing

Next Permutation

Scan from the right to find the pivot, swap with the next-larger suffix value, then reverse the descending suffix

First Missing Positive

Place each in-range value x at index x-1 by swapping, then scan for the first index whose value is wrong

Set Matrix Zeroes

First pass records which rows/columns contain a zero, second pass zeroes any cell in a marked row or column

Spiral Matrix II

Fill the matrix ring by ring while shrinking top, bottom, left, and right boundaries

Balanced Binary Tree

Run one postorder DFS that returns subtree height or an imbalance sentinel as soon as a node fails

Lowest Common Ancestor of a Binary Tree

Post-order DFS returns target hits upward and marks the first split point as the LCA

Binary Tree Zigzag Level Order Traversal

BFS processes one queue level at a time and writes values into zigzag positions, where w is the widest level

Pseudo-Palindromic Paths in a Binary Tree

Root-to-leaf DFS toggles a 9-bit parity mask, and each leaf qualifies exactly when that mask has at most one bit set

N-Queens

Backtrack row by row, trying columns left-to-right while boolean arrays mark blocked columns and diagonals so the DFS emits boards in canonical order

Rotate String

Check equal lengths, then test whether goal appears inside the doubled string s + s

Min Cost Climbing Stairs

Roll two variables holding the cheapest cost to reach the previous two stairs and take the minimum incoming move at each step

House Robber II

Run the linear house-robber recurrence twice — once skipping the first house and once skipping the last — and take the larger result

Unique Paths II

Sweep the grid row by row keeping one rolling DP row; zero out obstacle cells and otherwise add the paths arriving from the left and from above

Partition Equal Subset Sum

Reduce to a subset-sum for half the total, then fill a 1D boolean reachability table iterating each value from high sums down to avoid reusing it twice

House Robber III

One postorder DFS returns each node's best loot with and without robbing it, so a parent combines children in O(1) without recomputation

Generate Parentheses

Backtrack with open/close counts, always trying '(' before ')' so only valid prefixes are explored and emitted in canonical order

Longest Common Subsequence

2D DP over string prefixes: on a character match take the diagonal + 1, otherwise carry forward the best of top/left; rolling rows can reduce space when only the length is needed

Flatten Binary Tree to Linked List

Postorder-style DFS flattens left and right subtrees, then splices the flattened left chain between the current node and the flattened right chain in preorder order

01 Matrix

Run a multi-source BFS from every zero at once, assigning each unvisited neighbor its distance the first time it is reached

Find the Duplicate Number

Treat nums as a functional graph and use Floyd's tortoise-and-hare to find the cycle entrance, which is the duplicate value

Merge Sorted Array

Use three pointers from the end of nums1, nums2, and the write position so the larger trailing value is placed first without overwriting unfinished data

Top K Frequent Words

Count word frequencies, keep the best k candidates in a min-heap ordered by frequency ascending and word descending, then sort the heap contents into the required final order

Path Sum III

Prefix-sum DFS tracks how many earlier running sums equal currentSum - targetSum, then decrements the current prefix count while backtracking so only downward paths in the active root-to-node chain are counted

Combination Sum III

Backtracking chooses the next larger digit from 1..9 and prunes impossible remaining sums

Sort List

Top-down merge sort splits the list with slow/fast pointers, recursively sorts both halves, then merges the sorted sublists

Binary Tree Inorder Traversal

Iterative in-order traversal with an explicit stack simulates the recursive left-node-right walk and visits each node exactly once

3Sum Closest

Sort the array, fix one value, then two-pointer scan the rest while tracking the closest triplet sum

Combination Sum II

Sorted backtracking skips equal values at the same depth and prunes oversized candidates

Decode String

Scan once, accumulating multi-digit counts and using stacks of prior strings and repeat counts to expand each bracketed segment when `]` closes it

Maximal Square

DP where dp[row][col] stores the largest all-1 square ending at that cell; when matrix[row][col] is 1, extend the minimum of top, left, and top-left by 1

Binary Tree Preorder Traversal

Iterative preorder with an explicit stack: pop a node, record it, then push its right child before its left child so the left subtree is processed first

Binary Tree Postorder Traversal

Single-stack iterative postorder that tracks the last visited node, only visiting a node after its right subtree has been processed

Valid Sudoku

Single pass over the fixed 9x9 board tracking used digits per row, column, and 3x3 box in boolean lookup tables, failing fast on the first conflict

Find All Duplicates in an Array

Reuse the input array as a visited map by negating nums[abs(val) - 1]; a value hitting an already-negative slot is a duplicate

Reverse Words in a String

Scan from the end of the string, collecting maximal non-space runs as words while skipping spaces, then join them with single spaces

Two Sum II - Input Array Is Sorted

Converge two pointers from both ends of the sorted array, moving the one that brings the sum toward the target, and return the 1-based indices on a match

Koko Eating Bananas

Binary-search the eating speed in [1, max(piles)]; for each candidate sum ceil(pile/speed) hours and keep the smallest speed whose total stays within h

Integer to Roman

Greedily subtract from a fixed descending table of thirteen value/symbol pairs (including the six subtractive forms), appending each symbol while it still fits

Reverse Integer

Peel digits off the magnitude with %10 and /10 to build the reversed number, reapply the sign, and return 0 if it escapes the signed 32-bit range

H-Index

Counting-sort the citations into n+1 buckets (clamping counts above n), then sweep from the top accumulating papers with at least i citations and return the first i the running total reaches