int burstingBalloons(int *arr, int n)

{

map<int,int>mp;

int cnt=0;

for(int i=0;i<n;i++){

if(mp[arr[i]+1]>0){

mp[arr[i]+1]--;

mp[arr[i]]++;

}

else{

cnt++;

mp[arr[i]]++;

}

}

return cnt;

}

Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

Detailed explanation

```
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.
```

```
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.
```

```
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Time Limit: 1sec
```

```
5
2 1 5 4 3
```

```
2
```

```
We need to shoot the arrow at height 5 - which destroys balloons at the height [5, 4, 3], and shoots an arrow at height 2 - which destroys [2, 1]. Therefore we require a minimum of 2 arrows.
```

```
3
3 2 1
```

```
1
```

```
We need to shoot the arrow at height 3 - which destroys balloons at the height [3,2,1]. Therefore we need to shoot only 1 arrow.
```

Hint

We would like to shoot a balloon with the maximum height and then whatever other balloons it can hit will be beneficial to us so think of a way to store the heights of the balloons such that for i’th balloon you should be able to know do you have to fire a new arrow or not.

Approaches

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.

Time Complexity

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

Space Complexity

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

Code Solution

(100% EXP penalty)

Bursting Balloons

All tags

Sort by

Interview problems

easy c++ code

int burstingBalloons(int *arr, int n)

{

map<int,int>mp;

int cnt=0;

for(int i=0;i<n;i++){

if(mp[arr[i]+1]>0){

mp[arr[i]+1]--;

mp[arr[i]]++;

}

else{

cnt++;

mp[arr[i]]++;

}

}

return cnt;

}

134 views

0 replies

0 upvotes

Interview problems

Python all test cases passed

```
from os import *
from sys import *
from collections import *
from math import *
from sys import stdin, setrecursionlimit
setrecursionlimit(10**7)
def burstingBalloons(arr, n):
# Write your code here.
mpp = {}
for i in range(n):
if arr[i] in mpp:
mpp[arr[i]] -= 1
if mpp[arr[i]]==0:
del mpp[arr[i]]
if arr[i]-1 in mpp:
mpp[arr[i]-1] +=1
else:
mpp[arr[i]-1] = 1
#print(mpp)
#print(mpp)
ans = 0
for k in mpp.keys():
ans += mpp[k]
return ans
# Taking Input using Fast I/O.
def takeInput():
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().strip().split(" ")))
return arr, n
# Main.
arr, n = takeInput()
ans = burstingBalloons(arr, n)
print(ans)
```

26 views

0 replies

0 upvotes

Interview problems

C++ Easy Solution || Pass all TestCases

```
#include <iostream>
#include <unordered_map>
using namespace std;
int burstingBalloons(int *arr, int n)
{
unordered_map<int, int> arrowsAtHeight;
for (int i = 0; i < n; i++)
{
if (arrowsAtHeight.find(arr[i]) != arrowsAtHeight.end())
{
// Destroying Ballon So Frequency will decrease.
arrowsAtHeight[arr[i]]--;
if (arrowsAtHeight[arr[i]] == 0)
{
arrowsAtHeight.erase(arr[i]);
}
}
// Frequency of Arrow at 1 less height will increase.
arrowsAtHeight[arr[i] - 1]++;
}
int ans = 0;
for (auto arrow : arrowsAtHeight)
{
ans += arrow.second;
}
return ans;
}
```

737 views

0 replies

0 upvotes

Interview problems

C++ EASY SOLUTION

#include<bits/stdc++.h> using namespace std; void helper(map<int,set<int>> &mpp , int curr , int ind , vector<int> &hit){ hit[ind] = -1; for(auto &i : mpp[curr]){ if(i >= ind){ int save = i; mpp[curr].erase(i); helper(mpp,curr - 1,save,hit); return; } } return; }

int burstingBalloons(int *arr, int n) { map<int,set<int>> mpp; vector<int> hit(n,0); for(int i = 0 ; i < n ; i++){ mpp[arr[i]].insert(i); } int times = 0;

for(int i = 0 ; i < n ; i++){ if(hit[i] == 0){ helper(mpp,arr[i],i,hit); times++; } } return times; }

434 views

0 replies

0 upvotes

Interview problems

Discussion thread on Interview Problem | Bursting Balloons

Hey everyone, creating this thread to discuss the interview problem - Bursting Balloons.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Bursting Balloons

466 views

1 reply

1 upvote