‹ DS&A interview · Socratic
DSA · Greedy / Intervals · #123

Minimum Number of Arrows to Burst Balloons

Module 77 · difficulty 3/5·⏱ 30:00starts on first keystroke

There are some spherical balloons taped to a flat wall. Each balloon is given as an interval `points[i] = [xstart, xend]`, meaning it spans the horizontal range `[xstart, xend]` (inclusive at both ends). Arrows are shot vertically upward from points along the x-axis. An arrow shot at coordinate `x` bursts a balloon `[xstart, xend]` if and only if `xstart <= x <= xend`. There is no limit to how many balloons one arrow can burst, and an arrow once shot keeps traveling upward forever. Implement `findMinArrowShots(points)` that returns the **minimum** number of arrows needed to burst all balloons.

Examples
  • points = [[10,16],[2,8],[1,6],[7,12]] → 2 — Shoot one arrow at x=6 (bursts [2,8] and [1,6]) and another at x=11 (bursts [10,16] and [7,12]).
  • points = [[1,2],[3,4],[5,6],[7,8]] → 4 — No two intervals overlap, so each needs its own arrow.
  • points = [[1,2],[2,3],[3,4],[4,5]] → 2 — Arrow at x=2 bursts [1,2] and [2,3]; arrow at x=4 bursts [3,4] and [4,5].
Constraints
  • · 1 <= points.length <= 10^5
  • · points[i].length == 2
  • · -2^31 <= xstart <= xend <= 2^31 - 1
  • · Endpoints are inclusive: touching intervals (e.g. [1,2] and [2,3]) can be burst by one arrow.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.