150 coding interview problems, by pattern
The problems interviewers ask most, grouped by the pattern that solves them. Each one has the key idea and its complexity; open the animated lesson to see the pattern run, or solve it in the browser editor.
Arrays and hashing
Two Sum Easy
Return the indices of two numbers that add up to a target.
Key idea: Walk the array once. For each number, look up target minus it in a dictionary of values seen so far, then store the current one.
Contains Duplicate Easy
Decide whether any value appears at least twice.
Key idea: Add each value to a HashSet. HashSet.Add returns false the moment a value repeats.
Valid Anagram Easy
Decide whether two strings use exactly the same letters.
Key idea: Count letters up for the first string and down for the second. Any counter below zero means no.
Group Anagrams Medium
Group words that are anagrams of each other.
Key idea: Use a dictionary keyed by a canonical form of each word: its sorted letters, or its 26 letter counts joined into a string.
Top K Frequent Elements Medium
Return the k values that occur most often.
Key idea: Count frequencies in a dictionary, then keep a min-heap of size k keyed by count. Bucket sort by count gives O(n).
Product of Array Except Self Medium
For each index, return the product of every other element, without division.
Key idea: Two passes: fill the result with prefix products from the left, then multiply by a running suffix product from the right.
Longest Consecutive Sequence Medium
Find the length of the longest run of consecutive integers in an unsorted array.
Key idea: Put everything in a HashSet. Only start counting from a number whose predecessor is absent, so each run is walked once.
Subarray Sum Equals K Medium
Count contiguous subarrays whose sum is k.
Key idea: Keep a running sum and a dictionary of how often each running sum has occurred. Add the count for sum minus k at every step.
Majority Element Easy
Find the value that appears more than half the time.
Key idea: Boyer-Moore voting: keep one candidate and a counter, cancel it against every different value.
Sort Colors Medium
Sort an array of 0s, 1s and 2s in place in one pass.
Key idea: Dutch national flag: three pointers split the array into zeros, ones, unknown and twos.
Maximum Subarray Medium
Find the contiguous subarray with the largest sum.
Key idea: Kadane: at each element either extend the running sum or restart from this element, and track the best seen.
Rotate Array Medium
Rotate an array to the right by k steps, in place.
Key idea: Reverse the whole array, then reverse the first k elements and the remaining n − k elements separately.
Find All Duplicates in an Array Medium
Values are between 1 and n and each appears once or twice; return every value that appears twice.
Key idea: Use each value as an index: walk the array and negate the number at index |value| − 1. A value whose slot is already negative is a duplicate.
First Missing Positive Hard
Find the smallest positive integer that is not in the array.
Key idea: Place every in-range value v at index v − 1 by swapping, then scan for the first index whose value is not index + 1.
Valid Sudoku Medium
Decide whether a partially filled 9x9 Sudoku board has no repeated digit in any row, column or 3x3 box.
Key idea: Keep a set per row, column and box. Walk every filled cell once and fail the moment a digit repeats in one of its three sets.
Subarray Sums Divisible by K Medium
Count contiguous subarrays whose sum is divisible by k.
Key idea: Keep a running sum mod k and a dictionary of how often each remainder has occurred so far. Add the count for the current remainder at every step, the same trick as counting subarrays that sum to k.
Move Zeroes Easy
Move every 0 to the end of the array while keeping the order of the other elements, in place.
Key idea: Two pointers: scan and swap every nonzero value into the next open slot from the left, pushing zeros toward the back as you go.
Two pointers
Valid Palindrome Easy
Decide whether a string reads the same both ways, ignoring case and punctuation.
Key idea: Two pointers from the ends, skipping characters that are not letters or digits.
Two Sum II: Input Array Is Sorted Medium
Find two numbers in a sorted array that add up to a target, in constant space.
Key idea: Pointers at both ends. Sum too small moves the left one, too large moves the right one.
3Sum Medium
Find all unique triplets that sum to zero.
Key idea: Sort, fix one number, and run the two-pointer pair search on the rest. Skip equal neighbours to avoid duplicate triplets.
Container With Most Water Medium
Pick two lines that hold the most water between them.
Key idea: Start with the widest container and always move the shorter line inward, since moving the taller one can never help.
Trapping Rain Water Hard
Compute how much water is trapped between bars after rain.
Key idea: Water above a bar is min(max to its left, max to its right) minus its height. Two pointers track both maxima in one pass.
Valid Palindrome II Easy
Decide whether a string can become a palindrome after deleting at most one character.
Key idea: Two pointers from the ends. On a mismatch, try skipping either the left or the right character and check that what remains is a palindrome.
Next Permutation Medium
Rearrange numbers into the next lexicographically greater permutation, or the lowest order if none exists.
Key idea: Scan from the right for the first dip, swap it with the smallest larger value to its right, then reverse everything after it.
Reverse Vowels of a String Easy
Reverse only the vowels of a string, leaving every other character where it is.
Key idea: Two pointers from both ends, each skipping past consonants, swapping whenever both sit on a vowel.
Squares of a Sorted Array Easy
Return the squares of a sorted array's values, themselves sorted in ascending order.
Key idea: The largest square is always at one of the two ends. Two pointers close in from both sides, filling the result from the back.
Boats to Save People Medium
Find the minimum number of boats to carry everyone, each boat holding at most two people within a weight limit.
Key idea: Sort by weight. Pair the lightest remaining person with the heaviest if they fit together, otherwise send the heaviest alone; either way move the right pointer in.
Is Subsequence Easy
Decide whether one string's characters appear in another string in the same order.
Key idea: Two pointers: advance through the longer string, and advance through the shorter one only on a match. The shorter string is a subsequence exactly when it is fully consumed.
Sliding window
Best Time to Buy and Sell Stock Easy
Find the best profit from one buy followed by one sell.
Key idea: Track the lowest price so far and the best profit if you sold today.
Longest Substring Without Repeating Characters Medium
Find the longest substring with all distinct characters.
Key idea: Grow a window on the right. When a character repeats inside the window, jump the left edge past its previous position.
Longest Repeating Character Replacement Medium
Find the longest substring that can become one repeated letter with at most k replacements.
Key idea: A window is valid while its length minus the count of its most common letter is at most k. Shrink from the left when it is not.
Minimum Window Substring Hard
Find the smallest window of s that contains every character of t.
Key idea: Expand right until all required counts are met, then shrink left while the window stays valid, recording the smallest.
Sliding Window Maximum Hard
Report the maximum of every window of size k.
Key idea: Keep a deque of indices with decreasing values. Drop smaller values from the back and expired indices from the front.
Longest Palindromic Substring Medium
Find the longest substring that reads the same forwards and backwards.
Key idea: Expand around every center, one index at a time and one gap between two indices at a time, tracking the longest palindrome found.
Permutation in String Medium
Decide whether s2 contains a contiguous substring that is a permutation of s1.
Key idea: Slide a window the length of s1 across s2, keeping letter counts for the window. Shift the count by one character per step instead of recomputing it.
Fruit Into Baskets Medium
Pick the longest contiguous run of trees that uses at most two fruit types.
Key idea: Grow a window while a dictionary of counts holds at most two distinct values, and shrink from the left the moment a third type appears.
Minimum Size Subarray Sum Medium
Find the length of the shortest contiguous subarray whose sum is at least target, or 0 if none exists.
Key idea: Grow a window adding to a running sum. While the sum already meets the target, shrink from the left and record the smallest length.
Max Consecutive Ones III Medium
Find the longest subarray of 1s obtainable by flipping at most k zeros to 1.
Key idea: Grow a window counting the zeros inside it, and shrink from the left whenever that count exceeds k.
Stack
Valid Parentheses Easy
Decide whether brackets are closed in the correct order.
Key idea: Push openers. On a closer, the top of the stack must be its matching opener. The stack must be empty at the end.
Min Stack Medium
Design a stack that returns its minimum in constant time.
Key idea: Store, with each pushed value, the minimum of the stack at that moment (a second stack or a tuple).
Evaluate Reverse Polish Notation Medium
Evaluate an expression in postfix form.
Key idea: Push numbers. An operator pops two values, applies itself and pushes the result. Mind the operand order.
Daily Temperatures Medium
For each day, find how many days until a warmer one.
Key idea: Monotonic stack of indices waiting for a warmer day. A warmer day resolves everything colder on top.
Largest Rectangle in Histogram Hard
Find the largest rectangle that fits under a histogram.
Key idea: Monotonic increasing stack. When a shorter bar arrives, pop taller bars and compute the area each one spans.
Decode String Medium
Decode a run-length encoded string such as 3[a2[c]] into its expanded form.
Key idea: Push the string built so far and its repeat count onto a stack at every '[', then pop and repeat the inner string when a ']' closes the group.
Asteroid Collision Medium
Simulate asteroids moving left or right until no more collisions can happen.
Key idea: Keep a stack of surviving right-moving asteroids. A left-moving asteroid pops smaller right-movers until it stops, is destroyed, or the stack empties.
Remove K Digits Medium
Remove k digits from a number so the digits that remain form the smallest possible number.
Key idea: Monotonic increasing stack of digits. Pop a larger digit on top whenever a smaller one arrives and removals remain, then strip leading zeros.
Online Stock Span Medium
Design a class that reports, for each day's price, how many consecutive days up to today had a price no higher than today's.
Key idea: Keep a monotonic stack of (price, span) pairs. Pop every entry whose price is no higher than today's and fold its span into today's before pushing.
Basic Calculator II Medium
Evaluate a string expression of non-negative integers with + - * / and no parentheses.
Key idea: Walk the string with a running operator. Push each number, or combine it with the stack top for * and /, then sum the stack once the string is used up.
Implement Queue using Stacks Easy
Build a FIFO queue using only two stacks.
Key idea: Push onto an input stack. To pop or peek, move everything to an output stack only when that one is empty, which reverses the order back to FIFO.
Binary search
Binary Search Easy
Find a target in a sorted array.
Key idea: Halve the range by comparing with the middle element. Use lo + (hi - lo) / 2 for the midpoint.
Search in Rotated Sorted Array Medium
Find a target in a sorted array that has been rotated.
Key idea: At every step one half is still sorted. Check whether the target lies in that half, otherwise search the other.
Find Minimum in Rotated Sorted Array Medium
Find the smallest element of a rotated sorted array.
Key idea: Compare the middle with the right end. If it is larger, the minimum is to the right, otherwise it is at mid or to the left.
Koko Eating Bananas Medium
Find the slowest eating speed that finishes all piles within h hours.
Key idea: Binary search on the answer: for a given speed, total hours is easy to compute and decreases as speed rises.
Median of Two Sorted Arrays Hard
Find the median of two sorted arrays in logarithmic time.
Key idea: Binary search a partition of the smaller array so that everything on the left of both partitions is no larger than everything on the right.
Search a 2D Matrix Medium
Search for a target value in a matrix whose rows are each sorted and whose first entry is greater than the previous row's last.
Key idea: Treat the matrix as one sorted array and binary search it, mapping the midpoint index back to a row and a column.
Find Peak Element Medium
Find the index of any peak element, one strictly greater than both its neighbours.
Key idea: Binary search toward the side that is still rising: a middle smaller than its right neighbour means a peak lies to the right, otherwise it lies at or before the middle.
Time Based Key-Value Store Medium
Design a store where a key can hold several timestamped values, and a query returns the value set at the latest timestamp not after the one asked for.
Key idea: Keep each key's values in a list ordered by timestamp and binary search that list for the latest timestamp no greater than the query.
Capacity To Ship Packages Within D Days Medium
Find the smallest ship capacity that lets all packages, loaded in order, ship within a given number of days.
Key idea: Binary search on the capacity itself: a greedy pass counts the days a candidate capacity needs, and more capacity never needs more days.
Find First and Last Position of Element in Sorted Array Medium
Find the first and last index of a target value in a sorted array, or [-1, -1] if it is absent.
Key idea: Binary search twice: once biased to keep going left on a match to find the first index, once biased to keep going right to find the last.
Linked list
Reverse Linked List Easy
Reverse a singly linked list.
Key idea: Walk with prev and curr, saving next before pointing curr back at prev.
Merge Two Sorted Lists Easy
Merge two sorted linked lists into one.
Key idea: Use a dummy head and always attach the smaller front node. Attach the leftover list at the end.
Linked List Cycle Easy
Detect whether a linked list has a cycle.
Key idea: Fast and slow pointers: if they ever land on the same node there is a cycle.
Remove Nth Node From End of List Medium
Delete the n-th node from the end in one pass.
Key idea: Move a fast pointer n steps ahead, then advance both until fast reaches the end. A dummy node handles removing the head.
Reorder List Medium
Reorder L0, L1, ..., Ln into L0, Ln, L1, Ln-1, ...
Key idea: Find the middle with fast and slow pointers, reverse the second half, then weave the two halves together.
LRU Cache Medium
Design a cache that evicts the least recently used entry, with O(1) get and put.
Key idea: Dictionary from key to node, plus a doubly linked list ordered by recency. Move a node to the front on every access.
Merge k Sorted Lists Hard
Merge k sorted linked lists.
Key idea: Put the head of each list in a min-heap, repeatedly take the smallest and push its successor.
Add Two Numbers Medium
Add two non-negative integers given as linked lists of digits in reverse order, and return the sum the same way.
Key idea: Walk both lists together, adding digit by digit plus a running carry and appending each result digit to a new list, until both lists and the carry are exhausted.
Palindrome Linked List Easy
Decide whether a singly linked list reads the same forwards and backwards.
Key idea: Find the middle with fast and slow pointers, reverse the second half in place, then walk both halves together comparing values.
Sort List Medium
Sort a linked list in ascending order.
Key idea: Merge sort: split the list in half at the middle, sort each half recursively, then merge the two sorted halves.
Reverse Linked List II Medium
Reverse only the nodes from position left to position right (1-indexed), in one pass.
Key idea: Walk to the node just before left, then repeatedly pull the next node out and splice it in right after that anchor, growing the reversed section one node at a time.
Odd Even Linked List Medium
Group all odd-indexed nodes together followed by all even-indexed nodes (1-indexed), keeping the relative order inside each group.
Key idea: Keep two running tails, one for odd positions and one for even positions, threading each new node onto the matching tail, then attach the even chain after the odd chain.
Swap Nodes in Pairs Medium
Swap every two adjacent nodes and return the head of the modified list.
Key idea: Use a dummy head and, two nodes at a time, rewire the pointers so the pair swaps places - only the links move, never the values.
Trees and tries
Invert Binary Tree Easy
Mirror a binary tree.
Key idea: Swap the children of every node, recursively.
Maximum Depth of Binary Tree Easy
Find the height of a binary tree.
Key idea: Height of a node is 1 plus the larger of its children's heights. An empty tree has height 0.
Binary Tree Level Order Traversal Medium
Return node values level by level.
Key idea: BFS with a queue. Read the queue size at the start of each round to know where the level ends.
Validate Binary Search Tree Medium
Decide whether a tree is a valid BST.
Key idea: Pass down an allowed (low, high) range, or check that an inorder traversal is strictly increasing.
Lowest Common Ancestor of a BST Medium
Find the lowest common ancestor of two nodes in a BST.
Key idea: Walk down from the root while both keys are on the same side. The first split point is the answer.
Kth Smallest Element in a BST Medium
Find the k-th smallest key in a BST.
Key idea: Inorder traversal visits keys in sorted order. Stop at the k-th visit.
Binary Tree Maximum Path Sum Hard
Find the largest sum along any path in a binary tree.
Key idea: Postorder: each node returns its best one-sided gain, while the best path through the node (left + node + right) updates a global maximum.
Serialize and Deserialize Binary Tree Hard
Convert a tree to a string and back.
Key idea: Preorder with a marker for null children. Rebuild by reading tokens in the same order.
Implement Trie (Prefix Tree) Medium
Build a structure that supports insert, search and startsWith.
Key idea: Each node has up to 26 children and an end-of-word flag. Follow one child per character.
Diameter of Binary Tree Easy
Find the length of the longest path between any two nodes in a binary tree.
Key idea: Post-order: each node returns its height, while the best diameter seen so far is updated with left height plus right height at every node.
Balanced Binary Tree Easy
Decide whether every node's left and right subtrees differ in height by at most 1.
Key idea: Compute height bottom-up and return -1 the instant a subtree is found unbalanced, so no extra work is wasted.
Same Tree Easy
Decide whether two binary trees are structurally identical with the same node values.
Key idea: Compare the two roots, then recursively compare their left children to each other and their right children to each other.
Symmetric Tree Easy
Decide whether a binary tree is a mirror of itself around its center.
Key idea: Compare the left and right subtrees of the root like two different trees, but cross sides: left's left against right's right, left's right against right's left.
Path Sum Easy
Decide whether a root-to-leaf path sums to a given target.
Key idea: Subtract each node's value from the target while descending, so at a leaf the question is only whether what's left equals the leaf's value.
Lowest Common Ancestor of a Binary Tree Medium
Find the lowest common ancestor of two nodes in a binary tree that is not necessarily a BST.
Key idea: Search both subtrees for p and q; if each side finds one, the current node is the answer, otherwise pass up whichever side found something.
Binary Tree Right Side View Medium
Return the value of the rightmost node at every level, top to bottom.
Key idea: BFS level by level, reading the queue size at the start of each round, and keep only the last node dequeued from each level.
Heaps
Kth Largest Element in an Array Medium
Find the k-th largest value.
Key idea: Keep a min-heap of size k. Its minimum is the answer. Quickselect gives O(n) on average.
Find Median from Data Stream Hard
Support adding numbers and reading the median at any time.
Key idea: Two heaps: a max-heap for the lower half and a min-heap for the upper half, kept within one element of each other.
K Closest Points to Origin Medium
Return the k points closest to the origin.
Key idea: Keep a max-heap of size k keyed by squared distance, and evict the farthest point whenever it grows past k. Squared distances keep the same order without square roots.
Last Stone Weight Easy
Repeatedly smash the two heaviest stones together and report the weight of the last stone left.
Key idea: Put every stone in a max-heap. Pop the two heaviest and push back their difference if it is not zero. Stop at one stone or none.
Task Scheduler Medium
Find the fewest intervals needed to run all tasks when two equal tasks need at least n intervals between them.
Key idea: Greedy: each tick run the task with the highest remaining count from a max-heap, then park it in a cooldown queue for n ticks. Idle when nothing is ready.
Top K Frequent Words Medium
Return the k most frequent words, with ties broken alphabetically.
Key idea: Count each word, then keep a min-heap of size k ordered by count, where the later word loses a tie. Pop it and reverse for the final order.
Kth Largest Element in a Stream Easy
Design a class that returns the k-th largest value after every new number is added.
Key idea: Keep a min-heap of size k. Its minimum is the k-th largest, so each add pushes the value and pops the minimum when the heap grows past k.
Backtracking
Subsets Medium
Generate every subset of a set of distinct numbers.
Key idea: Backtrack: record the current path, then for each later element choose it, recurse and undo.
Permutations Medium
Generate every ordering of distinct numbers.
Key idea: Backtrack over positions, tracking which elements are already used.
Combination Sum Medium
Find all combinations that sum to a target, reusing numbers freely.
Key idea: Backtrack with a start index. Recurse with the same index to reuse a number, and stop when the remaining target goes negative.
Word Search Medium
Decide whether a word can be traced through adjacent cells of a grid.
Key idea: DFS from every cell, marking cells on the current path as visited and unmarking them on the way back.
N-Queens Hard
Place n queens on an n by n board so that none attack each other.
Key idea: Place row by row. Track used columns and both diagonal directions so a safety check is O(1).
Palindrome Partitioning Medium
Split a string into pieces that are all palindromes, and return every way to do it.
Key idea: Backtrack over cut points: try every prefix of what is left, and only recurse past it when that prefix is a palindrome.
Letter Combinations of a Phone Number Medium
Return every letter combination that a string of digits 2-9 could spell on a phone keypad.
Key idea: Backtrack one digit at a time: for each letter the current digit maps to, append it to the path and recurse on the next digit.
Generate Parentheses Medium
Generate every well-formed string made of n pairs of parentheses.
Key idea: Track how many opens and closes are placed. Add an open while open < n and a close only while close < open, so every path is valid by construction.
Subsets II Medium
Generate every subset of an array that may contain duplicates, with no duplicate subsets in the result.
Key idea: Sort first so equal values sit together. Backtrack with a start index, and skip a value equal to the one just tried at the same depth.
Combination Sum II Medium
Find all combinations that sum to a target when each number may be used at most once and the input may contain duplicates.
Key idea: Sort, then backtrack with a start index that always moves forward (i + 1). Skip a value equal to the one just tried at the same depth so no combination repeats.
Graphs
Number of Islands Medium
Count connected groups of land in a grid.
Key idea: Scan the grid. On unvisited land, count one island and flood fill it with DFS or BFS.
Clone Graph Medium
Deep-copy a connected undirected graph.
Key idea: Traverse with DFS or BFS, keeping a dictionary from each original node to its copy.
Course Schedule Medium
Decide whether all courses can be finished given prerequisites.
Key idea: It is cycle detection in a directed graph. Kahn's topological sort must output every node.
Rotting Oranges Medium
Find how many minutes until every orange is rotten.
Key idea: Multi-source BFS: start with all rotten oranges in the queue and count levels.
Network Delay Time Medium
Find how long a signal takes to reach every node in a weighted graph.
Key idea: Dijkstra from the source. The answer is the largest shortest distance, or -1 if a node is unreachable.
Word Ladder Hard
Find the shortest chain of one-letter changes between two words.
Key idea: BFS where neighbours are words one letter apart. Generate neighbours by trying each letter at each position.
Number of Connected Components in an Undirected Graph Medium
Count the connected groups in an undirected graph of n nodes.
Key idea: Union-Find: union the two ends of every edge. Each successful union merges two groups, so start at n and subtract one per merge.
Redundant Connection Medium
A tree had one extra edge added. Find the edge to remove so it is a tree again.
Key idea: Union-Find over the edges in order. The first edge whose two ends already share a root closes the cycle, so it is the answer.
Graph Valid Tree Medium
Decide whether n nodes and a list of undirected edges form a valid tree.
Key idea: A tree has exactly n - 1 edges and no cycle. Check the count, then union every edge: a union of two nodes already joined means a cycle.
Pacific Atlantic Water Flow Medium
Find every cell whose rain water can reach both the Pacific and the Atlantic ocean.
Key idea: Search backwards from each ocean's border cells, stepping only to neighbours at least as high. Return the cells both searches reach.
Surrounded Regions Medium
Flip every region of 'O' that is fully surrounded by 'X' into 'X'.
Key idea: Only an 'O' linked to the border survives. Flood fill from every border 'O' to mark the survivors, then flip every unmarked 'O'.
Min Cost to Connect All Points Medium
Connect all points with the least total Manhattan distance.
Key idea: It is a minimum spanning tree on a complete graph. Prim's with a plain distance array picks the closest unjoined point n times.
Cheapest Flights Within K Stops Medium
Find the cheapest price from src to dst using at most k stops.
Key idea: Bellman-Ford limited to k + 1 rounds. Each round relaxes from a copy of the previous round's prices, so a path gains at most one edge per round.
Dynamic programming
Climbing Stairs Easy
Count the ways to climb n steps taking 1 or 2 at a time.
Key idea: dp[i] = dp[i-1] + dp[i-2]. Two variables are enough.
House Robber Medium
Maximise the sum of chosen values with no two adjacent.
Key idea: dp[i] = max(dp[i-1], dp[i-2] + value). Skip the house or take it.
Coin Change Medium
Find the fewest coins that make an amount.
Key idea: dp[x] = 1 + the smallest dp[x - coin] over all coins. Unreachable amounts stay at infinity.
Longest Increasing Subsequence Medium
Find the length of the longest strictly increasing subsequence.
Key idea: dp[i] = 1 + the best dp[j] for earlier smaller values. A sorted tails array with binary search gives O(n log n).
Longest Common Subsequence Medium
Find the length of the longest subsequence shared by two strings.
Key idea: 2D table. Matching characters extend the diagonal, otherwise take the better of dropping a character from either string.
Unique Paths Medium
Count paths from the top-left to the bottom-right of a grid, moving only right or down.
Key idea: Each cell is the sum of the cell above and the cell to its left.
Edit Distance Medium
Find the fewest inserts, deletes and replacements to turn one word into another.
Key idea: 2D table. Matching characters copy the diagonal, otherwise 1 plus the minimum of replace, delete and insert.
Word Break Medium
Decide whether a string can be split into dictionary words.
Key idea: dp[i] is true if some dictionary word ends at i and dp at its start is true.
Partition Equal Subset Sum Medium
Decide whether an array can be split into two parts with equal sums.
Key idea: It is 0/1 knapsack: can some subset reach half the total? Fill a boolean array from right to left.
Maximum Product Subarray Medium
Find the contiguous subarray with the largest product.
Key idea: Track both the running maximum and running minimum product ending here. A negative number flips them, so the smallest can become the largest.
Decode Ways Medium
Count the ways to decode a string of digits into letters, where 1 to 26 map to A to Z.
Key idea: dp[i] adds dp[i-1] when the last digit is not 0, and dp[i-2] when the last two digits form 10 to 26.
House Robber II Medium
Maximise the sum of chosen values with no two adjacent, when the houses form a circle.
Key idea: The first and last house are neighbours, so run the House Robber DP twice, once without the first and once without the last, and take the larger. A single house is a special case.
Longest Palindromic Subsequence Medium
Find the length of the longest palindromic subsequence of a string.
Key idea: 2D table over substrings. If the end characters match, add 2 to the inside answer, otherwise drop one end and take the better result.
Min Cost Climbing Stairs Easy
Find the cheapest way to reach the top of a staircase, taking 1 or 2 steps and starting from step 0 or 1.
Key idea: dp[i] = the cheaper of dp[i-1] + cost[i-1] and dp[i-2] + cost[i-2]. Two variables are enough.
Target Sum Medium
Count the ways to put + or - before each number so the total equals a target.
Key idea: The positives must sum to (total + target) / 2, so it becomes subset-sum counting. Return 0 if that value is negative or not a whole number.
Maximal Square Medium
Find the area of the largest square made only of 1s in a binary matrix.
Key idea: dp[i][j] = 1 + min(up, left, up-left) when the cell is 1, otherwise 0. The best dp value squared is the answer.
Intervals and greedy
Merge Intervals Medium
Merge all overlapping intervals.
Key idea: Sort by start. Extend the last merged interval while the next one starts before it ends.
Non-overlapping Intervals Medium
Remove the fewest intervals so the rest do not overlap.
Key idea: Greedy: sort by end time and keep every interval that starts after the last kept one ends.
Jump Game Medium
Decide whether you can reach the last index given maximum jump lengths.
Key idea: Track the farthest index reachable so far. If the current index is beyond it, you are stuck.
Insert Interval Medium
Insert a new interval into a sorted list of non-overlapping intervals, merging where needed.
Key idea: Walk the sorted list: copy the intervals that end before the new one starts, merge every interval that overlaps it, then copy the rest.
Meeting Rooms II Medium
Find the minimum number of rooms needed to hold all the meetings.
Key idea: Sort start times and end times separately and sweep. A meeting that starts at or after the earliest end reuses that room, otherwise open a new one.
Gas Station Medium
Find the station to start from to drive the whole circuit, or -1 if it is impossible.
Key idea: If total gas is at least total cost, an answer exists. Keep a running tank and restart from the next station whenever the tank goes negative.
Partition Labels Medium
Split a string into as many parts as possible so that each letter appears in at most one part.
Key idea: Record the last index of every letter. Extend the current part to the last index of each letter you meet, and cut when you reach that end.
Minimum Number of Arrows to Burst Balloons Medium
Find the fewest arrows, shot straight up, that burst every balloon given as an [xstart, xend] range.
Key idea: Greedy: sort by end. Shoot at the end of the first balloon, skip every balloon that starts at or before that point, then shoot again at the next one.
Bit manipulation
Number of 1 Bits Easy
Count the set bits of an integer.
Key idea: n &= n - 1 clears the lowest set bit. Count how many times you can do it.
Single Number Easy
Every value appears twice except one. Find it.
Key idea: XOR everything together. Pairs cancel to zero.
Counting Bits Easy
Return the number of set bits for every number from 0 to n.
Key idea: dp[i] = dp[i >> 1] + (i & 1): the count for half the number plus its lowest bit.
Reverse Bits Easy
Reverse the bits of a 32-bit unsigned integer.
Key idea: Peel the lowest bit off n and push it onto the result for 32 rounds: result = (result << 1) | (n & 1).
Missing Number Easy
Given n distinct numbers from 0 to n, find the one that is missing.
Key idea: XOR every index and every value together, plus n. Matching pairs cancel and the missing number is left.
Sum of Two Integers Medium
Add two integers without using the + or - operators.
Key idea: XOR adds without carrying and (a & b) << 1 is the carry. Repeat until the carry is zero, using 32-bit unsigned values so negatives work.
Power of Two Easy
Decide whether an integer is a power of two.
Key idea: A power of two has exactly one set bit, so n > 0 and n & (n - 1) == 0.
Hamming Distance Easy
Count the bit positions where two integers differ.
Key idea: XOR keeps a 1 exactly where the bits differ. Count the set bits of x ^ y.