Last Updated: 1 Feb, 2021
Kth Minimum Floor
Moderate
Asked in company
Ninja is appointed as an architect in Square City. As the name suggests, all the ‘N’ * ‘N’ buildings in the Square City are constructed in a square grid with ‘N’ rows and ‘N’ columns. Each building has a fixed number of floors and is arranged in a row and column in non decreasing order of the number of floors.
For example: One of the Square City with ‘N = 3’ is shown below:
Ninja wants to develop the Square City. So, he selects the ‘K’the building with minimum floors and plans to work on it. As he is busy deciding the design and infrastructure for that building, he asks you for help.
For Example: For the given Square City and ‘K’ = 4, the 4th building having the minimum number of floors is at (2,0) and having 11 floors.
Can you help Ninja find the building with ‘K’the building with minimum floors?
Input Format :
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 two single space-separated integers ‘N’ and ‘K’ where ‘N’ represents the size (number of rows or columns) of Square City and 'K' denotes the Kth building with minimum floors, respectively.
The next ‘N’ lines of each test case contain ‘N’ single space-separated integers denoting the number of floors in each building.
Output Format :
For each test case, print the number of floors in the ‘K’th’ building with minimum floors.
Print the output of each test case in a separate line.
Note :
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 100
1 <= N <= 100
1 <= K <= N
1 <= Square City[i][j] <= 10^6
where 'Square City[i][j]' denotes the number of floors in a row and column wise sorted matrix 'Square City'.
Time limit: 1 sec
Approaches
This problem can be solved by storing all the elements in an array of size ‘N * N’ and sort the array and return Kth minimum element
Algorithm:
We will store all the elements in an array of size ‘N * N’ and then sort the array. Then we return the Kth element from starting.
The kMinFloor function will return the floors in the building having K’th minimum number of floors.
The algorithm for kMinFloor function will be as follows:
- First we will create an array/list ‘temp’ of size ‘N * N’ and store all the elements of the ‘Square City’ in the array/list.
- Sort the array ‘temp’.
- Finally, return ‘temp[K - 1]’.
This problem can be solved by storing all the elements in min-heap and removing top ‘K-1’ elements from the heap. Now, the top element in the heap is our required answer.
Algorithm:
- In a min-heap push all the elements in the ‘Square City’.
- Remove the top ‘K’ - 1 elements from the heap.
- Finally, we return the top element from the heap as our answer.
The main idea behind this approach is that since the ‘Square City’ is sorted in two directions, we can use binary search to find the ‘Kth’ building with minimum floors. As we are searching for the required building, the searching space should be ranging from the smallest to the biggest number in the ‘Square City’. It must be noted that the index here cannot be used to form the searching space since it's not linear to the numbers in the matrix, whose order lies in two directions unlike the index from 0 to the size of array/list in binary search on an array.
Idea:
- Start with the middle of the smallest and biggest floors of the ‘Square City’.
- Count how many floors are smaller than or equal to it row by row. ‘K’ directs the comparison by determining which direction we will proceed in the next round, left part or the right part.
- Keep the answer within the range in each round.
Here is the complete Algorithm:
- Initialize three variables ‘low = Square City[0][0]’ , ‘high = Square City[N -1][N - 1]’ and ‘answer = low’.
- Calculate middle value as ‘mid’ = ( low + high ) / 2 .
- Continue the while loop till ‘low < high’ and in each iteration do the following:
- We call the lesserThanEqualToMid function on each row which will return the number of values which are lesser than or equal to mid using binary search algorithm and store this value in ‘num’. In the function lesserThanEqualToMid we initialize ‘mid’ = 0 ,’low’ = 0, ‘high’ = ‘N’. We want to find the number of floors which are lesser than or equal to the ‘mid’ which is our ‘target’. We do the following while ‘low < high’:
- Find the ‘mid’ of ‘low’ and ‘high’.
- If ‘target’ >= ‘arr[mid]’ (‘arr’ represents the row in the ‘Square City’) then ‘low’ = ‘mid’ + 1.
- Else ‘high’ = ‘mid’.
- Finally, return ‘low’.
- If ‘num < K’ then ‘low = mid + 1’.
- Else ‘high = mid -1’ , and ‘answer = mid’.
- We call the lesserThanEqualToMid function on each row which will return the number of values which are lesser than or equal to mid using binary search algorithm and store this value in ‘num’. In the function lesserThanEqualToMid we initialize ‘mid’ = 0 ,’low’ = 0, ‘high’ = ‘N’. We want to find the number of floors which are lesser than or equal to the ‘mid’ which is our ‘target’. We do the following while ‘low < high’:
- Finally, we return our ‘answer’.