LC-0452 Medium LeetCode

452. Minimum Number of Arrows to Burst Balloons

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 60% Topics: Array, Greedy, Sorting

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(1)

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points:
            return 0

        points.sort()

        result = 0
        i = 0
        while i < len(points):
            j = i + 1
            right_bound = points[i][1]
            while j < len(points) and points[j][0] <= right_bound:
                right_bound = min(right_bound, points[j][1])
                j += 1
            result += 1
            i = j
        return result

Solution from kamyu104/LeetCode-Solutions · MIT