Category Archives: Heap

Kth smallest element in a row-wise and column-wise sorted Matrix

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