Skip to content
Tutorials Center
My learning

Topics

Lesson 224 of 225 ยท Practice and Review

Practice Sets by Topic (Arrays, Trees, Graphs, DP)

Curated practice sets for arrays, trees, graphs and dynamic programming. Each problem has a difficulty, a hint and the pattern it trains, plus worked samples.

Knowing a technique and being fluent with it are different things. Fluency comes from solving the right problems in the right order. This lesson is a curated list: four topic sets, each with problems ordered from warm-up to hard, a one-line hint that nudges without spoiling, and the pattern each problem trains.

The problems are described in our own words and are classics you will meet again and again. Use the sets together with the study plan: after you read the lessons for a topic, work through its set, and log your misses for review. For fully solved problems with tests, see Practice Problems: Arrays, Strings and Hashing and Advanced Practice Problems.

How to use a set

  1. Read the statement and write two or three examples, including an edge case.
  2. Write the brute force in a sentence and state its cost.
  3. Try for 25 to 30 minutes before opening the hint.
  4. After solving, compare your complexity with the one in the hint column, and note the pattern.
  5. Re-solve every problem you needed help with, a week later, from a blank file.
flowchart TD
    A["Pick a set"] --> B["Easy problems first"]
    B --> C{"Solved in time?"}
    C -- yes --> D["Next problem"]
    C -- no --> E["Read the hint, then retry"]
    E --> F["Log in the review list"]
    F --> D
    D --> G["Finish the set, then mix topics"]

The loop for each set: attempt, hint if needed, log the miss, move on, and mix topics at the end.

Set 1: Arrays and strings

# Problem Level Hint Pattern
1 Find two numbers in an array that add up to a target Easy Store each value you have seen; look for target - x Hash map
2 Best day to buy and sell a stock once Easy Track the lowest price so far while scanning One pass, running minimum
3 Does any value appear twice? Easy A set answers membership in O(1) Sets
4 Product of all elements except self, without division Medium Combine a prefix product and a suffix product Prefix sums idea
5 Maximum sum subarray Medium Decide at each index: extend the run or restart Kadane
6 Longest substring without repeating characters Medium Grow a window; shrink from the left on a repeat Sliding window
7 Three numbers that sum to zero (no duplicate triples) Medium Sort, fix one, walk two pointers; skip equal values Two pointers
8 Merge overlapping intervals Medium Sort by start, then extend the last interval Sorting
9 Number of subarrays with sum equal to k Medium Count how often each prefix sum has occurred Prefix sum plus hash map
10 Rain water trapped between bars Hard Water above a bar is bounded by the lower of the best left and right bars Two pointers
11 Smallest window containing all characters of a pattern Hard Count needs, expand until satisfied, then shrink Window with counts
12 Longest palindromic substring Medium Expand around every center, or use Manacher Expand from center

A first worked sample: problem 9, counting subarrays whose sum equals k. The key fact is that a subarray sum is a difference of two prefix sums, so at each position you only need to know how many earlier prefixes equal current - k.

Python Subarray sum equals k with prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fast version is O(n) time and O(n) space; the brute force is O(n^3) as written. Always keep a brute force like this around: it is your test oracle.

Set 2: Trees

Trees are mostly about choosing between recursion that returns an answer for a subtree and level-by-level BFS. Read Tree Traversals and Tree Problems first.

# Problem Level Hint Pattern
1 Height of a binary tree Easy 1 + max(left, right), empty tree is 0 Postorder recursion
2 Are two trees identical? Easy Compare values, then both subtrees Parallel recursion
3 Mirror (invert) a tree Easy Swap children, then recurse Recursion
4 Level order traversal Medium A queue and the size of the current level BFS
5 Is it a valid binary search tree? Medium Pass down the allowed lower and upper bounds Recursion with bounds
6 The k-th smallest value in a BST Medium Inorder traversal visits values in sorted order Inorder
7 Lowest common ancestor Medium If the two targets are in different subtrees, you are the answer Recursion
8 Diameter of a tree Medium Longest path through a node is left height + right height Return one value, record another
9 Build a tree from preorder and inorder lists Medium Preorder gives the root; inorder splits the sides Divide and conquer
10 Maximum path sum Hard Ignore negative branches; return the best single branch upward Tree DP
11 Serialize and deserialize a tree Hard Preorder with a marker for empty children Preorder encoding
12 Smallest subtree with all the deepest nodes Hard Return both depth and candidate root Tree DP

A second sample: problem 8 shows a trick used in many tree problems. The function returns one thing (the height) but updates another (the best diameter seen so far).

Python Diameter of a binary tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The diameter is measured in edges: the path 6, 4, 2, 1, 3 has four of them. Each node is visited once, so the time is O(n), and the recursion depth equals the height of the tree.

Set 3: Graphs

For graphs, the first decision is the model. Rows and columns of a grid are a graph where each cell is a node. Prerequisites are directed edges. Words that differ by one letter are connected. Read Graph Representations, BFS and DFS before you start.

# Problem Level Hint Pattern
1 Count islands in a grid of land and water Medium Start a flood fill at each unvisited land cell Components
2 Is there a path between two nodes? Easy BFS or DFS with a visited set Traversal
3 Shortest path in an unweighted grid Medium BFS, level by level BFS
4 Clone a graph Medium Map old nodes to new nodes while traversing DFS with a map
5 Can all courses be finished given prerequisites? Medium Cycle detection, or Kahn's algorithm Topological sort
6 Order the courses Medium The topological order itself Topological sort
7 Is the graph a tree? Medium Exactly n - 1 edges and connected Union-Find
8 Redundant connection Medium The first edge that joins two nodes already connected Union-Find
9 Rotting oranges: minutes until all rot Medium Multi-source BFS from every rotten cell Multi-source BFS
10 Word ladder Hard BFS where neighbors differ by one letter BFS on an implicit graph
11 Cheapest route with at most k stops Hard Bellman-Ford limited to k rounds, or BFS with state Shortest paths
12 Time for a signal to reach all nodes Medium Dijkstra; the answer is the largest distance Dijkstra

A third sample: problem 9. The twist is the multi-source start: put every rotten cell in the queue at minute zero, and each BFS level is one minute.

Python Rotting oranges with multi-source BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time is O(rows * cols), because each cell enters the queue at most once.

Set 4: Dynamic programming

DP problems are solved in four steps: define the state in words, write the recurrence, set the base cases, and decide the order (top-down with memoization or bottom-up). Start with DP Introduction and 1D DP.

# Problem Level Hint Pattern
1 Climbing stairs: ways to reach step n using 1 or 2 steps Easy ways[n] = ways[n-1] + ways[n-2] 1D DP
2 House robber: no two adjacent houses Medium Rob this house plus i-2, or skip to i-1 1D DP
3 Minimum coins for an amount Medium best[a] = 1 + min(best[a - coin]) Coin change
4 Number of ways to make an amount Medium Loop over coins on the outside to avoid counting orders Coin change
5 Longest increasing subsequence Medium Quadratic DP first, then patience sorting LIS
6 Unique paths in a grid with obstacles Medium Add the cell above and the cell to the left Grid DP
7 0/1 knapsack Medium State: item index and remaining capacity Knapsack
8 Partition into two equal-sum subsets Medium Subset sum to half the total Knapsack
9 Longest common subsequence Medium Matching last characters extend the diagonal LCS
10 Edit distance Hard Insert, delete or replace: three neighbors LCS family
11 Word break Medium can[i] if some j < i has can[j] and s[j:i] is a word String DP
12 Palindromic substrings (count them) Medium Expand around centers, or a table of substrings String DP

A fourth sample: problem 4, counting the ways to make an amount. A small detail decides correctness. Putting the coins in the outer loop counts combinations, while putting the amounts first would count ordered sequences.

Python Counting coin combinations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(coins * amount) and space is O(amount). If you can explain why swapping the loops changes the answer, you understand the technique and not just the template.

Choosing what to practice next

After the four sets, mix topics so that you have to identify the pattern yourself. Pick a random problem, cover the topic label and ask: what is the signal? A good test of readiness is solving a medium problem you have never seen in 30 to 40 minutes while talking. If that is still hard, return to the topic where you needed the most hints. The Patterns Cheat Sheet will help you map signals to techniques, and Choosing the Right Structure covers the decision from the data side.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In 'subarray sum equals k', why do we start the prefix-sum counter with seen[0] = 1?

    The empty prefix has sum 0. Without it, a subarray beginning at the first element would have no earlier prefix to subtract.
  2. 2. In the tree diameter solution, what does the helper function return, and what does it record?

    Only one branch of a path can continue upward, so the function returns the height. The path that bends at this node is checked against the best diameter.
  3. 3. Why does rotting oranges start the BFS with all rotten oranges in the queue?

    Multi-source BFS treats all sources as distance zero. The levels then measure time correctly for oranges rotted from different starting points.
  4. 4. Which loop order counts coin combinations (1+2 and 2+1 are the same)?

    With coins in the outer loop, each coin type is introduced once, so every combination is counted in a single canonical order.

Summary

  • The four sets cover arrays and strings, trees, graphs and dynamic programming, from warm-up to hard, with a hint and a pattern for each problem.
  • Solve each problem in order: examples, brute force, attempt, hint, optimal solution, notes.
  • Keep a brute force next to every clever solution and compare them on small inputs.
  • Tree problems often return one value and record another; graph problems start by choosing the right model; DP problems start by naming the state.
  • Re-solve what you missed after a week, then switch to mixed practice to train pattern recognition.

To keep going, work through the solved problems in Practice Problems: Arrays, Strings and Hashing and Advanced Practice Problems.