452. Minimum Number of Arrows to Burst Balloons - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Sorting intervals by start or end values for greedy processing
Greedy Algorithms - Making optimal local choices for interval scheduling problems
Interval Overlap Detection - Determining when two intervals share common points

1. Greedy (Sort By Start Value)

Intuition

Think of each balloon as a horizontal range on a number line. If two balloons overlap, a single arrow can pop both. The key insight is that by sorting balloons by their starting position, we can process them left to right and greedily merge overlapping intervals.

When we encounter a new balloon, we check if it overlaps with the previous group. If it does, we shrink the overlap region by taking the minimum of the end values. If not, we need a new arrow. We start by assuming each balloon needs its own arrow, then subtract one for each overlap we find.

Algorithm

Sort the intervals by their starting position.
Initialize res as the total number of balloons and track the previous interval's end.
For each subsequent balloon:
- If it overlaps with the previous group (its start is at or before the tracked end), decrement res and update the tracked end to be the minimum of both ends.
- Otherwise, start a new group by updating the tracked end to this balloon's end.
Return res.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        res, prevEnd = len(points), points[0][1]

        for i in range(1, len(points)):
            curr = points[i]
            if curr[0] <= prevEnd:
                res -= 1
                prevEnd = min(curr[1], prevEnd)
            else:
                prevEnd = curr[1]

        return res

public class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int res = points.length, prevEnd = points[0][1];

        for (int i = 1; i < points.length; i++) {
            int[] curr = points[i];
            if (curr[0] <= prevEnd) {
                res--;
                prevEnd = Math.min(curr[1], prevEnd);
            } else {
                prevEnd = curr[1];
            }
        }

        return res;
    }
}

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end());
        int res = points.size(), prevEnd = points[0][1];

        for (int i = 1; i < points.size(); i++) {
            vector<int>& curr = points[i];
            if (curr[0] <= prevEnd) {
                res--;
                prevEnd = min(curr[1], prevEnd);
            } else {
                prevEnd = curr[1];
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} points
     * @return {number}
     */
    findMinArrowShots(points) {
        points.sort((a, b) => a[0] - b[0]);
        let res = points.length,
            prevEnd = points[0][1];

        for (let i = 1; i < points.length; i++) {
            let curr = points[i];
            if (curr[0] <= prevEnd) {
                res--;
                prevEnd = Math.min(curr[1], prevEnd);
            } else {
                prevEnd = curr[1];
            }
        }

        return res;
    }
}

public class Solution {
    public int FindMinArrowShots(int[][] points) {
        Array.Sort(points, (a, b) => a[0].CompareTo(b[0]));
        int res = points.Length, prevEnd = points[0][1];

        for (int i = 1; i < points.Length; i++) {
            int[] curr = points[i];
            if (curr[0] <= prevEnd) {
                res--;
                prevEnd = Math.Min(curr[1], prevEnd);
            } else {
                prevEnd = curr[1];
            }
        }

        return res;
    }
}

func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
        return points[i][0] < points[j][0]
    })
    res, prevEnd := len(points), points[0][1]

    for i := 1; i < len(points); i++ {
        curr := points[i]
        if curr[0] <= prevEnd {
            res--
            prevEnd = min(curr[1], prevEnd)
        } else {
            prevEnd = curr[1]
        }
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun findMinArrowShots(points: Array<IntArray>): Int {
        points.sortBy { it[0] }
        var res = points.size
        var prevEnd = points[0][1]

        for (i in 1 until points.size) {
            val curr = points[i]
            if (curr[0] <= prevEnd) {
                res--
                prevEnd = minOf(curr[1], prevEnd)
            } else {
                prevEnd = curr[1]
            }
        }

        return res
    }
}

class Solution {
    func findMinArrowShots(_ points: [[Int]]) -> Int {
        let sortedPoints = points.sorted { $0[0] < $1[0] }
        var res = sortedPoints.count
        var prevEnd = sortedPoints[0][1]

        for i in 1..<sortedPoints.count {
            let curr = sortedPoints[i]
            if curr[0] <= prevEnd {
                res -= 1
                prevEnd = min(curr[1], prevEnd)
            } else {
                prevEnd = curr[1]
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Greedy (Sort By End Value)

Intuition

Sorting by end position offers a cleaner greedy approach. By shooting an arrow at the end of the first balloon, we maximize the chance of hitting subsequent balloons. Each balloon that starts after our current arrow position requires a new arrow.

This is a classic interval scheduling pattern: always pick the earliest finishing interval first. When we shoot at the end of a balloon, any other balloon that overlaps must have started before or at that point.

Algorithm

Sort the balloons by their ending position.
Start with one arrow at the end of the first balloon.
For each subsequent balloon:
- If it starts after the current arrow position, shoot a new arrow at this balloon's end and increment res.
- Otherwise, the current arrow already covers this balloon.
Return the total arrow count.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        res, prevEnd = 1, points[0][1]

        for i in range(1, len(points)):
            if points[i][0] > prevEnd:
                prevEnd = points[i][1]
                res += 1

        return res

public class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int res = 1, prevEnd = points[0][1];

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > prevEnd) {
                prevEnd = points[i][1];
                res++;
            }
        }

        return res;
    }
}

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });
        int res = 1, prevEnd = points[0][1];

        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > prevEnd) {
                prevEnd = points[i][1];
                res++;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} points
     * @return {number}
     */
    findMinArrowShots(points) {
        points.sort((a, b) => a[1] - b[1]);
        let res = 1,
            prevEnd = points[0][1];

        for (let i = 1; i < points.length; i++) {
            if (points[i][0] > prevEnd) {
                prevEnd = points[i][1];
                res++;
            }
        }

        return res;
    }
}

public class Solution {
    public int FindMinArrowShots(int[][] points) {
        Array.Sort(points, (a, b) => a[1].CompareTo(b[1]));
        int res = 1, prevEnd = points[0][1];

        for (int i = 1; i < points.Length; i++) {
            if (points[i][0] > prevEnd) {
                prevEnd = points[i][1];
                res++;
            }
        }

        return res;
    }
}

func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })
    res, prevEnd := 1, points[0][1]

    for i := 1; i < len(points); i++ {
        if points[i][0] > prevEnd {
            prevEnd = points[i][1]
            res++
        }
    }

    return res
}

class Solution {
    fun findMinArrowShots(points: Array<IntArray>): Int {
        points.sortBy { it[1] }
        var res = 1
        var prevEnd = points[0][1]

        for (i in 1 until points.size) {
            if (points[i][0] > prevEnd) {
                prevEnd = points[i][1]
                res++
            }
        }

        return res
    }
}

class Solution {
    func findMinArrowShots(_ points: [[Int]]) -> Int {
        let sortedPoints = points.sorted { $0[1] < $1[1] }
        var res = 1
        var prevEnd = sortedPoints[0][1]

        for i in 1..<sortedPoints.count {
            if sortedPoints[i][0] > prevEnd {
                prevEnd = sortedPoints[i][1]
                res += 1
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Using Subtraction for Comparator with Large Values

When sorting intervals with coordinates that can be very large (up to 2^31 - 1) or very small (down to -2^31), using a[0] - b[0] as a comparator can cause integer overflow. For example, comparing [-2147483648, 0] with [2147483647, 0] would overflow. Always use Integer.compare(a[0], b[0]) in Java or explicit comparison operators like a[0] < b[0] in other languages.

Not Updating the Overlap Region Correctly

When merging overlapping balloons, you must shrink the overlap region by taking the minimum of the end values, not the maximum. If balloon A ends at 6 and balloon B ends at 4, the arrow must be shot at or before position 4 to hit both. Forgetting to update prevEnd = min(curr[1], prevEnd) will cause incorrect counts when a later balloon extends beyond the current overlap region.

Confusing Inclusive vs Exclusive Overlap Checks

The problem states that balloons touching at a single point can be burst by one arrow. This means the overlap check should be curr[0] <= prevEnd (inclusive), not curr[0] < prevEnd. Missing this edge case will count extra arrows for balloons that just touch at their boundaries.