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:

`_5Input: points = [[10,16],[2,8],[1,6],[7,12]]_5Output: 2_5Explanation: 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].`

## 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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
`_35type Points [][]int_35_35func (point Points) Len() int {_35 return len(point)_35}_35_35func (point Points) Swap(i, j int) {_35 point[i], point[j] = point[j], point[i]_35}_35_35func (point Points) Less(i, j int) bool {_35 return point[i][1] < point[j][1]_35}_35_35_35func 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}`