Bursting Balloons
You are given an array 'ARR' of N integers. Each integer represents the height of a balloon. So, there are N balloons lined up.

Your aim is to destroy all these balloons. Now, a balloon can only be destroyed if the player shoots its head. So, to do the needful, he/ she shoots an arrow from the left to the right side of the platform, from an arbitrary height he/she chooses. The arrow moves from left to right, at a chosen height ARR[i] until it finds a balloon. The moment when an arrow touches a balloon, the balloon gets destroyed and disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if the arrow was moving at height ARR[i], after destroying the balloon it travels at height ARR[i]-1. The player wins this game if he destroys all the balloons in minimum arrows.

You have to return the minimum arrows required to complete the task.

Input Format:

The first line of input contains an integer N representing the size of the array. The second line of input contains N space-separated integers representing the height of the balloons.

Output Format:

Return a single integer i.e. the count of the minimum number of arrows required to complete the task.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Bursting Balloons

You are given an array 'ARR' of N integers. Each integer represents the height of a balloon. So, there are N balloons lined up.

Your aim is to destroy all these balloons. Now, a balloon can only be destroyed if the player shoots its head. So, to do the needful, he/ she shoots an arrow from the left to the right side of the platform, from an arbitrary height he/she chooses. The arrow moves from left to right, at a chosen height ARR[i] until it finds a balloon. The moment when an arrow touches a balloon, the balloon gets destroyed and disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if the arrow was moving at height ARR[i], after destroying the balloon it travels at height ARR[i]-1. The player wins this game if he destroys all the balloons in minimum arrows.

You have to return the minimum arrows required to complete the task.

Input Format:

The first line of input contains an integer N representing the size of the array.

The second line of input contains N space-separated integers representing the height of the balloons.

Output Format:

Return a single integer i.e. the count of the minimum number of arrows required to complete the task.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= N <= 5*10^5
1 <= ARR[i] <= 10^9

Time Limit: 1sec

Accepted Answer

Approach :

1 )We will use a map data structure that will store the height of fired arrows.
2) Start a loop from i = 0 to i = N - 1 and for the i’th balloon if the map contains the value ARR[i] then it
means this balloon will get hit by the previous arrow.
2.1) Therefore decrease the count of ARR[i] in the map and if it becomes 0 remove the key from the
map.
2.2) Increase the count of ARR[i]-1 in the map because there is an arrow at this height available.
3) If the map does not contain the ARR[i] then We will need to fire a new arrow to increase the count of
ARR[i] in the map.
4) Now at the end find the sum of all the arrows present in the map and return it.

TC : O(N)), where N is the number of balloons.
SC : O(N)

Accepted Answer

Using hashmap

We can see here that balloons need to be destroyed in a minimum number of arrows so we need to reuse the arrows, also it’s clear that we need a new arrow for every balloon which is not getting destroyed by any previous arrow.

So we can solve this problem greedily by adding a new arrow for every balloon which is not getting destroyed by existing arrows.

We will use a map data structure that will store the height of fired arrows.
Start a loop from i = 0 to i = N - 1 and for the i’th balloon if the map contains the value ARR[i] then it means this balloon will get hit by the previous arrow.
- Therefore decrease the count of ARR[i] in the map and if it becomes 0 remove the key from the map.
- Increase the count of ARR[i]-1 in the map because there is an arrow at this height available.
If the map does not contain the ARR[i] then We will need to fire a new arrow to increase the count of ARR[i] in the map.
Now at the end find the sum of all the arrows present in the map and return it.

Space Complexity: O(n)Explanation:

O(N), where N is the number of balloons.

As we are storing the heights of balloons in the hashmap and its size can at max grow up to O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of balloons.

As we are visiting every balloon only once and we are also searching and accessing Hashmap N times whereas hashmap has constant time complexity on average. So overall time complexity is O(N).

You are given an array 'ARR' of N integers. Each integer represents the height of a balloon. So, there are N balloons lined up.

You have to return the minimum arrows required to complete the task.

Input Format:

Output Format:

Note:

Constraints:

Top Samsung Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Samsung Software Developer