[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.
Input = [6, 5, 1, 4, 5]
Output = 3
Note: This question was asked in Petasense coding interview rounds.
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.
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.
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)
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
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.
Can we solve it in
O(n)using a map?
Do you have any solution in your mind to solve it in O(n) time?