Problem:
Kth smallest element in a row-wise and column-wise sorted Matrix
Given an n x n matrix, where every row and column is sorted in non-decreasing order.
Find the kth smallest element in the given 2D array.Your task is to complete the function kthSmallest which takes two arguments the first is a matrix (mat) and sec argument is the order of the matrix (n) and the function returns the kth smallest element in the matrix.
For example, consider the following 2D array.
10, 20, 30, 40 15, 25, 35, 45 24, 29, 37, 48 32, 33, 39, 50
The 3rd smallest element is 20 and 7th smallest element is 30
Solution
Question is based on Tournament Tree (Winner Tree).
Latest Source Code:
Github: KthSmallestElementInMatrix.java
Output:
When k == 1 then : 10 When k == 2 then : 15 When k == 3 then : 20 When k == 4 then : 24 When k == 5 then : 25 When k == 6 then : 29 When k == 7 then : 30 When k == 8 then : 32 When k == 9 then : 33 When k == 10 then : 35 When k == 11 then : 37 When k == 12then : 39 When k == 13 then : 40 When k == 14 then : 45 When k == 15 then : 48 When k == 16 then : 50