[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 heights 6, 5, and 4 will burst.
• With the second arrow, the balloon having a height of 1 will burst.
• The third arrow will burst the balloon at a height of 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, the order of the balloons is important here. The arrow always shoots the balloons from the left to the right direction.

Python Program

I’m solving this coding question 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

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

Output:

3

Complexity

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

In the above Python program, we traverse the array two times recursively. 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 the Python program to find the minimum arrows required to burst balloons. If you know of any other optimized solution, kindly share it in the comment.