Given a N x N matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the matrix.
Example 1:
Input:
N = 4
mat[][] =     {{16, 28, 60, 64},
                   {22, 41, 63, 91},
                   {27, 50, 87, 93},
                   {36, 78, 87, 94 }}
K = 3
Output: 27
Explanation: 27 is the 3^{rd} smallest element.
 
Example 2:
Input:
N = 4
mat[][] =     {{10, 20, 30, 40}
                   {15, 25, 35, 45}
                   {24, 29, 37, 48}
                   {32, 33, 39, 50}}
K = 7
Output: 30
Explanation: 30 is the 7^{th} smallest element.
Your Task:
You don't need to read input or print anything. Complete the function kthsmallest() which takes the mat, N and K as input parameters and returns the kth smallest element in the matrix.
 
Expected Time Complexity: O(K*Log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 50
1 <= mat[][] <= 10000
1 <= K <= N*N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3

def kthSmallest(mat, n, k): 
    # Your code goes here



Solutions:
def kthSmallest(mat, n, k):
	s = []
	for i in range(n):
		for j in range(n):
			s.append(mat[i][j])
	s.sort()
	return s[k - 1]


def kthSmallest(mat, n, k):
	a = [0 for i in range(n * n)]
	v = 0
	for i in range(n):
		for j in range(n):
			a[v] = mat[i][j]
			v += 1
	a.sort()
	return a[k - 1]


import heapq

def kthSmallest(mat, n, k):
	cmp = lambda a, b: mat[a[0]][a[1]] - mat[b[0]][b[1]]
	heap = [(mat[i][0], i, 0) for i in range(n)]
	heapq.heapify(heap)
	for i in range(k - 1):
		(val, row, col) = heapq.heappop(heap)
		if col < n - 1:
			heapq.heappush(heap, (mat[row][col + 1], row, col + 1))
	return heap[0][0]


def kthSmallest(matrix, n, k):
	(left, right) = (0, n - 1)
	(top, bottom) = (0, n - 1)
	ans = []
	while left <= right and top <= bottom:
		for i in range(left, right + 1):
			ans.append(matrix[top][i])
		top += 1
		if top > bottom:
			break
		for i in range(top, bottom + 1):
			ans.append(matrix[i][right])
		right -= 1
		if left > right:
			break
		for i in range(right, left - 1, -1):
			ans.append(matrix[bottom][i])
		bottom -= 1
		if top > bottom:
			break
		for i in range(bottom, top - 1, -1):
			ans.append(matrix[i][left])
		left += 1
		if left > right:
			break
	ans.sort()
	return ans[k - 1]


def kthSmallest(mat, n, k):
	l = []
	for i in mat:
		l.extend(i)
	l.sort()
	return l[k - 1]


import numpy as np

def kthSmallest(mat, n, k):
	a = np.array(mat)
	x = n * n
	a = a.reshape(x)
	return sorted(a)[k - 1]


def kthSmallest(mat, n, k):
	list = []
	for x in mat:
		list += x
	list.sort()
	return list[k - 1]


def kthSmallest(mat, n, k):
	a = []
	for i in range(n):
		a.extend(mat[i])
	a.sort()
	return a[k - 1]


def kthSmallest(mat, n, k):
	res = []
	for i in mat:
		res += i
	res.sort()
	return res[k - 1]


import numpy as np

def kthSmallest(mat, n, k):
	flattened_list = [element for sublist in mat for element in sublist]
	flattened_list.sort()
	return flattened_list[k - 1]


def kthSmallest(matrix, n, k):
	n = len(matrix)
	(left, right) = (matrix[0][0], matrix[n - 1][n - 1])
	while left < right:
		mid = (left + right) // 2
		count = 0
		j = n - 1
		for i in range(n):
			while j >= 0 and matrix[i][j] > mid:
				j -= 1
			count += j + 1
		if count < k:
			left = mid + 1
		else:
			right = mid
	return left


def kthSmallest(matrix, n, k):
	arr = []
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			arr.append(matrix[i][j])
	arr.sort()
	return arr[k - 1]


def kthSmallest(mat, n, k):
	ans = []
	for i in mat:
		ans += i
	ans.sort()
	return ans[k - 1]


def kthSmallest(mat, n, k):
	high = mat[-1][-1]
	low = mat[0][0]
	while low <= high:
		mid = low + (high - low) // 2
		count = 0
		for row in mat:
			count += upper_bound(row, mid)
		if count < k:
			low = mid + 1
		else:
			high = mid - 1
	return low

def upper_bound(row, mid):
	count = 0
	i = 0
	while i < len(row) and row[i] <= mid:
		count += 1
		i += 1
	return count


def kthSmallest(mat, n, k):
	list1 = []
	for i in range(len(mat)):
		for j in range(len(mat)):
			list1.append(mat[i][j])
	list1.sort()
	return list1[k - 1]


def kthSmallest(mat, n, k):
	(left, right) = (mat[0][0], mat[-1][-1])
	while left <= right:
		mid = (left + right) // 2
		count = 0
		for row in mat:
			count += counter(row, mid)
		if count < k:
			left = mid + 1
		else:
			right = mid - 1
	return left

def counter(row, mid):
	i = 0
	count = 0
	while i < len(row) and row[i] <= mid:
		count += 1
		i += 1
	return count


def kthSmallest(mat, n, k):
	list1 = []
	for r in range(n):
		for c in range(n):
			list1.append(mat[r][c])
	list1.sort()
	return list1[k - 1]


from collections import *
from sys import *
from os import *
from math import *
import heapq

def kthSmallest(mat, n, k):
	list1 = []
	for r in range(n):
		for c in range(n):
			heapq.heappush(list1, mat[r][c])
	heapq.heapify(list1)
	for i in range(k - 1):
		heapq.heappop(list1)
	return heapq.heappop(list1)


def kthSmallest(mat, n, k):
	r = []
	for i in mat:
		for j in i:
			r.append(j)
	r.sort()
	return r[k - 1]


import heapq

def kthSmallest(mat, n, x):
	ans = []
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			heapq.heappush(ans, -mat[i][j])
			if len(ans) > x:
				heapq.heappop(ans)
	return -ans[0]


import heapq

def kthSmallest(mat, n, k):
	heap = []
	for i in range(n):
		for j in range(n):
			heapq.heappush(heap, mat[i][j])
	while k - 1:
		heapq.heappop(heap)
		k -= 1
	return heapq.heappop(heap)


def kthSmallest(mat, n, k):
	sorted_flattened = sorted([j for i in mat for j in i])
	return sorted_flattened[k - 1]


def kthSmallest(mat, n, k):
	l = []
	for i in mat:
		l += i
	return sorted(l)[k - 1]


def kthSmallest(mat, n, k):
	arr = []
	cnt = 0
	for i in range(n):
		for j in range(n):
			arr += [mat[i][j]]
	arr.sort()
	return arr[k - 1]


import heapq

def kthSmallest(mat, n, k):
	heap = []
	for i in range(n):
		heapq.heappush(heap, (mat[i][0], i, 0))
	while k > 0:
		(num, i, j) = heapq.heappop(heap)
		j += 1
		k -= 1
		if j == n:
			continue
		heapq.heappush(heap, (mat[i][j], i, j))
	return num


def kthSmallest(mat, n, k):
	mx = mat[0][n - 1]
	mn = mat[0][0]
	for i in range(1, n):
		if mx < mat[i][n - 1]:
			mx = mat[i][n - 1]
		if mn > mat[i][0]:
			mn = mat[i][0]
	while mn < mx:
		mid = (mn + mx) // 2
		count = 0
		for i in range(n):
			for j in range(n):
				if mat[i][j] > mid:
					break
				count += 1
		if count < k:
			mn = mid + 1
		else:
			mx = mid
	return mx


import numpy as np

def kthSmallest(mat, n, k):
	arr = np.array(mat)
	s = n * n
	arr = arr.reshape(s)
	return sorted(arr)[k - 1]


def countSmallerThanEqualToMid(row, mid):
	low = 0
	high = len(row) - 1
	while low <= high:
		md = (low + high) // 2
		if row[md] <= mid:
			low = md + 1
		else:
			high = md - 1
	return low

def kthSmallest(mat, n, k):
	low = mat[0][0]
	high = mat[-1][-1]
	while low <= high:
		mid = (low + high) // 2
		count = 0
		for i in range(n):
			count += countSmallerThanEqualToMid(mat[i], mid)
		if count < k:
			low = mid + 1
		else:
			high = mid - 1
	return low


def kthSmallest(mat, n, k):
	left = 0
	right = len(mat[0]) - 1
	top = 0
	bottom = len(mat) - 1
	arr = []
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			arr.append(mat[top][i])
		top = top + 1
		for i in range(top, bottom + 1):
			arr.append(mat[i][right])
		right = right - 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				arr.append(mat[bottom][i])
			bottom = bottom - 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				arr.append(mat[i][left])
			left += 1
	arr.sort()
	return arr[k - 1]


def kthSmallest(mat, n, k):
	import heapq
	max_heap = []
	for i in mat:
		for j in i:
			if len(max_heap) == k and j * -1 > max_heap[0]:
				heapq.heappop(max_heap)
				heapq.heappush(max_heap, j * -1)
			elif len(max_heap) < k:
				heapq.heappush(max_heap, j * -1)
	return max_heap[0] * -1


from heapq import *

def kthSmallest1(mat, n, k):
	minheap = []
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			heappush(minheap, mat[i][j])
	while k:
		x = heappop(minheap)
		k -= 1
		if k == 0:
			return x

def kthSmallest(mat, n, k):
	ans = []
	for i in range(len(mat)):
		ans.extend(mat[i])
	ans = sorted(ans)
	return ans[k - 1]


import heapq

def kthSmallest(mat, n, k):
	ans = []
	heapq.heapify(ans)
	for i in range(n):
		for j in range(n):
			heapq.heappush(ans, mat[i][j])
	res = 0
	while k:
		res = heapq.heappop(ans)
		k -= 1
	return res


def kthSmallest(mat, n, k):
	l = sum(mat, [])
	l.sort()
	return l[k - 1]


def kthSmallest(mat, n, k):
	ans = []
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			ans.append(mat[i][j])
	ans.sort()
	return ans[k - 1]


def kthSmallest(mat, n, k):
	arr = []
	for x in mat:
		for y in x:
			arr.append(y)
	arr.sort()
	return arr[k - 1]


import heapq

def kthSmallest(mat, n, k):
	maxH = []
	for i in range(n):
		for j in range(n):
			heapq.heappush(maxH, -mat[i][j])
			if len(maxH) > k:
				heapq.heappop(maxH)
	return -maxH[0]


import heapq

def kthSmallest(mat, n, k):
	pq = []
	for i in range(n):
		heapq.heappush(pq, (mat[i][0], i, 0))
	while k - 1:
		(x, y, z) = heapq.heappop(pq)
		if z < n - 1:
			heapq.heappush(pq, (mat[y][z + 1], y, z + 1))
		k -= 1
	return heapq.heappop(pq)[0]


import sys

def kthSmallest(mat, n, k):
	l = []
	for i in range(n):
		for j in mat[i]:
			l.append(j)
	l.sort()
	return l[k - 1]


def kthSmallest(mat, n, k):
	new_list = []
	for row in mat:
		new_list = new_list + row
	new_list.sort()
	return new_list[k - 1]


def kthSmallest(mat, n, k):
	a = []
	for i in range(n):
		for j in range(n):
			a.append(mat[i][j])
	a.sort()
	return a[k - 1]

def binary(matrix, row, value, C):
	ini = 0
	fini = C
	while fini - ini > 1:
		mid = (ini + fini) // 2
		if matrix[row][mid] > value + 0.1:
			fini = mid
		else:
			ini = mid
	if ini == 0:
		if matrix[row][0] > value:
			ini -= 1
	return ini + 1

def median(matrix, R, C, k):
	mini = 1
	req = k
	maxi = 10000
	while maxi - mini > 1:
		mid = (maxi + mini) // 2
		count = 0
		for i in range(R):
			count += binary(matrix, i, mid, C)
		if count >= req:
			maxi = mid
		else:
			mini = mid
	req2 = 10000
	for i in range(R):
		for j in range(C):
			if matrix[i][j] >= maxi:
				req2 = min(req2, matrix[i][j])
	return req2


import numpy as np

def kthSmallest(mat, n, k):
	array = np.array(mat)
	flat_array = array.flatten()
	k_smallest = np.partition(flat_array, k - 1)[k - 1]
	return k_smallest


import numpy as np

def kthSmallest(mat, n, k):
	arr = np.array(mat)
	new = arr.reshape(-1)
	a = np.sort(new)
	return a[k - 1]


def kthSmallest(mat, n, k):
	x = []
	for i in range(n):
		for j in range(n):
			x.append(mat[i][j])
	x.sort()
	c = x[k - 1]
	return c


import numpy as np

def kthSmallest(mat, n, k):
	arr = np.array(mat)
	arr = arr.flatten()
	arr.sort()
	return arr[k - 1]


def kthSmallest(mat, n, k):
	mat2 = []
	for i in range(0, n):
		for j in range(0, n):
			mat2.append(mat[i][j])
	mat2.sort()
	return mat2[k - 1]


import heapq

def kthSmallest(mat, n, k):
	heap = [(mat[i][0], 0, i) for i in range(n)]
	heapq.heapify(heap)
	for i in range(k - 1):
		(ele, ind, row) = heapq.heappop(heap)
		if ind < n - 1:
			heapq.heappush(heap, (mat[row][ind + 1], ind + 1, row))
	return heapq.heappop(heap)[0]


def kthSmallest(mat, n, k):
	N = []
	for i in mat:
		N = N + i
	N.sort()
	return N[k - 1]


def kthSmallest(mat, n, k):
	arr = []
	for i in mat:
		for j in i:
			arr.append(j)
	arr.sort()
	b = arr[k - 1]
	return b