DSA-040 · Earliest-right-endpoint interval stabbing
Minimum Arrows to Burst Balloons
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 2364 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the minimum number of arrow positions needed to hit every closed balloon interval on a line.
- balloons is a non-null int[][] with 0–100,000 signed-int [start,end] rows. Both methods throw IllegalArgumentException for null/malformed rows or start>end. Point balloons [x,x] are valid.
- An arrow at coordinate x hits exactly balloons with start≤x≤end. Closed endpoints mean [1,2] and [2,3] can share one arrow at two. Empty input returns zero; duplicate balloons remain occurrences but may share one arrow.
- Return a count and preserve caller order/row values. Arrows may conceptually be placed at real coordinates, but an optimal solution exists using balloon right endpoints, which fit int. No subtraction-based comparator or sentinel arrow outside the int range is used.
Examples
Input:
[[10,16],[2,8],[1,6],[7,12]]
Output:2Arrows at 6 and 12 cover all four closed intervals.
Input:
[[1,2],[2,3]]
Output:1One arrow at the shared closed endpoint hits both.
Before you start
- Closed versus half-open intervals and compatible endpoints
- Sorting with safe comparators and invariant or exchange proofs
Recognize the structure
This is point stabbing, not union merging or interval selection. Choose a point that must hit the earliest-ending uncovered interval and can be shifted as far right as that interval permits without losing its covered companions.
Try before revealing
Hint 1
Which uncovered balloon imposes the earliest rightmost allowed shot?
Hint 2
Can an optimum’s shot be moved to that end without losing its covered balloons?
Hint 3
Sort by end and shoot only when the current closed interval starts beyond the last arrow.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Repeatedly scan for the earliest uncovered end
Keep a covered flag per balloon. Find the smallest end among uncovered rows, shoot there, and scan all rows to mark those containing it. On [1,3],[2,5],[4,6], shoot at three to cover the first two, then at six for the last. This O(n²) baseline makes the greedy action explicit without sorting; sorting avoids repeated searches and coverage scans.
Improve the baseline
Sort balloons by right endpoint
Process the most urgent uncovered deadline first. Use a safe end comparator to handle extreme signed coordinates.
Place at the first uncovered end
If no arrow has been placed, or the next start is greater than the current arrow, shoot at this balloon’s end and increment the count.
Reuse the current arrow
Otherwise start≤arrow, and sorting ensures arrow≤this balloon.end. The existing arrow lies inside the closed interval, so no new shot is needed.
Why it is correct
Endpoint exchange
Let B be an uncovered interval with smallest right endpoint e. An optimal solution must hit B with some point p≤e. Every other uncovered interval hit by p has start≤p≤e and end≥e by minimality of e, so moving that arrow to e preserves all its coverage. An optimum exists with the greedy first arrow.
Residual optimality
Remove all balloons containing e. The remaining task is the same problem on uncovered intervals; applying the exchange inductively proves the minimum number of arrows.
Sorted scan and termination
All future interval ends are at least the current arrow. If a start exceeds it, that interval is still uncovered and its end is the earliest among the remaining scan order. Otherwise the current arrow covers it. Each row is processed once after sorting; an explicit placed flag handles every signed coordinate and empty input.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void validate(int[][] balloons) {
for (int[] row : balloons) if (row == null || row.length != 2 || row[0] > row[1]) throw new IllegalArgumentException("closed balloon intervals required");
}
public static int findMinArrowShots(int[][] balloons) {
validate(balloons);
int[][] sorted = balloons.clone();
Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
int count = 0, arrow = 0;
boolean placed = false;
for (int[] next : sorted) {
if (!placed || next[0] > arrow) {
arrow = next[1];
count++;
placed = true;
}
}
return count;
}
public static int baseline(int[][] balloons) {
validate(balloons);
boolean[] covered = new boolean[balloons.length];
int remaining = balloons.length, count = 0;
while (remaining > 0) {
int earliest = -1;
for (int i = 0; i < balloons.length; i++) if (!covered[i] && (earliest == -1 || balloons[i][1] < balloons[earliest][1])) earliest = i;
int point = balloons[earliest][1];
count++;
for (int i = 0; i < balloons.length; i++) if (!covered[i] && balloons[i][0] <= point && point <= balloons[i][1]) { covered[i] = true; remaining--; }
}
return count;
}
}
Read the meaningful blocks
Closed equality covers
A new arrow is needed only when start>arrow, not when start==arrow.
Keep arrow fixed while covered
Do not move an already placed arrow to a later interval end: that can leave previously covered balloons behind.
Avoid a fake sentinel
arrow starts at zero only as an unused local value. placed determines whether it represents a real shot, allowing Integer.MIN_VALUE point balloons safely.
Complexity
O(n log n) time and O(n) auxiliary storage for the cloned row-reference array and object-sort workspace. The scan uses O(1) state; returned output is one count.
The repeated-scan baseline uses O(n²) time and O(n) coverage flags. Tests use a separate endpoint set-cover DP on small cases, examining coverage combinations rather than assuming the greedy choice.
Exact-state walkthroughs
Reveal normal and boundary traces
Earliest endpoints give two shots
Input: [[10,16],[2,8],[1,6],[7,12]] · Result: 2
Step 1 of 6: Sort closed balloons by right endpoint.
No real arrow exists yet; null represents the not-placed state rather than a numeric sentinel.
Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions.
- Row #0:
[1, 6] - Row #1:
[2, 8] - Row #2:
[7, 12] - Row #3:
[10, 16]
Empty at this step.
The Java count-only method retains the last arrow and count. Earlier arrow positions are shown as explanatory history.
| Variable | Value |
|---|---|
| intervalRows | [[1,6],[2,8],[7,12],[10,16]] |
| index | -1 |
| arrow | null |
| arrowPositions | [] |
| count | 0 |
| closed | true |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] balloons) { 4 for (int[] row : balloons) if (row == null || row.length != 2 || row[0] > row[1]) throw new IllegalArgumentException("closed balloon intervals required"); 5 } 6 public static int findMinArrowShots(int[][] balloons) { 7 validate(balloons); 8 int[][] sorted = balloons.clone(); 9 Arrays.sort(sorted, Comparator.comparingInt(value -> value[1])); 10 int count = 0, arrow = 0; 11 boolean placed = false; 12 for (int[] next : sorted) { 13 if (!placed || next[0] > arrow) { 14 arrow = next[1]; 15 count++; 16 placed = true; 17 } 18 } 19 return count; 20 } 21 public static int baseline(int[][] balloons) { 22 validate(balloons); 23 boolean[] covered = new boolean[balloons.length]; 24 int remaining = balloons.length, count = 0; 25 while (remaining > 0) { 26 int earliest = -1; 27 for (int i = 0; i < balloons.length; i++) if (!covered[i] && (earliest == -1 || balloons[i][1] < balloons[earliest][1])) earliest = i; 28 int point = balloons[earliest][1]; 29 count++; 30 for (int i = 0; i < balloons.length; i++) if (!covered[i] && balloons[i][0] <= point && point <= balloons[i][1]) { covered[i] = true; remaining--; } 31 } 32 return count; 33 } 34 } 35
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Sort closed balloons by right endpoint.
No real arrow exists yet; null represents the not-placed state rather than a numeric sentinel.
- intervalRows
[[1,6],[2,8],[7,12],[10,16]]- index
-1- arrow
null- arrowPositions
[]- count
0- closed
true
- Shoot at the earliest-ending uncovered balloon’s right endpoint.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,6],[2,8],[7,12],[10,16]]- index
0- arrow
6- shot
true- arrowPositions
[6]- count
1- closed
true
- Reuse the fixed arrow inside this closed interval.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,6],[2,8],[7,12],[10,16]]- index
1- arrow
6- shot
false- arrowPositions
[6]- count
1- closed
true
- Shoot at the earliest-ending uncovered balloon’s right endpoint.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,6],[2,8],[7,12],[10,16]]- index
2- arrow
12- shot
true- arrowPositions
[6,12]- count
2- closed
true
- Reuse the fixed arrow inside this closed interval.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,6],[2,8],[7,12],[10,16]]- index
3- arrow
12- shot
false- arrowPositions
[6,12]- count
2- closed
true
- Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
- result
2
Touching closed endpoints share an arrow
Input: [[1,2],[2,3],[3,3]] · Result: 2
Step 1 of 5: Sort closed balloons by right endpoint.
No real arrow exists yet; null represents the not-placed state rather than a numeric sentinel.
Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions.
- Row #0:
[1, 2] - Row #1:
[2, 3] - Row #2:
[3, 3]
Empty at this step.
The Java count-only method retains the last arrow and count. Earlier arrow positions are shown as explanatory history.
| Variable | Value |
|---|---|
| intervalRows | [[1,2],[2,3],[3,3]] |
| index | -1 |
| arrow | null |
| arrowPositions | [] |
| count | 0 |
| closed | true |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] balloons) { 4 for (int[] row : balloons) if (row == null || row.length != 2 || row[0] > row[1]) throw new IllegalArgumentException("closed balloon intervals required"); 5 } 6 public static int findMinArrowShots(int[][] balloons) { 7 validate(balloons); 8 int[][] sorted = balloons.clone(); 9 Arrays.sort(sorted, Comparator.comparingInt(value -> value[1])); 10 int count = 0, arrow = 0; 11 boolean placed = false; 12 for (int[] next : sorted) { 13 if (!placed || next[0] > arrow) { 14 arrow = next[1]; 15 count++; 16 placed = true; 17 } 18 } 19 return count; 20 } 21 public static int baseline(int[][] balloons) { 22 validate(balloons); 23 boolean[] covered = new boolean[balloons.length]; 24 int remaining = balloons.length, count = 0; 25 while (remaining > 0) { 26 int earliest = -1; 27 for (int i = 0; i < balloons.length; i++) if (!covered[i] && (earliest == -1 || balloons[i][1] < balloons[earliest][1])) earliest = i; 28 int point = balloons[earliest][1]; 29 count++; 30 for (int i = 0; i < balloons.length; i++) if (!covered[i] && balloons[i][0] <= point && point <= balloons[i][1]) { covered[i] = true; remaining--; } 31 } 32 return count; 33 } 34 } 35
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Sort closed balloons by right endpoint.
No real arrow exists yet; null represents the not-placed state rather than a numeric sentinel.
- intervalRows
[[1,2],[2,3],[3,3]]- index
-1- arrow
null- arrowPositions
[]- count
0- closed
true
- Shoot at the earliest-ending uncovered balloon’s right endpoint.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,2],[2,3],[3,3]]- index
0- arrow
2- shot
true- arrowPositions
[2]- count
1- closed
true
- Reuse the fixed arrow inside this closed interval.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,2],[2,3],[3,3]]- index
1- arrow
2- shot
false- arrowPositions
[2]- count
1- closed
true
- Shoot at the earliest-ending uncovered balloon’s right endpoint.
The latest arrow covers this balloon. Previously selected points remain fixed; the trace lists their history while Java stores only the last point and count.
- intervalRows
[[1,2],[2,3],[3,3]]- index
2- arrow
3- shot
true- arrowPositions
[2,3]- count
2- closed
true
- Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
- result
2
Test the contract
Input:
[]
Output:0No balloons.
Input:
[[3,3],[3,3]]
Output:1One point hits duplicate point balloons.
Input:
[[1,2],[3,4]]
Output:2A strict gap separates the targets.
Input:
[[-2147483648,-2147483648],[2147483647,2147483647]]
Output:2Extreme points require no subtraction or out-of-range sentinel.
Common mistakes and counterexamples
Reuse meeting equality rules
Counterexample: [1,2] and [2,3] share a closed point and need only one arrow.
Use start>arrow for a new shot.
Replace the arrow with every covered end
Counterexample: For [1,3],[2,5],[4,6], moving the first arrow from three to five loses [1,3].
Leave the chosen point fixed until the next uncovered interval.
Count connected union components
Counterexample: [1,3],[2,4],[3,5],[4,6] is one connected union, but no single point hits all four; two arrows suffice.
Solve common-point coverage, not overlap connectivity.
Follow-ups
Return arrow positions.
Append each chosen right endpoint when the count increments. The exchange proof already establishes their optimality; returned storage becomes O(number of arrows).
Assign nonuniform position costs.
The endpoint exchange can change cost and therefore fails for arbitrary location prices. Define a finite candidate set and use an optimization method that accounts for both coverage and cost.
Compare with overlap components.
Connected intervals can form a long chain without one common intersection. Union merging answers which points are covered; stabbing asks how few points meet every interval, so a connected component may need several shots.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 150/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.