Ninja And The Nested Ranges

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

Problem statement

Ninja was bored practicing Martial Arts. So, he started playing with ranges. There are ‘N’ ranges in the form of [Ai, Bi] in array/list 'RANGES'. Ninja wants to determine for each range if it contains some other range and if some other range contains it.

Your task is to return a list of two arrays, ‘RESULT’ where ‘RESULT[ 0 ]’ is an array of size ‘N’ that stores the value 1 or 0 for each range indicating if it contains some other range (1) or not (0) and ‘RESULT[ 1 ]’ is an array of size ‘N’ that stores the value 1 or 0 for each range indicating if some other range contains it (1) or not (0).

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 ‘RESULT[ 0 ]’ is an array of size ‘N’ that stores the value 1 or 0 for each range indicating if it contains some other range (1) or not (0) and ‘RESULT[ 1 ]’ is an array of size ‘N’ that stores the value 1 or 0 for each range indicating if some other range contains it (1) or not (0).

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 the 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 1 0
1 1 0 0
Explanation of Sample Output 1 :
Test Case 1 :  
For ‘RESULT[ 0 ]’ array:
Since the range [3, 8] contains the 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 the 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 the ranges [4, 9] and [9, 10], the output corresponding to [4, 10] is 1.
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 the range [4, 10], the output corresponding to [4, 9] is 1.
Since the range [9, 10] is contained by the 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 1 0 1
1 1 1 1 0
1 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. If the condition becomes true at any instant, then mark 1. Otherwise, in the end, mark 0.

 

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.
    • Declare two boolean variables, ‘CONTAINS’ and ‘CONTAINED’. Initialize both of them by false. The ‘CONTAINS’ will be true if the ‘i’th range contains some other range and the ‘CONTAINED’ will be true if the ‘i’th range is contained by some other range.
    • 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 CONTAINS == false && X <= A && Y >= B, that shows that ‘i’th range contains the ‘j’th range. Therefore,
        • Update ‘CONTAINS’ by true.
        • Update ‘RESULT1[ i ]’ by 1.
      • Else if CONTAINED == false && X >= A && Y <= B, that shows that ‘i’th range is contained by the ‘j’th range. Therefore,
        • Update ‘CONTAINED’ by true.
        • Update ‘RESULT2[ i ]’ by 1.
      • If CONTAINS == true && CONTAINED == true, that shows that ‘i’th range contains some other range and some other range also contains it. Therefore,
        • Break out of the inner loop.
  • 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
Full screen
Console