452. Minimum Number of Arrows to Burst Balloons LeetCode Solution
In this guide, you will get 452. Minimum Number of Arrows to Burst Balloons LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Arrows to Burst Balloons problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
– Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
– Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
– Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
– Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].
452. Minimum Number of Arrows to Burst Balloons LeetCode Solution in C++
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
ranges::sort(points,
[](const auto& a, const auto& b) { return a[1] < b[1]; });
int ans = 1;
int arrowX = points[0][1];
for (int i = 1; i < points.size(); ++i)
if (points[i][0] > arrowX) {
arrowX = points[i][1];
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
452. Minimum Number of Arrows to Burst Balloons LeetCode Solution in Java
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int ans = 1;
int arrowX = points[0][1];
for (int i = 1; i < points.length; ++i)
if (points[i][0] > arrowX) {
arrowX = points[i][1];
++ans;
}
return ans;
}
} // code provided by PROGIEZ
452. Minimum Number of Arrows to Burst Balloons LeetCode Solution in Python
class Solution:
def findMinArrowShots(self, points: list[list[int]]) -> int:
ans = 0
arrowX = -math.inf
for point in sorted(points, key=lambda x: x[1]):
if point[0] > arrowX:
ans += 1
arrowX = point[1]
return ans # code by PROGIEZ
