Fewest Laser Shots to Pop Every Balloon
Solve this ProblemBalloons are stuck to a wall, each covering a horizontal stretch from xStart to xEnd. A laser shot is a vertical line at some position x: it pops every balloon whose stretch contains x, ends included, and keeps going. Find the fewest shots that pop every balloon.
Trying combinations of shot positions is exponential. But sorting the balloons by right end reveals a simple rule: the first unpopped balloon must be hit, and the best place to hit it is at its right end, which also pops every balloon that starts at or before that position.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ balloons.length ≤ 10; each balloon is [xStart, xEnd] with 0 ≤ xStart ≤ xEnd ≤ 50, the horizontal stretch it covers on a wall - ◆
A shot is a vertical laser at some x (any integer or real position); it pops every balloon with xStart ≤ x ≤ xEnd — the ends count as inside - ◆
A shot passes through all balloons at that x, and popped balloons do not stop it - ◆
Return the fewest shots needed to pop every balloon
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Combination of Shot Positions
BruteA shot never needs to be anywhere but at the right end of some balloon: any shot can slide right until it hits the end of the leftmost balloon it pops, without releasing anything. So the candidate shot positions are the n balloon ends. Try every subset of those positions (a bitmask); for each subset check that every balloon contains at least one chosen position. Among the subsets that pop everything, the smallest one gives the answer. It is correct because it tries every possibility, but there are 2ⁿ subsets and each needs an n × n check.
O(2ⁿ · n²)O(1)1class Solution {
2 public int fewestShots(int[][] balloons) {
3 int n = balloons.length;
4 int best = n;
5 for (int mask = 1; mask < (1 << n); mask++) {
6 boolean allPopped = true;
7 for (int b = 0; b < n && allPopped; b++) {
8 boolean popped = false;
9 for (int s = 0; s < n; s++) {
10 if ((mask & (1 << s)) != 0 && balloons[b][0] <= balloons[s][1] && balloons[s][1] <= balloons[b][1]) {
11 popped = true;
12 break;
13 }
14 }
15 if (!popped) allPopped = false;
16 }
17 if (allPopped) best = Math.min(best, Integer.bitCount(mask));
18 }
19 return best;
20 }
21}Optimal — Sort by End and Shoot at the First Unpopped End
OptimalSort the balloons by right end. The first balloon must be popped by some shot, and the best place for that shot is at its right end: it reaches as far right as possible while still popping that balloon, catching the most others. Fire there, and skip every balloon whose start is at or before that x (they are popped too). The next balloon whose start is beyond the last shot needs a new shot, again at its own right end. Count the shots — one sort and one pass.
O(n log n)O(n)1class Solution {
2 public int fewestShots(int[][] balloons) {
3 int[][] byEnd = balloons.clone();
4 Arrays.sort(byEnd, (a, b) -> Integer.compare(a[1], b[1]));
5 int shots = 0;
6 int lastShot = Integer.MIN_VALUE;
7 for (int[] balloon : byEnd) {
8 if (balloon[0] > lastShot) {
9 shots++;
10 lastShot = balloon[1];
11 }
12 }
13 return shots;
14 }
15}