Minimum Number of Arrows to Burst…

1. Define the problem

Minimum Number of Arrows to Burst Balloons

Balloons are represented as intervals points_i = [x_start, x_end] along the x-axis. An arrow shot at position x bursts every balloon with x_start ≤ x ≤ x_end, and can travel an unlimited distance. Return the minimum number of arrows needed to burst every balloon. Sort by end position . Shoot the first arrow at the end of the first balloon, then only shoot a new arrow when a balloon starts after the position of the last arrow shot.

Constraints

1 ≤ points.length ≤ 10⁵
points_i.length == 2
-2³¹ ≤ x_start_i < x_end_i ≤ 2³¹ - 1

Example

Inputpoints = [[10, 16], [2, 8], [1, 6], [7, 12]]

Output2

Explanation One arrow at x = 6 bursts [2,8] and [1,6]. A second arrow at x = 12 bursts [10,16] and [7,12].

2. Visualize the solution

Sweep balloons sorted by end, shooting only when needed

Slot1–6

Slot2–8

Slot7–12

Slot10–16

StatusarrowPos=6

Sorted by end: [1,6] is first. Shoot an arrow at x=6. arrows=1.

What happens in this step

sorted (by end): [1,6], [2,8], [7,12], [10,16]

arrowPos = sorted[0][1] = 6, arrows = 1

The first balloon after sorting always gets the first arrow, placed at its end.

Step 1 of 5

Steps to visualize

Sort the balloons by their end value.
Shoot the first arrow at the end of the first balloon.
For each following balloon, if it starts at or before the current arrow position, it is already burst.
Only shoot a new arrow — placed at that balloon's end — when a balloon starts after the current arrow position.
The number of arrows shot is the answer.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sweep balloons sorted by end, shooting only when needed

Slot1–6

Slot2–8

Slot7–12

Slot10–16

StatusarrowPos=6

Sorted by end: [1,6] is first. Shoot an arrow at x=6. arrows=1.

What happens in this step

sorted (by end): [1,6], [2,8], [7,12], [10,16]

arrowPos = sorted[0][1] = 6, arrows = 1

The first balloon after sorting always gets the first arrow, placed at its end.

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function findMinArrowShots(points) {
  if (points.length === 0) return 0;

  const sorted = [...points].sort((a, b) => a[1] - b[1]);
  let arrows = 1;
  let arrowPos = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    if (start > arrowPos) {
      arrows++;
      arrowPos = end;
    }
  }

  return arrows;
}

Time: O(n log n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`points = [[10, 16], [2, 8], [1, 6], [7, 12]]`	`2`	example from the docstring
`points = [[1, 2], [3, 4], [5, 6], [7, 8]]`	`4`	every balloon is separate, one arrow needed per balloon
`points = [[1, 2], [2, 3], [3, 4], [4, 5]]`	`2`	touching balloons can share an arrow at the shared point
`points = [[1, 2]]`	`1`	smallest valid input, a single balloon
`points = [[1, 1], [1, 1]]`	`1`	identical balloons burst together with one arrow
`points = [[1, 100], [50, 150], [120, 200]]`	`2`	a chain where the first and last balloons never directly overlap
`points = []`	`0`	no balloons at all, no arrows needed

Minimum Number of Arrows to Burst Balloons