[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 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.
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.
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)
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
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.