Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X

Bursting Balloons

Average time to solve is 40m
Asked in companies

Problem statement

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 ( Input/output format, Notes, Images )
1 <= N <= 10^5
1 <= ARR[i] <= 10^9

Time Limit: 1sec
Sample Input 1:
2 1 5 4 3
Sample Output 1:
Explanation of the Sample Input1:
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.
Sample Input 2:
3 2 1
Sample Output 2:
Explanation of the Sample Input 2:
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.
Full screen