Kth Minimum Floor

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in company
Adobe

Problem statement

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:

alt

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.

text

Can you help Ninja find the building with ‘K’the building with minimum floors?

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3 4
1 2 8
4 10 11
6 11 12
1 1
4

Sample Output 1 :

6
4

Explanation for Sample Input 1 :

For the first test case, if we write all the floors in increasing order then the 4th building from the beginning will be 6 as shown below:
1, 2, 4, 6, 8, 10, 11, 11, 12

For the second test case, we have only one building in the smart city so this will be the 1’st minimum.

Sample Input 2 :

1
2 4
1 9
14 16

Sample Output 2 :

16

Explanation for Sample Input 2 :

If we write all the floors in increasing order then the 4’th minimum will be 16 as shown below:
1 9 14 16
Hint

Think of using a Brute force approach

Approaches (3)
Brute Force

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:

  1. 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.
  2. Sort the array ‘temp’.
  3. Finally, return ‘temp[K - 1]’.
Time Complexity

 O( N * N * log(N * N) ) where N is the number of rows/columns in the Square City.

 

We will iterate through every element in ‘Square City’. Then sorting ‘temp’ of size ‘N * N’. Hence, the overall time complexity is  O( N * N * log(N*N) ).

Space Complexity

O(N * N), where N is the number of rows/columns in the Square City.

 

We are using ‘temp’ array of size ‘N * N’ for storing elements.

Code Solution
(100% EXP penalty)
Kth Minimum Floor
Full screen
Console