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


  • Approach:

    1. 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.

    2. After sorting traverse through the vector.

    3. For each i, check if points[i][0] become lesser than the minimum of points[i-1][1].

    4. Increase the count by 1.

    5. 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].

    6. Keep doing it until we reach the end.

    7. 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;

}

};