Kth Smallest Integer In Ranges

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
6 upvotes
Asked in company
Walmart

Problem statement

You are given a list of ‘N’ ranges of integers. A range can be represented as (‘start’, ‘end’) where ‘end’ >= ‘start’ and all the integers between ‘start’ and ‘end’ (inclusive) belong to that range.

You need to answer ‘M’ independent queries. In each query, you are given an integer ‘K’ and you need to find the Kth smallest integer of the sequence formed by all the distinct integers of these ‘N’ ranges.

Example:

Let ‘N’= 5,  ‘ranges’ be [(5, 7), (6, 8), (3, 6), (10, 11), (15, 15)], ‘M’ = 3 and these 3 queries are given by array ‘queries’ = [4, 2, 8].
Then the sequence formed by distinct integers present between these ranges in ascending order is [3, 4, 5, 6, 7, 8, 10, 11, 15].
So, 
The 4th smallest element of this sequence is 6.
The 2nd smallest element of this sequence is 4.
The 8th smallest element of this sequence is 11.

Note:

If the sequence has less than K integers then the answer will be -1.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The description of ‘T’ test cases follows-:

The first line of each test case contains two space-separated integers  ‘N’ and ‘M’ representing the number of ranges and number of queries respectively.

Next ‘N’ lines of the test case contain two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the ith range.

The last line of the test cases contains ‘M’ space-separated integers representing ‘M’ queries.
Output format : 
For each test case, print a line consisting of M space-separated integers where the ith integer represents the answer of the ith query.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function. 

In the given function, you need to return an array consisting of ‘M’ integers where the ith integer is the answer of the ith query. In a given function the parameter ‘ranges’ is the list of ‘N’ lists of 2 integers representing ‘N’ ranges where the 1st element of each list represent 'start' and the second element represent 'end' of the range,  and parameter ‘queries’  which is the list of ‘M’ Integers representing queries.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4
1 <= M <= 10^4
1 <= K <= 10^9
1 <= start <= end <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ is the number of ranges, ‘M’ is the number of queries, ‘K’ is the integer in the query, and ‘start’ and ‘end’ represent the first and the last integer of ranges,

Time Limit: 1 sec
Sample Input 1:
2
4 4
5 6 1 2 1 1 1 2
1 2 3 5
5 3
5 7 6 8 3 6 10 11 15 15
4 2 8
Sample Output 1:
1 2 5 -1
6 4 11
Explanation For Sample Input 1:
Test case 1:
Here, ‘N’ = 4, ‘ranges’ = [(5, 6), (1,  2), (1, 1), (1, 2)] , ‘M’ = 4 and queries = [1, 2, 3, 5].
Then the sequence formed by a distinct integer present between these ranges in ascending order is [1, 2, 5, 6].
So, 
The 1st smallest element of this sequence is 1.
The 2nd smallest element of this sequence is 2.
The 3rd smallest element of this sequence is 5.
There exist only four elements in this array so the answer for ‘K’ = 5  is -1.

Test case 2:
See problem statement for an explanation.
Sample Input 2:
2
1 3
2 7
1 2 3
2 1
5 4 3 2
7
Sample Output 2:
2 3 4
-1
Explanation For Sample Input 2:
Test case 1:
Here, ‘N’ = 1, ‘ranges’ = [(2, 7)] , ‘M’ = 3 and queries = [1, 2, 3].
Then the sequence formed by a distinct integer present between these ranges in ascending order is [2, 3, 4, 5, 6, 7].
So, 
The 1st smallest element of this sequence is 2.
The 2nd smallest element of this sequence is 3.
The 3rd smallest element of this sequence is 4.

Test case 2:
Here, ‘N’ = 2, ‘ranges’ = [(5, 4), (3, 2)] , ‘M’ = 1 and queries = [7].
Then the sequence formed by a distinct integer present between these ranges in ascending order is [2, 3, 4, 5].
So, 
There exist only four elements in this array so the answer for ‘K’ = 7  is -1.
Hint

Find the sequence of distinct elements and sort it.

Approaches (3)
Sorting

Appraoch: We will create a list ‘sequence’ and push all distinct elements of these ranges in it. We then sort this list in ascending order. After that, each of the ‘M’ queries can be answered in constant time.

 

Algorithm:

  1. Create a list of integers ‘SEQUENCE’.
  2. Create a HashMap to track whether an integer is already present in the list ‘SEQUENCE’ or not.
  3. Iterate over the list ‘RANGES’ and do the following for each range in that list
    • Run a loop where ‘j’ ranges from start to end of the range, and for each ‘j’ if it is not present in HashMap then add it to HashMap and in the list ‘SEQUENCE’.
  4. Sort the array sequence in ascending order.
  5. Create a list ‘RESULT’ of size ‘M’.
  6. Run a loop where ‘i’ ranges from 0 to M - 1 and in each iteration do following
  7. If ‘QUERIES[i]’ is greater than size of list ‘sequence’ then assign RESULT[i] = -1
  8. Otherwise assign RESULT[i]:= SEQUENCE[k - 1].
  9. Return ‘RESULT’.

 

Time Complexity

O(X * log(X) + M), where ‘X’ is the total number of distinct elements present in all ‘N’ ranges and ‘M’ is the number of queries. 

 

Here we iterate over all the ranges, and insert all elements present in these ranges in the list ‘sequence’. Let ‘X’ be the maximum size of this list, thus it can be sorted in O(XlogX) time. All ‘M’ queries can be answered in constant time. Thus, the final time complexity will be  O(X * log(X) + M).

Space Complexity

O(X + M), where ‘X’ is the total number of distinct elements present in all ‘N’ ranges and ‘M’ is the number of queries. 

 

Space used by the list ‘sequence’ and ‘HashMap’ will be O(X) and space used by list ‘result’ will be O(M). Thus, the final space complexity will be O(X + M).

Code Solution
(100% EXP penalty)
Kth Smallest Integer In Ranges
Full screen
Console