[Solved] Minimum Arrows Required to Burst Balloons

Problem Statement: “Minimum arrows required to burst balloons”

Given an array A, where A[i] represents the height of the balloon from the ground. You are shooting arrows from left to right direction, once you shoot an arrow, if it hits the balloon at height x, the trajectory of the arrow decreases by 1.

Find the minimum number of arrows required to burst all the balloons.

Example

Input = [6, 5, 1, 4, 5]
Output = 3

Note: This question was asked in Petasense coding interview rounds.

Explanation:

It will require three arrows to burst all the balloons.

• With the first arrow, the balloons having height 6, 5, and 4 will be burst.
• With the second arrow, the balloon having the height 1 will be burst.
• The third arrow will burst the balloon at height 5.

When the arrow hits the balloon, we are updating the height of the balloon in the array as -1. This will help us to track the burst balloons.

While traversing the array, if the value is -1, we are skipping that balloon considering it has already burst.

Remember, order of the balloons is important here. Arrow always shoot the balloons from left to right direction.

Python Program

I’m solving this coding questions in Python. You can choose any other programming language of your choice. The logic to solve this problem will be the same.

Prerequisite:

• if-else statement in Python
• Python list
• range() function in Python

Code:

def burst_balloon(arr):
    out = 0
    len_arr = len(arr)
    for i in range(len_arr):
        v = arr[i]
        if v == -1:
            continue;
        v -= 1 
        out = out +1
        arr[i] = -1
        for j in range(i+1, len_arr):
            if arr[j] == v:
                arr[j] = -1
                v -= 1
    return out

A = [6, 5, 1, 4, 5]
out  = burst_balloon(A)
print(out)

Output:

3

Complexity

If you are asked this question in interview, you also have to explain the complexity of your program.

In the above Python program, we traversing the array two times. So, the time complexity of the problem is O(n^2).

Check other competitive coding questions asked in the interview for practice.

This is all about Python program to find the minimum arrows required to burst balloons. If you know any other optimized solution, kindly share it in the comment.