Skip to main content
Back to ChallengesMinimum Number of Arrows to Burst BalloonsMedium 30 min

Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end].

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end.

Return the minimum number of arrows that must be shot to burst all balloons.

Examples

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Shoot one arrow at x = 6 (bursting [2,8] and [1,6]) and another at x = 11 (bursting [10,16] and [7,12]).

Constraints

  • • 1 <= points.length <= 10^5
  • • points[i].length == 2
  • • -2^31 <= x_start < x_end <= 2^31 - 1

Complexity Analysis

Time
O(N log N)
due to sorting the balloons.
Space
O(1) auxiliary space.

Test Cases

#1 Overlap handled
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Expected: 2
#2 No overlap
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Expected: 4
Output
Click "Run Code" to see output here...