Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 63 ยท Practice and Review

Practice: Intermediate Problems with Solutions

Twelve mid-level contest problems on greedy, binary search, dynamic programming and graphs, with ideas, runnable Python solutions and brute-force checks.

Intermediate problems are where contests become interesting. The statement no longer tells you which technique to use, and often the same problem can be attacked in two ways, one fast and one too slow. The twelve problems below are grouped by technique, but in a real contest nothing is labeled, so the first skill is recognizing the pattern from the constraints and the shape of the question.

Each problem has a statement, the key idea and a short complexity note, followed by runnable code. Several solutions are checked against a brute force on random small inputs, exactly as described in stress testing. Try each problem yourself before reading the idea; if you get stuck, reading just the first sentence of the idea is a good hint level.

flowchart LR
  Q["Question shape"] --> G["Best or max/min with local choices:<br/>try greedy"]
  Q --> B["Largest min or smallest max:<br/>binary search the answer"]
  Q --> D["Count or optimize over choices<br/>with repeated subproblems: DP"]
  Q --> H["Grid, network, dependencies:<br/>model a graph"]

Four common clues that point to a technique.

Greedy and binary search (problems 1 to 4)

Problem 1: Most meetings. You are given meetings as intervals [start, end). You can attend a set of meetings if none overlap. What is the largest number you can attend? Idea: sort by end time and take every meeting that starts no earlier than the end of the last chosen one. Finishing early leaves the most room for later meetings. Sorting by start time or by length fails, and you can find counterexamples in a minute. Cost O(n log n). The proof technique (exchange argument) is explained in greedy algorithms and how to trust them.

Problem 2: Can you reach the end? An array jumps[i] says the farthest you can jump from cell i. Starting at cell 0, can you reach the last cell? Idea: sweep left to right, keeping the farthest reachable index. If you ever stand at an index beyond the farthest reachable one, you are stuck. Cost O(n). For [3, 2, 1, 0, 4] every path ends at the zero in cell 3, so the answer is no.

Problem 3: Split an array. Split an array of positive integers into at most k contiguous parts so that the largest part sum is as small as possible. Idea: binary search on the answer. If a limit L is feasible (greedy: start a new part whenever adding the next element would exceed L), then every larger limit is feasible too. Search between max(a) and sum(a). Cost O(n log(sum)). This is the pattern from binary search on answer.

Problem 4: Spread the routers. Place k routers at some of the given positions on a line to maximize the minimum distance between two routers. Idea: binary search on the distance d. For a given d, place the first router at the leftmost position and greedily add the next one at least d away. If you can place k, a smaller d also works, so feasibility is monotone. Because we want the maximum feasible d, the midpoint is rounded up ((lo + hi + 1) // 2), otherwise the loop never ends when hi = lo + 1.

Python Problems 1 to 4 with brute-force checks

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.

For problem 3 the answers are 18 (the parts [7, 2, 5] and [10, 8]) and 3 (each element alone). For problem 4 the best choice is the positions 1, 4 and 8 (or 1, 4 and 9), with a smallest gap of 3.

Binary search bugs are almost always about the midpoint and the bounds, not the idea. Minimizing uses hi = mid with a rounded-down midpoint; maximizing uses lo = mid with a rounded-up midpoint. Mixing the two causes an infinite loop.

Dynamic programming (problems 5 to 8)

Problem 5: Longest increasing subsequence. Find the length of the longest strictly increasing subsequence (elements need not be adjacent). Idea: keep a list tails, where tails[i] is the smallest possible last value of an increasing subsequence of length i + 1. For each number, find its place with bisect_left: replace the first tail that is at least as large, or append. The list stays sorted, and its length is the answer. Cost O(n log n), against O(n^2) for the textbook DP. bisect_left makes the subsequence strictly increasing; bisect_right would allow equal values.

Problem 6: Fewest coins. Given coin values and a target, find the smallest number of coins that sum to the target, or -1. Idea: dp[t] is the best answer for amount t, computed from dp[t - c] for each coin c. Greedy fails here: with coins 1, 5 and 6 and target 10, taking the largest coin first gives 6 + 1 + 1 + 1 + 1 (five coins), while 5 + 5 uses two. Cost O(target x coins).

Problem 7: Knapsack. Each item has a weight and a value; choose a subset with total weight at most cap and maximum value. Idea: dp[c] is the best value with capacity c. Processing items one by one, iterate the capacity downward, so each item is used at most once. Iterating upward would let the same item be used repeatedly, which solves a different problem (unbounded knapsack). Cost O(items x cap).

Problem 8: Edit distance. What is the minimum number of single-character insertions, deletions and replacements needed to turn one string into another? Idea: d[i][j] is the distance between the first i characters of s and the first j of t. Either the last characters match (copy the diagonal), or you take the cheapest of insert, delete and replace, plus one. Only the previous row is needed, which cuts memory from O(nm) to O(m). Cost O(nm). The distance between kitten and sitting is 3.

Python Problems 5 to 8 with brute-force checks

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 LIS answer for [10, 9, 2, 5, 3, 7, 101, 18] is 4 (for example 2, 3, 7, 18). The knapsack with capacity 5 takes the items of weight 2 and 3, for a value of 7. If you want to study these patterns systematically, see DP problem patterns.

Graphs (problems 9 to 12)

Problem 9: Count the islands. A grid has # for land and . for water. Count groups of land cells connected through the four neighbors. Idea: scan the grid; whenever you meet land you have not visited, count one island and flood it with a BFS. Cost O(cells). Use an explicit queue instead of recursion, because a large island can exceed Python's recursion limit.

Problem 10: Shortest path in a maze. Find the fewest steps from S to E through free cells, where # is a wall. Print -1 if there is no path. Idea: BFS from S. The first time the queue reaches E, the distance is minimal, because BFS visits cells in order of distance. Cost O(cells).

Problem 11: Cheapest route. In a graph with positive edge weights, find the shortest distance from a source to every vertex. Idea: Dijkstra with a heap. Pop the closest unfinished vertex, skip stale heap entries (d > dist[u]) and relax its edges. Cost O(E log V). It fails on negative edges; see shortest paths in practice.

Problem 12: Course order. Courses have prerequisites (a, b) meaning a must come before b. Print a valid order, or report that none exists. Idea: topological sort with indegrees (Kahn's algorithm). Start with courses that have no prerequisites, remove them and lower the indegree of what they unlock. If fewer than n courses come out, there is a cycle, so no order exists. Cost O(V + E).

Python Problems 9 to 12

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 grid in problem 9 has four islands. In problem 11 the route to vertex 1 is not the direct edge of cost 4: going through vertex 2 costs 1 + 2 = 3, which is why the distances are [0, 3, 1, 8, 11]. For problem 12 the first prerequisite list has a valid order [0, 1, 3, 2], and the cyclic list prints None. Graph modeling is the topic of graph problems: modeling and traversal.

After you solve them

  • Classify the clue. For each problem write one sentence: "I knew it was X because the statement said Y". Those sentences become your pattern recognition.
  • Break the constraints. What happens to problem 6 if the target is 10^9? (The table is too big, and the problem needs a different idea.) What if the edge weights in problem 11 can be negative?
  • Time yourself. Intermediate problems should take 15 to 30 minutes each, including testing. Slower is fine at first, but note where the time went: understanding, finding the idea, or debugging.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the 'maximize the minimum distance' binary search round the midpoint up?

    When maximizing, a feasible mid becomes the new lo. If mid equals lo (rounded down), no progress is made and the loop never ends.
  2. 2. Coins are 1, 5 and 6 and the target is 10. Why is taking the largest coin first the wrong strategy?

    Greedy works only for special coin systems. Here DP finds 2 coins where the greedy choice finds 5.
  3. 3. In the 0/1 knapsack with one array, why iterate the capacity from high to low?

    Going downward means dp[c - w] still holds the value from before this item was added. Going upward would reuse the item.
  4. 4. How can the course-order algorithm tell that no valid order exists?

    Courses in a cycle always keep at least one unfinished prerequisite, so they are never queued, and the output is shorter than n.

Summary

  • Match the question shape to a technique: local choices suggest greedy, "largest minimum" or "smallest maximum" suggests binary search on the answer, repeated subproblems suggest DP, and grids or dependencies suggest graphs.
  • Sort meetings by end time, sweep for reachability, binary search on a monotone feasibility check.
  • DP needs a clear state, a transition and the right iteration order; knapsack goes downward, LIS uses bisect_left.
  • Use BFS for unweighted shortest paths, Dijkstra for non-negative weights and indegrees for ordering with cycle detection.
  • Check clever solutions against a brute force on tiny random inputs.

Next: Practice: Hard Problems with Solutions