Published on

Coding Practice: Minimum Number of Arrows to Burst Balloons

Authors

Problem

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/

Example 1:


_5
Input: points = [[10,16],[2,8],[1,6],[7,12]]
_5
Output: 2
_5
Explanation: The balloons can be burst by 2 arrows:
_5
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
_5
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Solution

Step 1

Create implementation custom type Points to create custom sort with provide Len() int, Swap(i, j int), and Less(i, j int) bool. See the example from sort package documentation for more details

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 2

Type cast [][]int to Points then check if intervals is empty return 0.

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 3

Sort the intervals values. Keep in mind make sure import package sort first if trying in local computer, because in the leetcode editor is already imported.

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 4

Iterate through the sorted array and keep track of the rightmost end point of a burst balloon

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 5

When we encounter a new balloon, if its start x-coordinate is less than or equal to the rightmost end point, we don't need to shoot a new arrow as the current arrow will burst the new balloon as well.

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 6

If the start x-coordinate is greater than the rightmost end point, we need to shoot a new arrow and update the rightmost end point to be the end x-coordinate of the new balloon. This way, we can determine the minimum number of arrows needed to burst all the balloons.

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 7

This way, we can determine the minimum number of arrows needed to burst all the balloons.

solution.go

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}

Step 1

Create implementation custom type Points to create custom sort with provide Len() int, Swap(i, j int), and Less(i, j int) bool. See the example from sort package documentation for more details

Step 2

Type cast [][]int to Points then check if intervals is empty return 0.

Step 3

Sort the intervals values. Keep in mind make sure import package sort first if trying in local computer, because in the leetcode editor is already imported.

Step 4

Iterate through the sorted array and keep track of the rightmost end point of a burst balloon

Step 5

When we encounter a new balloon, if its start x-coordinate is less than or equal to the rightmost end point, we don't need to shoot a new arrow as the current arrow will burst the new balloon as well.

Step 6

If the start x-coordinate is greater than the rightmost end point, we need to shoot a new arrow and update the rightmost end point to be the end x-coordinate of the new balloon. This way, we can determine the minimum number of arrows needed to burst all the balloons.

Step 7

This way, we can determine the minimum number of arrows needed to burst all the balloons.

solution.go
ExpandClose

_35
type Points [][]int
_35
_35
func (point Points) Len() int {
_35
return len(point)
_35
}
_35
_35
func (point Points) Swap(i, j int) {
_35
point[i], point[j] = point[j], point[i]
_35
}
_35
_35
func (point Points) Less(i, j int) bool {
_35
return point[i][1] < point[j][1]
_35
}
_35
_35
_35
func findMinArrowShots(points [][]int) int {
_35
intervals := Points(points)
_35
if len(intervals) == 0 {
_35
return 0
_35
}
_35
_35
sort.Sort(intervals)
_35
_35
count := 1
_35
start := intervals[0][1]
_35
for i := 1; i < len(intervals); i++ {
_35
if intervals[i][0] <= start {
_35
continue
_35
}
_35
count++
_35
start = intervals[i][1]
_35
}
_35
_35
return count
_35
}