Furthest Building You Can Reach

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.

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.

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.

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

In the first step, Ninja can use 1 ladder to go to the 2nd building. Then the 3rd building has a height smaller than the 2nd building so he jumps to the 3rd building. Now he does not have sufficient ladders or bricks to go to the 4th building, hence the answer is 3.

Brute Force

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.

Time Complexity

O(N ^ 2 * log(N)), where N is the size of ‘HEIGHTS’.

For each building from 1 to ‘N’ we check if it is reachable or not. And for each building we do the sum of the ‘M’ - ‘ladder’ smallest increments till now, which in the worst case can have a size ’N’. Hence the time complexity is O(N ^ 2 * log(N)).

Space Complexity

O(N), where N is the size of ‘HEIGHTS’.

If the building's heights are in increasing order, then we can encounter at max ‘N’ increments. Therefore at any index, we add at max ‘N’ values to the multiset. Each value takes O(1) space in the multiset which makes the space complexity O(‘N’).

Furthest Building You Can Reach

Problem statement

Sample input 1:

Sample output 1:

Explanation for sample input 1:

Sample input 2:

Sample output 2:

Explanation for sample input 2: