Ninja and Meteorites

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
16 upvotes
Asked in company
Uber

Problem statement

You are a scientist observing a peculiar planet ‘NINJA_LAND’. The surface of this planet is a flat X-Y plane. ‘N’ square-shaped meteorites are falling one by one into the planet on the X-axis from space.

With your years of experience and new technology, you have been able to accurately calculate the position of the leftmost X coordinate of meteors on ‘NINJA_LAND’ along with their size.

You store this information in a 2D matrix/list ‘METEORITES’ of size ‘N’ x 2 where ‘METEORITES[i][0]’ denotes the leftmost ‘X’ coordinate of meteor ‘i’ and ‘METEORITES[i][1]’ denotes its size.

As a meteorite ‘M’ falls on ‘NINJA_LAND’ at a specific location, and if some meteorite ‘N’ is already there at that location, then the current meteorite ‘M’ will stick on top of that previous meteorite ‘N’.

Your task is to find the current highest height of any meteorite after each meteorite falls from space. Formally, return an array/list ‘HEIGHTS’ where ‘HEIGHT[i]’ denotes the highest height so far after ‘i’ meteorites have fallen on ‘NINJA_LAND’.

For example:

Let ‘N’ = 3 and ‘METEORITES’ = [[1, 2], [2, 3], [6, 1]].
The position and size of each meteorite are: </br>
‘Meteorite1’:  At 1 position and size of 2.
‘Meteorite2’:  At 2 position and size of 3.
‘Meteorite3’:  At 6 position and size of 1.


So when the first meteorite falls maximum height till now is 2.
When the second meteorite falls maximum height till now is 5.
When the third meteorite falls maximum height till now is 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the number of meteorites.

The next ‘N’ line of each test case contains two single space-separated integers ‘X’ and ‘SIZE’ representing the leftmost X-coordinate and size of the meteorites respectively.
Output Format : 
For each test case, print a single line containing the current highest height of any meteorite after each meteorite falls from space.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
1 <= ‘X’ <= 100000
1 <= ‘SIZE’ <= 10000  

Where ‘T’ denotes the total number of test cases, ‘N’ represents the number of meteorites,’ X’ denotes the leftmost X-coordinate of the current meteorite and ‘SIZE’ represents the size of the current meteorite.

Time Limit: 1 second
Sample Input 1:
1
2
100 100
200 100
Sample Output 1:
100 100

Explanation for Sample Output 1:

For sample test case 1: 


So, when the first meteorite falls maximum height till now is 100.
When the second meteorite falls maximum height till now is 100.
Sample Input 2:
1
3
1 3
4 2
2 2
Sample Output 2:
3 3 5

Explanation for Sample Output 2:

For sample test case 1: 


So when the first meteorite falls maximum height till now is 3.
When the second meteorite falls maximum height till now is 3.
When the third meteorite falls maximum height till now is 5.
Hint

Think of Segment tree and lazy propagation.

Approaches (1)
Segment Tree

We are finding height with the help of the ‘QUERY’ function and then updating the heights with the help of the ‘UPDATE’ function. These functions take O(N) time. And we know we have a data structure that works on queries and updates on intervals. With the help of segment tree data structure we can find the maximum height due to the current meteorite with the help of ‘QUERY’ function in O(log(N)) time and we can update the ‘TEMP_HEIGHT’ array/list with the help of the ‘UPDATE’ function in also O(log(N)) time.

When we want to update an interval all at once, we need to use lazy propagation so that our algorithm works fast.

You can learn about Segment tree and Lazy propagation from here:

https://www.codingninjas.com/free-content/competitive-programming-course/content/segment-tree

https://www.codingninjas.com/blog/2020/08/29/learn-to-build-a-segment-tree/

 

Here is the algorithm:

The algorithm is the same as the above solution algorithm but different in only the ‘QUERY’ and ‘UPDATE’ functions. Here we implement these functions with the help of a segment tree data structure.

  1. We declare a ‘TREE’ and ‘LAZY’ array/list.

 

‘OUERY(‘L1’, ‘R1’)’.

  1. Call ‘QUERY_HELPER(1, 0, ‘N’ - 1, ‘L1’, ‘R1’).

 

‘QUERY_HELPER(‘INDEX’ , ‘START’, ’END’, ‘L1’, ‘R1’)

  1. If LAZY[‘INDEX’] is not equal to 0:
    • ‘Update’ = ‘LAZY[‘INDEX’]’.
    • ‘LAZY[‘INDEX’] = 0.
    • ‘TREE[‘INDEX’] = max(‘TREE[‘INDEX’], Update).
    • If ‘START’ is not equal to ‘END’:
      • LAZY[2 * ‘INDEX’] = max(‘LAZY[2* ‘INDEX’]’, Update).
      • LAZY[2 * ‘INDEX’ + 1] = max(‘LAZY[2* ‘INDEX’ + 1]’, Update).
  2. If ‘START’ is greater than ‘END’ or ‘START’ is greater than ‘R1’ or ‘END’ is less than ‘L1’:
    • Return 0.
  3. If ‘START’ is greater than or equal to ‘L1’ and ‘END’ is less than ‘R1’:
    • Return ‘TREE[‘INDEX’].
  4. ‘MID’ = (‘START’ + ‘END’ ) / 2.
  5. Return max(‘QUERY_HELPER(2* ‘INDEX’, ‘START’, ‘MID’, ‘L1’ , ‘R1’), ‘QUERY_HELPER(2* ‘INDEX’ + 1, ‘MID’ + 1, ‘END’, ‘L1’ , ‘R1’)).

 

UPDATE(‘L1’, ‘R1’ , ‘CURR_MAX_HEIGHT’).

  1. Call UPDATE_HELPER(1, 0, ‘N’ - 1, ‘L1’, ‘R1’ , ‘CURR_MAX_HEIGHT’).

 

UPDATE_HELPER(‘INDEX’, ‘START’, ‘END’ , ‘L1’, ‘R1’ , ‘CURR_MAX_HEIGHT’).

  1. If LAZY[‘INDEX’] is not equal to 0:
    • ‘Update’ = ‘LAZY[‘INDEX’]’.
    • ‘LAZY[‘INDEX’] = 0.
    • ‘TREE[‘INDEX’] = max(‘TREE[‘INDEX’], Update).
    • If ‘START’ is not equal to ‘END’:
      • LAZY[2 * ‘INDEX’] = max(‘LAZY[2* ‘INDEX’]’, Update).
      • LAZY[2 * ‘INDEX’ + 1] = max(‘LAZY[2* ‘INDEX’ + 1]’, Update).
  2. If ‘START’ is greater than ‘END’ or ‘START’ is greater than ‘R1’ or ‘END’ is less than ‘L1’:
    • Return.
  3. If ‘START’ is greater than or equal to ‘L1’ and ‘END’ is less than ‘R1’:
    • ‘TREE[‘INDEX’] = max(‘TREE[‘INDEX’], ‘CURR_MAX_HEIGHT’).
    • If ‘START’ is not equal to ‘END’:
      • LAZY[2 * ‘INDEX’] = max(‘LAZY[2* ‘INDEX’]’, ‘CURR_MAX_HEIGHT’).
      • LAZY[2 * ‘INDEX’ + 1] = max(‘LAZY[2* ‘INDEX’ + 1]’, ‘CURR_MAX_HEIGHT’).
    • Return.
  4. ‘MID’ = (‘START’ + ‘END’ ) / 2.
  5. ‘UPDATE_HELPER(2* ‘INDEX’, ‘START’, ‘MID’, ‘L1’ , ‘R1’,‘CURR_MAX_HEIGHT’ ).
  6.  ‘UPDATE_HELPER(2* ‘INDEX’ + 1, ‘MID’ + 1, ‘END’, ‘L1’ , ‘R1’, ‘CURR_MAX_HEIGHT’).
  7. ‘TREE[‘INDEX’] = max(‘TREE[2* ‘INDEX’], ‘TREE[2* ‘INDEX’ + 1]).
Time Complexity

O(N * log(N)) where ‘N’ represents the number of meteorites.

 

We are traversing the ‘METEOR’ array/list of length ‘N’. While traversing we are calling two functions ‘QUERY’ and ‘UPDATE’. We implemented these two functions with the help of a segment tree hence the time taken by each of these functions is O(log(N). Hence the overall time complexity is O(N * log(N)).

Space Complexity

O(N) where ‘N’ represents the number of meteorites.

 

Because we are using the ‘HEIGHT’ array/list of size ‘N’ where ‘HEIGHT[i]’ denotes the highest height so far after ‘i’ meteorites have fallen on ‘NINJA_LAND’. We are using a map ‘INDEX’ and ‘SORTED_COORDS’ in which we are storing the coordinates of all meteorites. We are using the ‘TREE’ and ‘LAZY’ array/list for the implementation of the segment tree. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja and Meteorites
Full screen
Console