Last Updated: 5 Apr, 2021
Furthest Building You Can Reach
Moderate
Asked in companies
Ninja is in the mood for a walk over the city, but being a ninja he prefers jumping over building roofs instead of walking through the streets.
The height of the buildings in his city can be represented through an array ‘HEIGHTS’ where ‘HEIGHT[i]’ is the height of the ith building. Ninja starts his journey from the 1st building and in one step can only travel to the roof of the next building.
While traveling from the ‘i’th to (i+1)th building:
1. If the ith building has a height greater than or equal to the next i.e (i+1)th building then he simply jumps to the next building.
2. Otherwise he uses either {‘HEIGHTS[i+1] -‘HEIGHTS[i]} bricks or just 1 ladder to climb up to the next building.
Having a limited number of bricks say ‘BRICKS’ and a limited number of ladders say ‘LADDERS’ in his Ninja pocket, he wants to know which is the farthest building he can travel up to if he uses the bricks and ladders optimally.
As Ninja is weak in mathematics so he asks for your help, can you help Ninja to find the maximum index of the building he can reach up to(1 based indexing)?
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains three integers ‘N’, ‘BRICKS’ and ‘LADDERS’ denoting the number of buildings, number of bricks, and number of ladders respectively.
The second line contains ‘N’ space-separated distinct integers where the ith integer denotes the height of the ith building.
Output format:
For each test case, print a single line containing a single integer, denoting the maximum index of the building chef can travel up to using the bricks and ladders optimally.
The output of every test case will be printed in a separate line.
Note :
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= T <=10
2 <= N <= 10 ^ 5
1 <= HEIGHTS[i] <= 10 ^ 6
0 <= ‘BRICKS’<= 10 ^ 4
0 <=’LADDERS’ < N
Where ‘T’ denotes the number of test cases, ‘N’ denotes the size of ‘HEIGHTS’ and ‘HEIGHT[i]’ denotes the height of the ith building, ‘BRICKS’ denotes the number of bricks and ‘LADDERS’ denote the number of ladders.
Time limit: 1 second
Approaches
Complete Algorithm :
- We need to think greedily. Assume currently Ninja is standing at building ‘idx’ and ‘HEIGHTS[idx + 1]’ > ‘HEIGHTS[idx]’. When is it optimal for Ninja to use bricks to get to the next building and when should he use a ladder?
- Suppose we are checking whether Ninja can travel till index ‘idx’ and there are m increments he needs to do in the path from 0 to ‘idx’. It’s important to note that out of these m increments, it is always optimal to use a ladder for larger increments i.e suppose he needs to do an increment of height 5 and one of height 3, it’s always optimal to use a ladder for the increment of size 5. This way we use 1 ladder and 3 bricks otherwise we would have to use 1 ladder and 5 bricks. This way we can always save bricks for lower increments, and thus it increases our chance for more increments.
- So for every building ‘idx’ from 1 to ‘N’ this is how we check if building i is reachable or not:
- Keep a multiset ‘store’ which will store all the increments in height we need to do to reach building ‘idx’.
- If the size of this multiset ‘store’ is less than the value of LADDERS’ then it is always possible to reach this building i.e building with index ‘idx’.(We can use that number of ladders).
- Otherwise, we will use ladders for the max ‘ladder’ number of increments and check if the sum of the rest increments is smaller than or equal to the number of bricks. If it is, then it’s possible to reach the building ‘idx’, otherwise not.
In the previous approach we were calculating the ‘store’ multiset every time from index 1 to ‘idx’ though we just needed to find the correct location of the current increment(if any) amongst the previous increments encountered. More formally, we need to find a way to insert a value in an already sorted array, and then check if this new value is one of the max ‘ladder’ values or not.
Steps:
- We will employ a min heap priority queue which supports finding and removing the smallest value in this queue.
- Keep inserting increments in the queue till the size of the queue is not greater than the value of ‘ladder’.
- When the size of the queue is ‘ladder’ + 1, decrease the top value (i.e the smallest value) of the queue from the ‘bricks’ and pop it from the queue. This small value will be compensated by bricks.
- Continue the process till ‘bricks’ is not smaller than 0.
- The first index where the value of ‘bricks’ is less than 0 is the farthest index Ninja can travel up to. If ‘bricks’ remain non zero till the end of the ‘HEIGHTS’, return ‘N’.