hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Minimum Number of Arrows to Burst Balloons
Problem: 452. Minimum Number of Arrows to Burst Balloons
Problem Link: leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons
Companies Asked: Google, Facebook, Goldman Sachs
Approach:
The first step is to sort the given vector based on the point[i][0]. If point[i][0] matches then based on point[i][1]. If point[i][1] matches then index.
After sorting traverse through the vector.
For each i, check if points[i][0] become lesser than the minimum of points[i-1][1].
Increase the count by 1.
If points[i][0] become greater than the minimum of points[i-1][1], compare the rest of the points based on current points[i][0].
Keep doing it until we reach the end.
Return the count.
Time and Space Complexity:
Time Complexity: O(Nlog2N + N)
Space Complexity: O(1)
Code [C++]
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& balloons) {
int n = balloons.size();
sort(balloons.begin(), balloons.end());
int counter = 0, comp_x = balloons[0][1];
for(int i=1; i<n; i++){
if(balloons[i][0] <= comp_x){
comp_x = min(comp_x, balloons[i][1]);
}
else{
counter++;
comp_x = balloons[i][1];
}
}
counter++;
return counter;
}
};