Minimum Number of Arrows to Burst
🔹 Logic
Sort all the balloon intervals by their starting point.
→ This helps process balloons in the correct order.
Start with one arrow — it can burst the first balloon.
Place the arrow at the end position of the first balloon.
→ This means the arrow can burst all balloons overlapping with that range.
For each next balloon:
If its start is greater than the current arrow position,
→ that balloon can’t be burst by the same arrow,
→ so shoot a new arrow and update arrow position to this balloon’s end.
Else,
→ it overlaps, so narrow the arrow’s range by updating arrowPos to the minimum of current and next balloon’s end (to stay within overlap).
After processing all balloons,
→ the total number of arrows shot is your answer.
Time & Space Complexity:
Time: O(n log n) → due to sorting
Space: O(1) → in-place sort, constant extra space
Insert Interval
🔹 Logic
Add the new interval into the list of existing intervals.
→ Because you need to consider it when merging.
Sort all intervals by their start time (ascending).
→ Ensures we can process them in the correct sequence.
Initialize two variables:from = start of the first intervalto = end of the first interval
Iterate through all intervals:
If the next interval’s start ≤ to
→ it overlaps with the current interval, so merge them by updatingto = max(to, next interval’s end)
Else
→ no overlap, so push [from, to] into result and start a new range:from = next interval’s startto = next interval’s end
After the loop ends, push the last [from, to] into result.
The result array now contains all merged intervals after inserting the new one.
Complexity
Time: O(n log n) (for sorting)
Space: O(n) (map + range)
Merge Intervals
🔹 Logic for Merging Intervals
Sort all intervals by their starting point.
Initialize from and to with the start and end of the first interval.
Iterate through remaining intervals:
If the next interval’s start ≤ to, merge it by updating to = max(to, nextEnd).
Otherwise, push [from, to] to the result and start a new range.
After the loop, push the last [from, to] into the result.
Return the merged intervals list.
Time ComplexityO(n log n) → sorting the intervals.
Space ComplexityO(n) → to store the merged result.
Leetcode: 56
Summary Ranges
🔹 Logic
If the array is empty → return an empty list.
Initialize start with the first number (beginning of a range).
Iterate through the array:
When you find a gap (nums[i] ≠nums[i-1] + 1),
→ form a range from start to nums[i-1],
→ push it to rangeList,
→ and set start = nums[i].
After the loop, add the final range (from start to last element).
Return the list of range strings.
Time ComplexityO(n) — single pass through the array.
Space ComplexityO(n) — for storing the list of range strings.
Leetcode : 228
