Given an NxN matrix Mat. Sort all elements of the matrix.
Example 1:
Input:
N=4
Mat=[[10,20,30,40],
[15,25,35,45] 
[27,29,37,48] 
[32,33,39,50]]
Output:
10 15 20 25 
27 29 30 32
33 35 37 39
40 45 48 50
Explanation:
Sorting the matrix gives this result.
Example 2:
Input:
N=3
Mat=[[1,5,3],[2,8,7],[4,6,9]]
Output:
1 2 3 
4 5 6
7 8 9
Explanation:
Sorting the matrix gives this result.
Your Task:
You don't need to read input or print anything. Your task is to complete the function sortedMatrix() which takes the integer N and the matrix Mat as input parameters and returns the sorted matrix.
Expected Time Complexity:O(N^{2}LogN)
Expected Auxillary Space:O(N^{2})
Constraints:
1<=N<=1000
1<=Mat[i][j]<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def sortedMatrix(self,N,Mat):

        #code here

Solutions:
class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in range(N):
			for j in range(N):
				arr.append(Mat[i][j])
		arr.sort()
		p = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = arr[p]
				p += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		c = []
		for i in range(N):
			for j in range(N):
				c.append(Mat[i][j])
		c.sort()
		k = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = c[k]
				k += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		a = sorted([j for i in Mat for j in i])
		b = []
		c = []
		for i in range(len(a)):
			c.append(a[i])
			if len(c) == N:
				b.append(c)
				c = []
		return b


class Solution:

	def sortedMatrix(self, N, Mat):
		n = N * N
		temp = [0] * n
		k = 0
		for i in range(N):
			for j in range(N):
				temp[k] = Mat[i][j]
				k += 1
		temp.sort()
		z = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = temp[z]
				z += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		a = []
		for i in range(N):
			a.extend(Mat[i])
		a.sort()
		final = [a[i * N:(i + 1) * N] for i in range((len(a) + N - 1) // N)]
		return final


class Solution:

	def sortedMatrix(self, N, Mat):
		l = []
		for i in Mat:
			l += i
		k = []
		l.sort()
		for i in range(0, len(l), N):
			j = l[i:i + N]
			k.append(j)
		return k


import heapq

class Solution:

	def sortedMatrix(self, N, Mat):
		Mat = [sorted(matrix) for matrix in Mat]
		hmap = []
		ans = []
		for i in range(N):
			hmap.append([Mat[i][0], i, 0])
		heapq.heapify(hmap)
		while len(hmap) > 0:
			ele = heapq.heappop(hmap)
			ans.append(ele[0])
			if ele[2] < len(Mat[ele[1]]) - 1:
				heapq.heappush(hmap, [Mat[ele[1]][ele[2] + 1], ele[1], ele[2] + 1])
		k = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = ans[k]
				k += 1
		return Mat


import heapq

class Solution:

	def sortedMatrix(self, n, matrix):
		res = [[0 for i in range(n)] for j in range(n)]
		heap = []
		for i in range(n):
			matrix[i].sort()
			heapq.heappush(heap, (matrix[i][0], i, 0))
		i = j = 0
		while heap and i < n:
			(el, row, col) = heapq.heappop(heap)
			res[i][j] = el
			if col + 1 < n:
				heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
			if not j + 1 < n:
				i += 1
				j = 0
			else:
				j += 1
		return res


class Solution:

	def sortedMatrix(self, N, matrix):
		temp = [0] * (N * N)
		k = 0
		for i in range(N):
			for j in range(N):
				temp[k] = matrix[i][j]
				k += 1
		temp.sort()
		k = 0
		for i in range(N):
			for j in range(N):
				matrix[i][j] = temp[k]
				k += 1
		return matrix


class Solution:

	def sortedMatrix(self, N, Mat):
		list1 = []
		for r in range(len(Mat)):
			for c in range(len(Mat)):
				list1.append(Mat[r][c])
		list1.sort()
		matrix = [[0 for i in range(N)] for j in range(N)]
		i = 0
		for r in range(len(Mat)):
			for c in range(len(Mat)):
				matrix[r][c] = list1[i]
				i += 1
		return matrix


class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in range(N):
			for j in range(N):
				arr += [Mat[i][j]]
		arr.sort()
		result = [[0 for i in range(N)] for i in range(N)]
		j = 0
		x = 0
		for i in range(N):
			while j < N:
				result[i][j] = arr[x]
				j += 1
				x += 1
			j = 0
		return result


class Solution:

	def sortedMatrix(self, N, mat):
		flat_mat = sorted([elem for row in mat for elem in row])
		k = 0
		for i in range(len(mat)):
			for j in range(len(mat)):
				mat[i][j] = flat_mat[k]
				k += 1
		return mat


class Solution:

	def sortedMatrix(self, N, Mat):
		l = []
		for i in Mat:
			for j in i:
				l.append(j)
		l.sort()
		k = 0
		mat = []
		for i in range(N):
			temp = []
			for j in range(N):
				temp.append(l[k])
				k += 1
			mat.append(temp)
		return mat


class Solution:

	def sortedMatrix(self, N, Mat):
		temp = []
		ans = Mat
		for row in Mat:
			for items in row:
				temp.append(items)
		temp.sort()
		count = 0
		for i in range(N):
			for j in range(N):
				ans[i][j] = temp[count]
				count += 1
		return ans


class Solution:

	def sortedMatrix(self, N, Mat):
		r = []
		for i in range(N):
			for j in range(N):
				r.append(Mat[i][j])
		r.sort()
		n = [[0 for i in range(N)] for j in range(N)]
		l = 0
		for i in range(N):
			for j in range(N):
				n[i][j] = r[l]
				l += 1
		return n


class Solution:

	def sortedMatrix(self, N, mat):
		a = []
		for i in range(N):
			a.extend(mat[i])
		a.sort()
		b = 0
		for i in range(N):
			for j in range(N):
				mat[i][j] = a[b]
				b += 1
		return mat


class Solution:

	def sortedMatrix(self, N, Mat):
		lst = []
		for i in Mat:
			for j in i:
				lst.append(j)
		lst.sort()
		count = 0
		for i in range(0, N):
			for j in range(0, N):
				Mat[i][j] = lst[count]
				count += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		l = []
		m = []
		for i in range(N):
			l += Mat[i]
		l.sort()
		for i in range(0, len(l), N):
			a = l[i:i + N]
			m.append(a)
		return m


import numpy as np

class Solution:

	def sortedMatrix(self, N, Mat):
		Mat = np.array(Mat)
		Mat = Mat.flatten()
		Mat = np.sort(Mat)
		Mat = Mat.reshape(N, N)
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in Mat:
			arr.extend(i)
		arr.sort()
		temp = []
		k = 0
		for i in range(N):
			temp1 = []
			for j in range(N):
				temp1.append(arr[k])
				k += 1
			temp.append(temp1)
		return temp


class Solution:

	def sortedMatrix(self, N, Mat):
		m = []
		for i in range(N):
			for j in range(N):
				m.append(Mat[i][j])
		m.sort()
		for i in range(N * N):
			row = i // N
			col = i % N
			Mat[row][col] = m[i]
		return Mat


class Solution:

	def sortedMatrix(self, n, mat):
		l = []
		m = len(mat[0])
		for i in range(n):
			for j in range(m):
				l.append(mat[i][j])
		l.sort()
		k = 0
		for i in range(n):
			for j in range(m):
				mat[i][j] = l[k]
				k += 1
		return mat


class Solution:

	def sortedMatrix(self, n, mat):
		temp = [0] * (n * n)
		k = 0
		for i in range(0, n):
			for j in range(0, n):
				temp[k] = mat[i][j]
				k += 1
		temp.sort()
		k = 0
		for i in range(0, n):
			for j in range(0, n):
				mat[i][j] = temp[k]
				k += 1
		return mat


import numpy as np

class Solution:

	def sortedMatrix(self, N, Mat):
		a = [i for row in Mat for i in row]
		b = sorted(a)
		c = np.reshape(b, (len(Mat), len(Mat[0])))
		return c


import numpy as np

class Solution:

	def sortedMatrix(self, N, Mat):
		elements = [element for row in Mat for element in row]
		sorted_elements = sorted(elements)
		sorted_matrix = np.reshape(sorted_elements, (len(Mat), len(Mat[0])))
		return sorted_matrix


class MinHeapNode:

	def __init__(self, element, i, j):
		self.element = element
		self.i = i
		self.j = j

class MinHeap:

	def __init__(self, arr, size):
		self.harr = arr
		self.size = size
		i = int((self.size - 1) / 2)
		while i >= 0:
			self.min_heapify(i)
			i -= 1

	def min_heapify(self, i):
		smallest = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < self.size and self.harr[left].element < self.harr[smallest].element:
			smallest = left
		if right < self.size and self.harr[right].element < self.harr[smallest].element:
			smallest = right
		if smallest != i:
			(self.harr[smallest], self.harr[i]) = (self.harr[i], self.harr[smallest])
			self.min_heapify(smallest)

	def left(self, i):
		left = 2 * i + 1
		if left < self.size:
			return left
		return -1

	def right(self, i):
		right = 2 * i + 2
		if right < self.size:
			return right
		return -1

	def get_min(self):
		if self.size:
			return self.harr[0]

	def replace_min(self, x):
		self.harr[0] = x
		self.min_heapify(0)

class Solution:

	def sortedMatrix_(self, N, Mat):
		arr = [MinHeapNode(Mat[i][0], i, 1) for i in range(N)]
		mh = MinHeap(arr, N)
		result = [[0 for i in range(N)] for j in range(N)]
		row = 0
		col = 0
		for count in range(N * N):
			if col >= N:
				col = 0
				row = row + 1
			root = mh.get_min()
			result[row][col] = root.element
			if root.j < N:
				root.element = Mat[root.i][root.j]
				root.j = root.j + 1
			else:
				root.element = float('inf')
			mh.replace_min(root)
			col += 1
		return result

	def sortedMatrix(self, N, Mat):
		temp = []
		arr = [list() for j in range(N)]
		for i in range(N):
			for j in range(N):
				temp.append(Mat[i][j])
		temp.sort()
		k = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = temp[k]
				k += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		l = []
		for i in range(N):
			for j in range(N):
				l.append(Mat[i][j])
		l = sorted(l)
		k = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = l[k]
				k += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, matrix):
		length = len(matrix)
		resultVector = []
		for x in range(length):
			for y in range(length):
				resultVector.append(matrix[x][y])
		resultVector.sort()
		z = 0
		for i in range(length):
			for j in range(length):
				matrix[i][j] = resultVector[z]
				z += 1
		return matrix


class Solution:

	def sortedMatrix(self, N, Mat):
		a = []
		for i in range(N):
			for j in range(N):
				a.append(Mat[i][j])
		a.sort()
		ini = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = a[ini]
				ini += 1
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		matrix = []
		ll = []
		for i in Mat:
			for j in i:
				ll.append(j)
		i = 0
		ll.sort()
		k = 0
		i = 0
		while i < N:
			j = 0
			while j < N:
				Mat[i][j] = ll[k]
				k = k + 1
				j = j + 1
			i = i + 1
		return Mat


class Solution:

	def sortedMatrix(self, n, arr):
		l = []
		for i in range(n):
			for j in range(n):
				l.append(arr[i][j])
		l.sort()
		k = 0
		for i in range(n):
			for j in range(n):
				arr[i][j] = l[k]
				k += 1
		return arr


import numpy as np

class Solution:

	def sortedMatrix(self, N, Mat):
		cat = np.array(Mat)
		cat = cat.flatten()
		cat.sort()
		k = 0
		for i in range(0, N):
			for j in range(0, N):
				Mat[i][j] = cat[k]
				k += 1
		return Mat


import heapq

class Solution:

	def sortedMatrix(self, N, Mat):
		heap = []
		heapq.heapify(heap)
		for row in Mat:
			for val in row:
				heapq.heappush(heap, val)
		colIndex = 0
		res = []
		row = []
		while heap != []:
			if colIndex == N:
				res.append(row)
				row = []
				colIndex = 0
			row.append(heapq.heappop(heap))
			colIndex += 1
		res.append(row)
		return res


import heapq

class Solution:

	def sortedMatrix(self, N, Mat):
		return self.bruteForceHeap(Mat)

	def bruteForceHeap(self, matrix):
		minHeap = []
		for row in matrix:
			for col in row:
				heapq.heappush(minHeap, col)
		N = len(matrix)
		M = len(matrix[0])
		for rowIndex in range(N):
			for colIndex in range(M):
				matrix[rowIndex][colIndex] = heapq.heappop(minHeap)
		return matrix


class Solution:

	def sortedMatrix(self, N, Mat):
		return self.bruteForce1D(Mat)

	def bruteForce1D(self, matrix):
		arr = []
		for row in matrix:
			for col in row:
				arr.append(col)
		arr.sort()
		N = len(matrix)
		M = len(matrix[0])
		index = 0
		for rowIndex in range(N):
			for colIndex in range(M):
				matrix[rowIndex][colIndex] = arr[index]
				index += 1
		return matrix


class Solution:

	def sortedMatrix(self, N, arr):
		ans = []
		for i in arr:
			for j in i:
				ans.append(j)
		ans.sort()
		k = 0
		for i in range(N):
			for j in range(N):
				arr[i][j] = ans[k]
				k += 1
		return arr


class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in Mat:
			arr.extend(i)
		arr.sort()
		ind = 0
		for i in range(N):
			for j in range(N):
				Mat[i][j] = arr[ind]
				ind += 1
		return Mat


class Solution:

	def sortedMatrix(self, n, matrix):
		list = []
		for i in range(n):
			for j in range(n):
				list.append(matrix[i][j])
		list.sort()
		k = 0
		for i in range(n):
			for j in range(n):
				matrix[i][j] = list[k]
				k = k + 1
		return matrix


class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in Mat:
			for j in i:
				arr.append(j)
		arr.sort()
		j = 0
		m = N
		for i in Mat:
			i[:] = arr[j:N]
			j = N
			N = N + m
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		l = []
		for i in range(N):
			for j in range(len(Mat[i])):
				l.append(Mat[i][j])
		sl = sorted(l)
		sm = []
		for i in range(N):
			row = sl[i * N:(i + 1) * N]
			sm.append(row)
		return sm


class Solution:

	def unwind(self, N, Mat):
		lista = []
		for i in range(N):
			for j in range(N):
				lista.append(Mat[i][j])
		return lista

	def make_mat(self, N, lista):
		listb = [[]]
		for i in range(N):
			for j in range(N):
				try:
					listb[i].append(lista[i * N + j])
				except:
					listb.append([])
					listb[i].append(lista[i * N + j])
		return listb

	def sortedMatrix(self, N, Mat):
		lista = self.unwind(N, Mat)
		lista.sort()
		mat2 = self.make_mat(N, lista)
		return mat2


class Solution:

	def sortedMatrix(self, N, Mat):
		a = [0] * (N * N)
		l = 0
		for i in Mat:
			for j in i:
				a[l] = j
				l += 1
		a.sort()
		v = 0
		for i in range(0, N):
			for j in range(0, N):
				Mat[i][j] = a[i * N + j]
				v += 1
		return Mat


import numpy as np

class Solution:

	def sortedMatrix(self, N, Mat):
		arr = []
		for i in range(N):
			for j in range(N):
				arr.append(Mat[i][j])
		arr.sort()
		arr1 = np.array(arr)
		res = arr1.reshape(N, N)
		return res


class Solution:

	def sortedMatrix(self, N, mat):
		c = []
		for i in range(N):
			for j in range(N):
				c.append(mat[i][j])
		c.sort()
		count = 0
		for i in range(N):
			for j in range(N):
				mat[i][j] = c[count]
				count += 1
		return mat


import heapq

class Solution:

	def sortedMatrix(self, N, Mat):
		heap = []
		for row in Mat:
			for i in row:
				heapq.heappush(heap, i)
		for i in range(N):
			for j in range(N):
				Mat[i][j] = heapq.heappop(heap)
		return Mat


class Solution:

	def sortedMatrix(self, N, Mat):
		all_element = [i for row in Mat for i in row]
		all_element.sort()
		y = 0
		for i in range(0, N):
			for j in range(0, N):
				Mat[i][j] = all_element[y]
				y += 1
		return Mat