Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Each input has exactly one solution; you may not use the same element twice.

Walk through the array once. For each number x, the value you'd need to pair with it is target - x. Keep a hash map of every number you've already passed, mapping its value to its index. Before storing the current number, check the map for target - x — if it's there, you've found your pair and can return both indices. The map lookup is O(1), which turns the brute-force O(n²) double loop into a single O(n) pass.

Two Sum

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a stock on day i. Choose one day to buy and a later day to sell to maximize profit. Return 0 if no profit is possible.

You can't go back in time — the buy day must come before the sell day. So scan left-to-right while tracking two things: the lowest price seen so far (your best possible buy) and the best profit achievable by selling at today's price (today minus that lowest). Update both at every step. The final answer is the highest profit ever recorded; if prices only fall, it stays at 0.

Best Time to Buy and Sell Stock

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Walk through the array once, adding each element to a hash set. The moment you try to add a value that's already in the set, you've found a duplicate — return true immediately. If you finish the loop without ever colliding, every element was unique. Hash sets give O(1) average-case add and lookup, so the entire pass is O(n).

Contains Duplicate

Product of Array Except Self

Given nums, return an array answer where answer[i] equals the product of all elements of nums except nums[i]. Solve in O(n) without using division.

Without using division, you need to know — for each index i — the product of every element to its left and the product of every element to its right; multiplying those two gives the answer. Do it in two passes. Pass 1 (left-to-right): write the running product of everything to the left of i into res[i]. Pass 2 (right-to-left): multiply res[i] by a running product of everything to the right of i. Each cell ends up holding the full product except itself, in O(n) time and O(1) extra space (the output array doesn't count).

Product of Array Except Self

Maximum Subarray

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. (Kadane's algorithm.)

At each index, ask one question: is the running subarray helping me, or hurting me? If the running sum so far is negative, it can only drag down whatever you add next — drop it and start a fresh subarray at the current element. Otherwise keep it and add the current element. Track the best running sum you've ever seen; that's the answer. One linear pass, no extra space.

Maximum Subarray

Maximum Product Subarray

Given an integer array nums, find the contiguous non-empty subarray within nums that has the largest product, and return that product. The answer is guaranteed to fit in a 32-bit integer.

If this were sums, you'd just keep a running total and reset whenever it went negative. Products are harder because of one thing: a negative times another negative is a positive — and if both are large in magnitude, the result can be huge. That means a 'bad' running product (very negative) is actually valuable if the next number is also negative, because it can flip into the best answer. So at every index you can't track just one running value — you have to track two: the largest product of any subarray ending at this index, and the smallest (most negative) product of any subarray ending at this index. When you move to the next number `curr`, the best subarray ending there must be one of three things: (1) `curr` by itself, starting a fresh subarray; (2) `curr` multiplied into the previous max, extending a positive streak; (3) `curr` multiplied into the previous min, in case `curr` is negative and flips a deeply-negative streak into a large positive. Take the max of those three for the new running max. Take the min of the exact same three candidates for the new running min — because next iteration, the min you have now might become the biggest answer. Keep a separate `best` variable that takes the max of itself and the running max at every step. That's your answer.

Maximum Product Subarray

Find Minimum in Rotated Sorted Array

An ascending sorted array of unique elements has been rotated. Find the minimum element in O(log n).

In a rotated sorted array, the minimum sits exactly at the rotation point. Binary search by comparing the middle element to the right boundary. If nums[m] > nums[r], the rotation point (and minimum) lies somewhere strictly to the right of m, so move l = m + 1. Otherwise the minimum is at m or to its left, so set r = m (don't skip m — it could be the answer). When l and r meet, you've cornered the minimum.

Find Minimum in Rotated Sorted Array

Search in Rotated Sorted Array

Given a rotated sorted array of distinct integers and a target, return its index, or -1 if not found. Must run in O(log n).

A rotated sorted array always has at least one half (left or right of mid) that's still in plain sorted order. Figure out which half by comparing nums[l] to nums[m]: if nums[l] ≤ nums[m], the left half [l..m] is sorted; otherwise the right half [m..r] is. Once you know which half is clean, you can decide in O(1) whether the target lies inside it (just compare against its endpoints). Discard the other half and continue. Standard binary search, plus one 'which side is sorted?' check per step.

Search in Rotated Sorted Array

3Sum

Given nums, return all unique triplets [a,b,c] such that a+b+c == 0. The solution set must not contain duplicate triplets.

Sort the array first — this enables an efficient two-pointer search. Fix one number nums[i] in the outer loop, then in the remaining sorted suffix use two pointers l (just after i) and r (the end) to find pairs that sum to -nums[i]. If the three-sum is too small, advance l; if too big, retreat r; if it hits zero, record the triplet and step both pointers inward. Duplicates are the only tricky part. Because the array is sorted, equal numbers cluster together, so the same triplet can be generated multiple times — both from a repeated nums[i] in the outer loop and from repeated l/r values inside the sweep. The clean way to handle this is to collect triplets into a Set<List<Integer>>: sorting guarantees each triplet appears in the same canonical order, so equal triplets hash identically and the Set silently drops the duplicates. No fiddly skip-while loops needed. Outer loop O(n), each inner sweep O(n) → O(n²) overall.

3Sum

Container With Most Water

Given n non-negative integers representing wall heights, find two lines that with the x-axis form a container holding the most water.

Start with the widest possible container — left pointer at 0, right pointer at n-1. The water area is min(height[l], height[r]) × (r - l). Now shrink: which pointer should you move? Always move the SHORTER wall. Reasoning: the height is capped by the shorter wall, and moving the taller wall inward can only reduce the width without ever raising the height — there's no chance of improvement. Moving the shorter wall at least gives the height a chance to grow. Track the best area as you go.

Container With Most Water

Sum of Two Integers

Given two integers a and b, return their sum without using the operators + or -. Use bit manipulation: XOR for sum-without-carry, AND+shift for carry.

Reproduce binary addition without using + or -. XOR (^) gives the sum of two bits while ignoring any carry. AND (&) followed by a left shift gives exactly the bits that need to be carried into the next column. Loop: compute the carry, set a = a XOR b (sum so far without carries), then set b = the shifted carry. Repeat until there's nothing left to carry — at that point a holds the final sum.

Sum of Two Integers

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of 1 bits (Hamming weight). Trick: n & (n-1) clears the lowest set bit.

There's a bit-manipulation identity worth memorising: the expression n & (n - 1) always clears the lowest 1-bit of n, leaving every other bit untouched. So if you keep applying that and counting, by the time n becomes 0 you've cleared every 1-bit, and your counter equals the original number of 1-bits. This is faster than checking all 32 bits one by one because you only do work for the bits that are actually set.

Number of 1 Bits

Counting Bits

Given n, return an array of length n+1 where ans[i] is the number of 1's in the binary representation of i. Solve in O(n).

Notice that i and i >> 1 (i with its lowest bit dropped) have the same number of 1-bits, except for that one bit you might have dropped. So bits(i) = bits(i >> 1) + (i & 1). Build the result array bottom-up: dp[0] = 0, then for each later i compute dp[i] in O(1) from an already-filled smaller index. One pass, no per-number bit counting.

Counting Bits

Missing Number

Given an array nums containing n distinct numbers in [0, n], return the only number in the range that is missing.

The numbers 0 through n add up to n(n+1)/2 — the closed-form sum of the first n+1 integers. Subtract every number actually present in the array from that expected total, and whatever's left is the missing number. One pass, O(1) extra space, no hashing or sorting needed.

Missing Number

Reverse Bits

Reverse the bits of a 32-bit unsigned integer. Shift the answer left and OR in the lowest bit of n; then shift n right.

Build the reversed result one bit at a time. On each iteration: shift res left by 1 (making room for a new bit at position 0), then OR in the lowest bit of n. Then unsigned-shift n right by 1 to expose the next bit. After 32 passes, every bit of n has migrated to its mirrored position in res.

Reverse Bits

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways can you reach step n? (Fibonacci.)

Think backwards from step n. The very last move you made to land on n was either a 1-step (so you came from step n-1) or a 2-step (you came from n-2). Those are the only two options, and they don't overlap, so the number of ways to reach n equals the ways to reach n-1 plus the ways to reach n-2. That recurrence is exactly the Fibonacci sequence. Build it bottom-up from steps 0 and 1 — you only need to remember the previous two values, so it's O(1) extra space.

Climbing Stairs

Coin Change

Given coin denominations and an amount, return the fewest number of coins needed to make up that amount. Return -1 if impossible.

Define dp[i] = the fewest coins needed to make amount i. Base case: dp[0] = 0. For every i from 1 to amount, try each coin c — if i - c is reachable, then dp[i] could be dp[i-c] + 1. Take the minimum across all coin choices. Initialise the array with a sentinel (amount + 1, larger than any possible answer) so 'unreachable' shows up naturally. At the end, dp[amount] is your answer (or -1 if it's still the sentinel).

Coin Change

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. Patience sort gives O(n log n).

Maintain an array tails where tails[k] holds the smallest possible tail value of any increasing subsequence of length k+1 seen so far. For each new x, binary-search the leftmost position pos where tails[pos] >= x. If you find one, overwrite tails[pos] with x — you've made an increasing subsequence of that length end with a smaller value, leaving more room to extend later. If x is larger than every tail, append it (longest subsequence grew by 1). The contents of tails aren't a valid LIS, but its length always equals the LIS length. O(n log n) total.

Longest Increasing Subsequence

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence (not necessarily contiguous).

Build a table dp where dp[i][j] is the LCS length of a's first i characters and b's first j characters. Recurrence: if the latest characters match (a[i-1] == b[j-1]), dp[i][j] = dp[i-1][j-1] + 1 — extend the previous match. Otherwise, drop one character from either string and take the better option: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base row and column are zero (an empty string has no common subsequence). The answer is dp[m][n].

Longest Common Subsequence

Word Break

Given string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of dictionary words.

Define dp[i] = true if the prefix s[0..i) can be split entirely into dictionary words. Base case: dp[0] = true (the empty prefix is trivially valid). For each i, try every split point j < i: if dp[j] is true and the substring s[j..i) is in the dictionary, then dp[i] is true as well — break early. Answer is dp[s.length]. Putting the dictionary in a HashSet makes each membership check O(1).

Word Break

Combination Sum IV

Given an array of distinct positive integers nums and a target, return the number of possible orderings (sequences) that sum to target.

Despite the name, this counts the number of ordered SEQUENCES of nums that sum to target (so [1,2] and [2,1] are different). Define dp[i] = number of sequences summing to i. Base: dp[0] = 1 (one empty sequence sums to 0). For each total i from 1 to target, sum dp[i - n] over every n in nums — each contributes 'all the ways to make i - n, then append n'. Critically, the OUTER loop is over totals (not coins) — that ordering is what makes sequences count rather than combinations.

Combination Sum IV

House Robber

Given non-negative integers representing money in each house, return the max you can rob without robbing two adjacent houses.

At each house i you have two choices: rob it (then add nums[i] to whatever you'd best collected up to house i-2 — you can't touch i-1 because it's adjacent) or skip it (keep your best total through house i-1). So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). You only ever need the previous two values, so roll two variables prev and curr instead of allocating a full array.

House Robber

House Robber II

Same as House Robber, but the houses are arranged in a circle (first and last are adjacent). Run House Robber on nums[1:] and nums[:-1].

Same recurrence as House Robber, but the houses are arranged in a circle, so the first and last houses are now neighbours and can't both be robbed. Reduce to two simpler linear problems: (a) rob within nums[0..n-2] (last house excluded) and (b) rob within nums[1..n-1] (first house excluded). Each becomes a regular linear House Robber. The answer is the larger of the two. Handle the n == 1 edge case separately (return nums[0]).

House Robber II

Decode Ways

A message of digits encodes letters: 'A'=1 ... 'Z'=26. Return the number of ways to decode the string.

Define dp[i] = number of ways to decode the prefix s[0..i). Base: dp[0] = 1 (empty has one decoding — itself). For each i, look at the last one or two digits. If s[i-1] is '1'..'9', it can stand alone as a letter — add dp[i-1]. If s[i-2..i] forms a number 10..26, it can be one two-letter decoding — add dp[i-2]. Watch for the leading-zero edge case: if s[0] == '0', there are zero valid decodings overall.

Decode Ways

Unique Paths

On an m x n grid, a robot at top-left moves only right or down. How many distinct paths reach the bottom-right?

From any cell you can only move right or down, so the number of paths to (i, j) equals paths to (i-1, j) plus paths to (i, j-1). The top row and left column are all 1 (only one way along an edge). You only ever need the current row and the row above, so keep one 1-D array of length n and update it in place: dp[j] += dp[j-1] computes 'paths to (i, j) = paths to (i-1, j) (already in dp[j]) + paths to (i, j-1) (just computed in dp[j-1])'.

Unique Paths

Jump Game

Given nums where nums[i] is the max jump length from index i, can you reach the last index? Greedy: track furthest reach.

Walk left-to-right, tracking 'reach' — the farthest index you can possibly land on so far. At each index i, first check if i > reach; if so, you've hit a position that can't be reached and you're stuck — return false. Otherwise update reach = max(reach, i + nums[i]) (the farthest you can jump from this index). If you make it through the whole loop, you reached every index, including the last one.

Jump Game

Clone Graph

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Use DFS + a Map from original to clone.

Walk the original graph with DFS, building copies as you go. Keep a HashMap from each original node to its newly created clone — this acts as both the 'visited' marker AND the way to return the same clone whenever you encounter the same original node twice (essential because graphs can have cycles). For each original node: if it's already in the map, return the cached copy. Otherwise create a new node with the same value, store it in the map BEFORE recursing into neighbours (so cycles short-circuit on the second visit), then recursively clone each neighbour and attach.

Clone Graph

Course Schedule

n courses labeled 0..n-1 with prerequisite pairs [a,b] meaning b must precede a. Return true if all courses can be finished (no cycles). Use Kahn's topological sort.

Model courses as nodes and each prerequisite [a, b] as a directed edge b → a (b must come before a). The schedule is feasible iff the graph has no cycles, i.e. you can topologically sort it. Kahn's algorithm: compute each node's in-degree (number of unmet prerequisites). Push every zero-in-degree node into a queue, then repeatedly pop one (mark it done) and decrement the in-degrees of its dependents — any that hit zero are queued. Count how many you process; if it equals n, you finished all courses. If a cycle exists, some nodes never reach zero and stay stuck.

Course Schedule

Pacific Atlantic Water Flow

Given an m x n matrix of heights, water flows to a neighbor if its height is <=. Return cells from which water can flow to BOTH the Pacific (top/left) and Atlantic (bottom/right).

Don't simulate water flowing FROM each cell TO an ocean — that's too expensive. Reverse the perspective: pretend water flows uphill in your model. Start a DFS from every cell on the Pacific border (top row + left column) and mark every cell you can reach by only stepping to neighbours of equal-or-greater height. Do the same from the Atlantic border (bottom row + right column). The cells reachable in BOTH searches are exactly those from which water can drain to both oceans. Two passes, O(m·n) total.

Pacific Atlantic Water Flow

Number of Islands

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is a group of '1's connected 4-directionally.

Scan the grid cell by cell. Every time you find a '1' you haven't visited yet, that's a new island, so increment your counter. Then 'sink' that whole island by running DFS from that cell, flipping every connected '1' to '0' as you go (4-directional neighbours only). Because you've turned visited land into water, when your outer scan reaches those cells later it'll skip them — so each island is counted exactly once. You don't need a separate visited array; the grid itself records what you've seen.

Number of Islands

Longest Consecutive Sequence

Given an unsorted array, return the length of the longest consecutive elements sequence. Solve in O(n). Only start counting from sequence starts.

Throw all numbers into a HashSet for O(1) membership checks. Then for each number n in the set, only START counting if n - 1 is NOT in the set — that means n is the smallest of its consecutive run. From there, walk upward (n+1, n+2, ...) while the next number exists, counting the length. The 'only start from sequence starts' rule keeps the inner loop's TOTAL work O(n) across all iterations, even though it looks like nested loops.

Longest Consecutive Sequence

Alien Dictionary

Given a sorted list of words from an alien language, derive the order of letters. Build a graph from each adjacent word pair and topo-sort.

Compare each pair of adjacent words. The first position where they differ tells you one ordering rule: that character of the earlier word must come before that character of the later word. Treat these as directed edges in a graph over the alphabet. Then topologically sort with Kahn's BFS. Two edge cases: if one word is a prefix of an EARLIER longer word (e.g. 'apple' before 'app'), that's invalid — return empty string. After topological sort, if the result is shorter than the alphabet you collected, there's a cycle — also return empty string.

Alien Dictionary

Graph Valid Tree

Given n nodes (0..n-1) and a list of edges, decide if these edges form a valid tree. A valid tree has exactly n-1 edges, is connected, and has no cycles.

An undirected graph on n nodes is a tree iff it has exactly n - 1 edges AND is connected. Equivalently: exactly n - 1 edges AND no cycles. Use Union-Find: walk through edges and union the endpoints. If you ever try to union two nodes that already share a root, you've found a cycle — return false. If you survive every edge with the count check passing too, the graph is connected and acyclic — a valid tree.

Graph Valid Tree

Number of Connected Components

Given n nodes and an array of edges in an undirected graph, return the number of connected components. Union-Find: start with n components and decrement on each successful union.

Start with n disconnected nodes — that's n components. Walk through every edge and union its endpoints; each successful union (different roots) merges two components into one, so decrement the counter. Edges between already-connected nodes leave the count alone. The final counter is your answer.

Number of Connected Components

Insert Interval

Given non-overlapping intervals sorted by start, insert a new interval (merging if necessary) and return the result.

Intervals are already sorted by start. Walk through in three phases. Phase 1: copy any interval that ends strictly before newInterval starts — these don't overlap. Phase 2: any interval whose start is ≤ newInterval's end overlaps — keep merging by extending newInterval's bounds to absorb them. Phase 3: copy any remaining intervals that start after newInterval ends. Push newInterval at the boundary between phases 2 and 3. O(n) total.

Insert Interval

Merge Intervals

Given an array of intervals, merge all overlapping intervals and return the merged list. Sort by start; merge by extending the last interval's end.

First sort the intervals by their start time. Then walk through them in order, maintaining a 'merged so far' list that starts with the first interval. For each new interval, peek at the last interval already in the list: if the new one starts at or before the last one ends, they overlap, so merge them by extending the last interval's end to the larger of the two ends. Otherwise there's a gap, so just append the new interval to the list as its own entry. The sort dominates the runtime at O(n log n); the sweep is O(n).

Merge Intervals

Non-overlapping Intervals

Given intervals, return the minimum number you must remove so that the rest are non-overlapping. Greedy by earliest end time.

Sort intervals by their END time. Walk through them, keeping track of the most recently kept interval's end. For each interval: if its start is >= the kept end, it doesn't overlap — keep it (update kept end). Otherwise it overlaps with what you've already kept; remove it (increment counter). Sorting by end time guarantees that whenever there's a conflict, removing the later-ending interval leaves the most room for everything that comes next — that's the greedy correctness argument.

Non-overlapping Intervals

Meeting Rooms

Given an array of meeting time intervals, determine if a person could attend all meetings (no overlaps).

Sort the meetings by start time. Then walk through and check every adjacent pair: if the current meeting starts before the previous one ends, you can't attend both — return false. If you reach the end without conflicts, you can attend them all.

Meeting Rooms

Meeting Rooms II

Given meeting intervals, return the minimum number of conference rooms needed. Use sorted starts/ends two-pointer or a min-heap of end times.

Pull all start times into one sorted array and all end times into another. Walk a pointer s through the sorted starts. For each start time, ask 'has any meeting ended by now?' by comparing against ends[e]. If not, you need a new room (rooms++). If yes, an existing room frees up — advance the end pointer e instead. The peak number of overlapping meetings (the max value rooms reaches) is your answer.

Meeting Rooms II

Reverse Linked List

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

Walk the list once with three pointers. prev is the head of the reversed list you're building (starts as null). curr is the node you're currently flipping. next is a temporary that holds curr's original next pointer so you don't lose the rest of the original list when you overwrite it. At each step: save curr.next into next, set curr.next = prev (this is the actual reversal), then advance prev = curr and curr = next. When curr becomes null you've processed every node, and prev is the new head.

Reverse Linked List

Linked List Cycle

Given head of a linked list, determine if it contains a cycle. Floyd's tortoise & hare: slow moves 1, fast moves 2; they meet inside any cycle.

Use two pointers: slow advances one node per step, fast advances two. If the list ends (fast reaches null), there's no cycle. If there IS a cycle, the fast pointer eventually 'laps' the slow one and they meet at some node inside the cycle — at that moment, return true. Constant extra space, no hash set needed.

Linked List Cycle

Merge Two Sorted Lists

Merge two sorted linked lists and return as a single sorted list, splicing nodes (no new node creation needed).

Allocate a dummy head node so you don't need a special case for the very first node attached. Keep a tail pointer at dummy. Walk both lists with pointers a and b: at each step, splice whichever has the smaller value into tail.next, then advance that pointer and move tail forward. When one list runs out, attach the remainder of the other in one step. Return dummy.next.

Merge Two Sorted Lists

Merge K Sorted Lists

Given an array of k sorted linked lists, merge them into one sorted list. Pairwise merge (divide & conquer) is O(N log k).

Naively merging the lists one by one is O(N·k); we can do O(N log k) by merging in pairs and halving the list count each round. In each round, walk through the lists array merging i with i+1 (or with null if odd), producing half as many lists. Repeat until one list remains. The merge subroutine is just standard 'merge two sorted lists'. Each node is touched O(log k) times across all rounds.

Merge K Sorted Lists

Remove Nth Node From End

Given the head of a linked list, remove the nth node from the end and return the head. Use two pointers: advance fast n+1 steps first.

Use a dummy node before head so removing the actual head isn't a special case. Set both fast and slow pointers at dummy. Advance fast by n + 1 steps. Then move both at the same pace until fast becomes null — at that moment slow sits exactly one node BEFORE the target. Splice it out with slow.next = slow.next.next, return dummy.next.

Remove Nth Node From End

Reorder List

Given L0->L1->...->Ln-1, reorder it to L0->Ln-1->L1->Ln-2->L2->Ln-3->... in place. Steps: find middle, reverse second half, weave the two halves.

Three steps. (1) Find the middle of the list with slow/fast pointers — slow lands on the midpoint when fast hits the end. (2) Detach the second half and reverse it in place. (3) Weave the two halves together: take one node from the front, then one from the (now-reversed) back, alternating, until done. Each phase is O(n) and uses O(1) extra space.

Reorder List

Set Matrix Zeroes

Given an m x n matrix, if a cell is 0, set its entire row and column to 0 — in place. Use the first row/col as markers; track them separately.

Naively you'd allocate two extra arrays (length m and n) to record which rows and columns to zero out. To do it in O(1) extra space, repurpose the matrix's own first row and first column as those markers. But first you have to remember separately whether the original first row and first column themselves contained any zeros (since you're about to overwrite them as markers). Then walk the rest of the matrix marking, then walk again zeroing based on the markers, and finally zero out the first row and column themselves if needed.

Set Matrix Zeroes

Spiral Matrix

Given an m x n matrix, return all elements in spiral order (right, down, left, up — repeat). Track top/bottom/left/right boundaries.

Maintain four boundary variables: top, bottom, left, right. Repeatedly traverse one layer in four directions: left-to-right along the top row (then top++), top-to-bottom down the right column (then right--), right-to-left along the bottom row (then bottom--), and bottom-to-top up the left column (then left++). After each direction, shrink that boundary inward. Stop when the boundaries cross. Guard the bottom and left passes with extra checks for the case where they collapse to a single row or column.

Spiral Matrix

Rotate Image

Rotate an n x n matrix 90 degrees clockwise in place. Trick: transpose, then reverse each row.

Rotating a square matrix 90° clockwise can be done with two simple in-place passes. Pass 1, transpose: swap matrix[i][j] with matrix[j][i] for every pair where i < j. This mirrors the matrix across its main diagonal (top-left to bottom-right). Pass 2, reverse each row left-to-right. The composition of those two operations is exactly a 90° clockwise rotation. Sketch it once on a 3×3 grid and the transformation becomes obvious; both passes are O(n²) time and O(1) extra space.

Rotate Image

Word Search

Given an m x n grid of letters and a word, return true if the word can be constructed from sequentially adjacent cells. The same cell may not be used twice.

From each cell, try DFS searching for the word starting at index 0. At each step, check bounds, that the cell matches word[k], and that you haven't already used this cell on the current path. To avoid an extra visited array, temporarily overwrite the cell with a sentinel ('#') before recursing into the four neighbours, then restore it after the recursion returns — classic backtracking. If recursion ever succeeds (k reaches word.length), return true; otherwise undo the mark and let the next start cell try.

Word Search

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters. Sliding window with a Map of last-seen indices.

Use a sliding window defined by two indices l (left edge) and r (right edge), both starting at 0. Also keep a hash map that remembers, for each character, the most recent index where you saw it. Move r forward one step at a time. When you encounter s[r], check the map: if you've seen this character at some position p that's still inside the window (p >= l), the window now contains a duplicate — slide l forward to p + 1 to kick the old occurrence out. Then update the map with s[r]'s new index, and update your best answer with the current window length r - l + 1. Each character is visited at most twice (once by r, once by l), so it's O(n).

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Given string s and integer k, you may replace at most k characters with any letter. Return the length of the longest substring containing the same letter.

Slide a window [l, r] and within it count the frequency of every letter. Track maxCount — the highest frequency in the current window. The minimum number of characters you'd have to change to make the whole window one letter is windowSize - maxCount. If that exceeds k, the window is too big; shrink it by advancing l (and decrementing the leaving character's count). Otherwise it's valid — update your best length. You don't need to recompute maxCount after shrinking; only growing the window can ever beat the current best, and a stale max can't lead to wrong answers.

Longest Repeating Character Replacement

Minimum Window Substring

Given strings s and t, return the minimum window substring of s such that every character in t (including counts) is included in the window. Sliding window + counts.

Build a 'need' map of each character in t with its required count. Slide a window [l, r] over s and a 'window' map of counts inside it. Track 'have' = how many distinct characters have reached their required count. Expand r; whenever a character's window count hits its needed count, have++. Once have equals the number of distinct required chars, the window is feasible — try shrinking from the left to find the smallest such window, updating the best length each time. Keep shrinking until the window stops being feasible (some character drops below its need), then resume expanding r.

Minimum Window Substring

Valid Anagram

Given two strings s and t, return true if t is an anagram of s. Compare character counts.

If the lengths differ, they can't be anagrams. Otherwise walk both strings together with one int[26] array — increment for each char of s, decrement for each char of t at the same loop index. After the pass, if the two strings are anagrams, every counter ended up at zero. Any non-zero entry signals a mismatch.

Valid Anagram

Group Anagrams

Given an array of strings, group the anagrams together. Use a sorted version of each string as the bucket key.

Two strings are anagrams iff sorting their characters produces the same string. So use the sorted version of each string as a hash-map key and bucket the original strings under it. One pass: for each input, sort its characters, look up (or create) the bucket, append the original. Return all buckets. Sorting each string costs O(L log L); total is O(n · L log L) where L is the average length.

Group Anagrams

Valid Parentheses

Given a string of '()[]{}', determine if the input has properly matched and nested brackets.

Use a stack. On every opening bracket, push it onto the stack. On every closing bracket, pop the top of the stack: if it doesn't match the expected opener for that closer (or the stack is empty), the string is invalid. After the whole pass, the stack must also be empty — leftover openers mean unclosed brackets.

Valid Parentheses

Valid Palindrome

Given a string s, return true if it is a palindrome considering only alphanumeric characters and ignoring case.

Two pointers, l starting at 0 and r at the end. Advance each one inward, skipping any character that isn't a letter or digit. When both land on alphanumeric characters, compare them case-insensitively — if they differ, return false. Otherwise step both inward and repeat until they meet.

Valid Palindrome

Longest Palindromic Substring

Given a string s, return the longest palindromic substring. Expand around each center (odd and even).

Every palindromic substring has a center. There are 2n - 1 candidate centers: n single characters (odd-length palindromes) and n - 1 pairs of adjacent characters (even-length palindromes). For each center, expand outward as long as the characters on both sides match — this finds the longest palindrome centered there in O(n). Track the best across all centers.

Longest Palindromic Substring

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it. Expand around centers and count.

Same expand-around-center idea as Longest Palindromic Substring, but instead of tracking the longest, count every successful expansion. From each of the 2n - 1 candidate centers, every step outward where the two characters match adds one more palindrome to the count.

Palindromic Substrings

Encode and Decode Strings

Design an algorithm to encode a list of strings to one string and decode it back. Length-prefix each string with a delimiter, e.g. '5#hello'.

Encode each string as 'length#string'. The length tells the decoder exactly how many characters to read for that string — so the strings themselves can contain any character, including '#', without ambiguity. Decoding: scan forward to find the next '#', parse the number before it as the length, then take exactly that many characters as the next string. Repeat until you've consumed the input.

Encode and Decode Strings

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

An empty tree has depth 0. Otherwise the depth of the tree rooted at this node is 1 (for itself) plus the maximum depth of its two subtrees. That's the entire algorithm — the recursion does the work.

Maximum Depth of Binary Tree

Same Tree

Given the roots of two binary trees p and q, return true if they are structurally identical and the nodes have the same values.

Two trees are the same iff: both are null (base case true), OR both are non-null AND have the same value AND their left subtrees are the same AND their right subtrees are the same. Recurse on both pairs simultaneously.

Same Tree

Invert Binary Tree

Given the root of a binary tree, invert the tree (mirror it) and return its root.

Recursively invert the left and right subtrees first, then swap them at the current node. This effectively mirrors the entire tree across its vertical axis. Equivalently: just swap children at every node — the order doesn't matter as long as each node ends up with its children flipped.

Invert Binary Tree

Binary Tree Maximum Path Sum

A path is any sequence of nodes connected by edges. Return the maximum sum of any non-empty path. Track best at each node; return 'gain' upward.

Two values matter at each node. (a) The best path sum that PASSES THROUGH this node and uses BOTH children — this might be the global answer, but it can't propagate upward, since a path can only enter a parent from one side. (b) The best path sum a parent can extend through this node — uses at most ONE child (whichever has the larger gain). Recurse to get both children's gainable sums, clamp negatives to 0 (a negative gain is worse than not extending), update the global best with node.val + leftGain + rightGain, and return node.val + max(leftGain, rightGain) for the parent to consume.

Binary Tree Maximum Path Sum

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values (BFS).

Standard BFS with a queue, but to know where each level ends, snapshot the queue size at the start of every level — that's exactly the count of nodes belonging to this level. Pop exactly that many, collect their values into one list, and enqueue all their children for the next level. Repeat until the queue is empty.

Binary Tree Level Order Traversal

Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree to a string and deserialize it back. Preorder DFS with '#' for null works well.

Serialize via preorder DFS, emitting each node's value (and a sentinel like '#' for nulls) separated by commas. The null markers are crucial — they tell the deserializer where each subtree ends. Deserialize by tokenising the string and recursively rebuilding: read the next token; if it's '#' return null, otherwise create a node and recurse to fill in its left then right children.

Serialize and Deserialize Binary Tree

Subtree of Another Tree

Given roots root and subRoot, return true if subRoot has the same structure & values as some subtree of root.

At every node of the main tree, ask 'is this node the root of a subtree identical to subRoot?' using a standard same-tree comparison. If yes, return true. Otherwise recurse into the left and right children. The same-tree check is O(size of sub) and you do it at each of the O(n) main nodes — O(n · m) overall.

Subtree of Another Tree

Construct Tree from Preorder & Inorder

Given preorder and inorder traversals of a binary tree (with unique values), reconstruct and return the tree. preorder[0] is the root; locate it in inorder to split left/right.

Preorder visits the root before its subtrees, so preorder[0] is the root. In inorder, the root's position splits the array into the left subtree (everything before) and the right subtree (everything after). Recurse: build the left subtree from the left part of inorder, advancing through preorder; then build the right subtree from the right part. Pre-build a HashMap of value → inorderIndex so each split is O(1) instead of O(n) — that drops total time from O(n²) to O(n).

Construct Tree from Preorder & Inorder

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid BST. Pass an open (lo, hi) range down recursively.

The naive check — 'for each node, is its left child smaller and right child larger?' — is wrong, because a node deep in the left subtree can still be larger than an ancestor higher up and the local check would miss it. The correct approach is to track an open range (lo, hi) that every node's value must fall strictly inside. Start the recursion at the root with the range (-∞, +∞). When you recurse into the left child, the new range is (lo, node.val) — the left subtree must be smaller than the current node. When you recurse right, it's (node.val, hi). If any node ever falls outside its inherited range, the tree is not a valid BST.

Validate Binary Search Tree

Kth Smallest Element in a BST

Given the root of a BST and an integer k, return the kth smallest value (1-indexed). Iterative inorder traversal.

An inorder traversal of a BST visits values in sorted order, so the kth value visited is the answer. Do it iteratively with an explicit stack: walk left as far as possible, pushing nodes; then pop the top, decrement k, and if k hits zero return that node's value; otherwise move into its right subtree and continue. Stops as soon as you've found it — average case faster than visiting all nodes.

Kth Smallest Element in a BST

Lowest Common Ancestor of BST

Given a BST and two nodes p and q, return their lowest common ancestor. Walk down: when p and q split, that node is the LCA.

Walk down from the root. At each node, compare its value to both p.val and q.val. If both targets are smaller, the LCA is in the left subtree — descend left. If both are larger, descend right. The first time the values 'split' (one ≤ this node and the other ≥, or one equals it), this node IS the LCA — return it. O(h) without any extra space.

Lowest Common Ancestor of BST

Implement Trie (Prefix Tree)

Implement a Trie with insert(word), search(word), and startsWith(prefix) operations.

Each node has up to 26 children (one per lowercase letter) and a boolean 'end' flag. insert: walk character by character, creating missing children as you go; mark the final node as end. search: walk through; if any expected child is missing return false; at the end, return whether the final node has end == true. startsWith is the same walk but it ignores the end flag — just needing the path to exist is enough. All operations are O(L) where L is the word/prefix length.

Implement Trie (Prefix Tree)

Add and Search Word

Design WordDictionary supporting addWord and search where '.' matches any letter. DFS over a Trie when '.' is encountered.

Same Trie structure as the basic Implement Trie. addWord is identical. The twist is search: when the search character is '.', it matches any letter, so you have to try EVERY existing child at that node and recurse — return true if any branch succeeds. For a normal letter, just descend that one branch as usual. The wildcard branching is what forces a recursive (DFS) search instead of a simple walk.

Add and Search Word

Word Search II

Given a board of letters and a list of words, return all words that can be formed in the board. Build a Trie of the words and DFS once.

Naively running Word Search once per query word is O(words × m·n·4^L). Build a Trie containing all the words, then DFS once from each cell, walking the Trie in lockstep — at each step, the current Trie node tells you which letters are even worth trying next. When you reach a Trie node that marks the end of a word, record it (and clear the marker so the same word isn't recorded twice). Standard backtracking on the board: replace the current cell with '#' before recursing, restore it after.

Word Search II

Top K Frequent Elements

Given nums and integer k, return the k most frequent elements. Bucket sort by frequency for O(n).

First, count how many times each number appears using a hash map. The key observation: any frequency must be between 1 and n (the array length). So allocate n + 1 buckets, where bucket[f] holds every value that appears exactly f times. Walk those buckets from the highest index downward and pull values into your answer until you have k of them. This avoids both sorting (O(n log n)) and a heap (O(n log k)), giving you a flat O(n) algorithm because the bucket index IS the frequency — no comparisons needed.

Top K Frequent Elements

Find Median from Data Stream

Design MedianFinder with addNum(num) and findMedian(). Maintain a max-heap (lower half) and min-heap (upper half), kept balanced.

Maintain two heaps balanced at the median: a max-heap (lo) holding the smaller half of the numbers, and a min-heap (hi) holding the larger half. Invariant: lo's size is always either equal to hi's size or one greater. To addNum: push into lo, then move lo's max into hi (this guarantees lo's max ≤ hi's min); rebalance by moving one back if hi got bigger than lo. To findMedian: if lo has more elements, the median is lo's max; otherwise it's the average of lo's max and hi's min. Each insert is O(log n); the median query is O(1).

Find Median from Data Stream