Ninja and the Nested Ranges II

Hard
0/120
Average time to solve is 45m
profile
Contributed by
9 upvotes
Asked in company
Apple

Problem statement

Ninja gained confidence while playing with ranges. So, he decided to show off his skills to his crush, Nina. But Nina is hard to impress. She gave him ‘N’ ranges in the form of [Ai, Bi] and asked him to determine for each range how many other ranges it contains and how many other ranges contain it. Ninja finds it challenging to solve the problem and needs your help to impress Nina?

Your task is to return a list of two arrays, ‘RESULT’ where for each range ‘RESULT[ 0 ]’ is an array of size ‘N’ that stores the count of ranges a range contains and ‘RESULT[ 1 ]’ is an array of size ‘N’ that stores the count of ranges a range is contained by.

Note: 
Range [X,Y] contains range [A,B] if 'X' <= 'A' and 'Y' >= 'B'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of integers in the array, ‘RANGES’.

The next ‘N’ lines of each test case contain two space-separated integers, ‘Ai’ and ‘Bi’ representing the range: [Ai, Bi].
Output Format: 
For each test case, return a list of two arrays, ‘RESULT’ where for each range ‘RESULT[ 0 ]’ is an array of size ‘N’ that stores the count of ranges a range contains and ‘RESULT[ 1 ]’ is an array of size ‘N’ that stores the count of ranges a range is contained by.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 5
1 <=  N <= 2000
1 <= Ai < Bi <= 10 ^ 6

All ranges are distinct.

Where ‘T’ is the number of test cases, ‘N’ is the number of ranges in the array, ‘RANGES’ and ‘Ai’ and ‘Bi’ are the integers representing the ‘i’th range: [Ai, Bi] in array ‘RANGES’.

Time limit: 1 second.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
2
3
3 8
1 3
7 8
4
4 9
9 10
4 10
2 3
Sample Output 1:
1 0 0
0 0 1
0 0 2 0
1 1 0 0
Explanation of Sample Output 1:
Test Case 1 :  
For ‘RESULT[ 0 ]’ array:
Since the range [3, 8] contains only one range: [7, 8], the output corresponding to [3, 8] is 1.
The range [1, 3] does not contain any of the ranges. Therefore, the output corresponding to [1, 3] is 0.
The range [7, 8] does not contain any of the ranges. Therefore, the output corresponding to [7, 8] is 0.

For ‘RESULT[ 1 ]’ array:
The range [3, 8] is not contained by any of the ranges. Therefore, the output corresponding to [3, 8] is 0.
The range [1, 3] is not contained by any of the ranges. Therefore, the output corresponding to [1, 3] is 0.
Since the range [7, 8] is contained by only one range: [3, 8], the output corresponding to [7, 8] is 1.

Test Case 2 :     
For ‘RESULT[ 0 ]’ array:
The range [4, 9] does not contain any of the ranges. Therefore, the output corresponding to [4, 9] is 0.
The range [9, 10] does not contain any of the ranges. Therefore, the output corresponding to [9, 10] is 0.
Since the range [4, 10] contains two ranges: [4, 9] and [9, 10], the output corresponding to [4, 10] is 2.
The range [2, 3] does not contain any of the ranges. Therefore, the output corresponding to [2, 3] is 0.

For ‘RESULT[ 1 ]’ array:
Since the range [4, 9] is contained by only one rang:e [4, 10], the output corresponding to [4, 9] is 1.
Since the range [9, 10] is contained by only one range: [4, 10], the output corresponding to [9, 10] is 1.
The range [4, 10] is not contained by any of the ranges. Therefore, the output corresponding to [4, 10] is 0.
The range [2, 3] is not contained by any of the ranges. Therefore, the output corresponding to [2, 3] is 0.
Sample Input 2:
2
5
5 8
8 11
5 13
13 14
3 15
4
22 91
25 40
66 85
57 83
Sample Output 2:
0 0 2 0 4
2 2 1 1 0
3 0 0 0
0 1 1 1
Hint

Use brute force approach and check for every range.

Approaches (2)
Brute Force

The idea is to use the brute force approach. For each range in the ‘RANGES’, we will check all the other ranges whether it contains some other range and if some other range contains it.

 

Algorithm:

  • Declare a vector of vectors of integers, ‘RESULT’ to store the final result.
  • Declare a vector of integers, ‘RESULT1’ of size ‘N’, where ‘RESULT1[ i ]’ will store 1 if the ‘i’th range contains some other range. Initially, fill it with zeroes.
  • Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
  • Run a loop for i = 0 to N - 1.
    • Declare two integer variables, ‘X’ and ‘Y’ and assign ‘RANGES[ i ][ 0 ]’ and ‘RANGES[ i ][ 1 ]’ to them, respectively.
    • Run a loop for j = 0 to N - 1.
      • If i == j, that shows that ranges are the same. Therefore,
        • Skip the below steps.
      • Else, declare two integer variables, ‘A’ and ‘B’ and assign ‘RANGES[ j ][ 0 ]’ and ‘RANGES[ j ][ 1 ]’ to them, respectively.
      • If X <= A && Y >= B, that shows that ‘i’th range contains the ‘j’th range. Therefore,
        • Increment the ‘RESULT1[ i ]’ by 1.
      • If X >= A && Y <= B, that shows that ‘i’th range is contained by the ‘j’th range. Therefore,
        • Increment the ‘RESULT2[ i ]’ by 1.
  • Push ‘RESULT1’ to the ‘RESULT’.
  • Push ‘RESULT2’ to the ‘RESULT’
  • In the end, return ‘RESULT’.
Time Complexity

O(N ^ 2), where ‘N’ is the number of ranges in the array, ‘RANGES’.

 

The outer loop runs for each element of the array within which the inner loop also runs for each element of the array. Therefore, overall time complexity = O(N) * O(N) = O(N ^ 2).

Space Complexity

O(1).

 

Since no auxiliary space is required. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja and the Nested Ranges II
Full screen
Console