Given K sorted arrays arranged in the form of a matrix of size K*K. The task is to merge them into one sorted array.
Example 1: 
Input:
K = 3
arr[][] = {{1,2,3},{4,5,6},{7,8,9}}
Output: 1 2 3 4 5 6 7 8 9
Explanation:Above test case has 3 sorted
arrays of size 3, 3, 3
arr[][] = [[1, 2, 3],[4, 5, 6], 
[7, 8, 9]]
The merged list will be 
[1, 2, 3, 4, 5, 6, 7, 8, 9].
Example 2: 
Input:
K = 4
arr[][]={{1,2,3,4},{2,2,3,4},
         {5,5,6,6},{7,8,9,9}}
Output:
1 2 2 2 3 3 4 4 5 5 6 6 7 8 9 9 
Explanation: Above test case has 4 sorted
arrays of size 4, 4, 4, 4
arr[][] = [[1, 2, 2, 2], [3, 3, 4, 4],
[5, 5, 6, 6], [7, 8, 9, 9 ]]
The merged list will be 
[1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 
6, 6, 7, 8, 9, 9].
Your Task:
You do not need to read input or print anything. Your task is to complete mergeKArrays() function which takes 2 arguments, an arr[K][K] 2D Matrix containing K sorted arrays and an integer K denoting the number of sorted arrays, as input and returns the merged sorted array ( as a pointer to the merged sorted arrays in cpp, as an ArrayList in java, and list in python)
Expected Time Complexity: O(K^{2}*Log(K))
Expected Auxiliary Space: O(K^{2})
Constraints:
1 <= K <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to merge k sorted arrays.

    def mergeKArrays(self, arr, K):

        # code here

        # return merged list

Solutions:
class Solution:

	def mergeKArrays(self, arr, K):
		b = []
		for i in range(K):
			for j in range(K):
				b.append(arr[i][j])
		b.sort()
		return b


from heapq import *

class Solution:

	def mergeKArrays(self, arr, k):
		ans = []
		heap = []
		for i in range(k):
			heappush(heap, (arr[i][0], i))
		while k > 0:
			elm = heappop(heap)
			ans.append(elm[0])
			arr[elm[1]].pop(0)
			if arr[elm[1]] != []:
				heappush(heap, (arr[elm[1]][0], elm[1]))
			else:
				k -= 1
		return ans


from heapq import *

class Solution:

	def mergeKArrays(self, arr, k):
		heap = []
		for i in range(k):
			a = arr[i]
			heappush(heap, (a[0], 1, i))
		ans = []
		while len(heap) != 0:
			(ele, next_index, kiska) = heappop(heap)
			ans.append(ele)
			if next_index < k:
				heappush(heap, (arr[kiska][next_index], next_index + 1, kiska))
		return ans


class Solution:

	def mergeKArrays(self, arr, K):
		a = []
		for i in range(K):
			a += arr[i]
		return sorted(a)


import heapq as h

class Solution:

	def mergeKArrays(self, arr, k):
		heap = []
		newarr = []
		n = len(arr)
		for i in range(k):
			h.heappush(heap, (arr[i][0], i, 0))
		while heap:
			(element, row, column) = h.heappop(heap)
			newarr.append(element)
			if column < k - 1:
				h.heappush(heap, (arr[row][column + 1], row, column + 1))
		return newarr


class Solution:

	def mergeKArrays(self, arr, K):
		lst = []
		for i in arr:
			lst += i
		lst.sort()
		return lst


class Solution:

	def mergeKArrays(self, arr, K):
		l = []
		for i in arr:
			l.extend(i)
		return sorted(l)


class Solution:

	def mergeKArrays(self, arr, K):
		l = []
		for i in arr:
			for j in i:
				l.append(j)
		l.sort()
		return l


class Solution:

	def mergeKArrays(self, arr, K):
		ans = []
		for l in arr:
			ans.extend(l)
		ans.sort()
		return ans


class Solution:

	def mergeKArrays(self, arr, K):
		res = arr[0]
		for i in range(1, len(arr)):
			res += arr[i]
		res.sort()
		return res


import heapq

class Solution:

	def mergeKArrays(self, matrix, K):
		merged = []
		heap = []
		for i in range(len(matrix)):
			heapq.heappush(heap, (matrix[i][0], i, 0))
		while heap:
			(minElement, minArrayIndex, minElementIndex) = heapq.heappop(heap)
			merged.append(minElement)
			if minElementIndex + 1 < len(matrix[minArrayIndex]):
				heapq.heappush(heap, (matrix[minArrayIndex][minElementIndex + 1], minArrayIndex, minElementIndex + 1))
		return merged


class Solution:

	def mergeKArrays(self, arr, K):
		list1 = list()
		for i in arr:
			list1 += i
		list1.sort()
		return list1


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		nums = []
		for i in arr:
			for j in i:
				nums.append(j)
		heapq.heapify(nums)
		return [heapq.heappop(nums) for i in range(len(nums))]


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		heaps = []
		for i in arr:
			heapq.heappush(heaps, i)
		res = []
		while heaps:
			row = heapq.heappop(heaps)
			res.append(row.pop(0))
			if row:
				heapq.heappush(heaps, row)
		return res


import heapq as h

class Solution:

	def mergeKArrays(self, arr, K):
		minheap = []
		result = []
		for i in range(0, K):
			for j in range(0, K):
				h.heappush(minheap, arr[i][j])
		while minheap:
			result.append(h.heappop(minheap))
		return result


import heapq

class Solution:

	def mergeKArrays(self, arr, k):
		heap = []
		ans = []
		for i in range(k):
			for j in range(k):
				heapq.heappush(heap, arr[i][j])
		while heap:
			ans.append(heapq.heappop(heap))
		return ans


class Solution:

	def mergeKArrays(self, arr, K):
		(a, res) = ([], [])
		for elem in arr:
			a += elem
		a.sort()
		for index in range(0, len(a), K):
			res += a[index:index + K]
		return res


class Solution:

	def mergeKArrays(self, arr, K):
		arr1 = []
		for i in range(K):
			arr1 = arr1 + arr[i]
		arr1.sort()
		return arr1


from queue import PriorityQueue

class Solution:

	def mergeKArrays(self, arr, K):
		q = PriorityQueue()
		for i in range(K):
			for j in range(len(arr[i])):
				q.put(arr[i][j])
		l = []
		while not q.empty():
			l.append(q.get())
		return l


class Solution:

	def mergeKArrays(self, arr, K):
		list1 = []
		for row in range(len(arr)):
			for col in range(len(arr)):
				list1.append(arr[row][col])
		list1.sort()
		return list1


class Solution:

	def mergeKArrays(self, arr, K):
		ans = []
		for i in arr:
			for k in i:
				ans.append(k)
		ans.sort()
		return ans


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		list1 = []
		for i in range(K):
			for j in range(K):
				heapq.heappush(list1, arr[i][j])
		heap = []
		for i in range(len(list1)):
			heap.append(heapq.heappop(list1))
		return heap


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		r = []
		h = []
		for i in range(K):
			heapq.heappush(h, (arr[i][0], i, 0))
		while h:
			(val, arr_index, element_index) = heapq.heappop(h)
			r.append(val)
			if element_index + 1 < K:
				heapq.heappush(h, (arr[arr_index][element_index + 1], arr_index, element_index + 1))
		return r


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		heap = []
		for r in range(len(arr)):
			for c in range(len(arr[0])):
				heapq.heappush(heap, arr[r][c])
		list1 = []
		for i in range(len(heap)):
			list1.append(heapq.heappop(heap))
		return list1


class Solution:

	def mergeKArrays(self, arr, K):
		res = []
		stack = []
		for i in range(len(arr)):
			stack.append([arr[i][0], i, 0])
		stack.sort()
		while stack:
			val = stack[0][0]
			row = stack[0][1]
			col = stack[0][2]
			res.append(val)
			del stack[0]
			if col + 1 < len(arr[0]):
				stack.append([arr[row][col + 1], row, col + 1])
				stack.sort()
		return res


class Solution:

	def mergeKArrays(self, arr, K):
		res = []
		for i in range(len(arr)):
			res.extend(arr[i])
		res.sort()
		return res


class Solution:

	def mergeKArrays(self, arr, K):
		p = []
		for i in range(K):
			li = arr[i]
			for j in range(len(li)):
				p.append(li[j])
		p.sort()
		return p


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		merged = []
		for i in arr:
			for j in i:
				heapq.heappush(merged, j)
		result = []
		while merged:
			val = heapq.heappop(merged)
			heapq.heappush(result, val)
		return result


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		res = []
		for i in range(K):
			for j in range(K):
				res.append(arr[i][j])
		res.sort()
		return res


class Solution:

	def mergeKArrays(self, arr, K):
		a = []
		for i in range(len(arr)):
			for j in range(K):
				a.append(arr[i][j])
		a.sort()
		return a


class Solution:

	def mergeKArrays(self, arr, K):
		l = []
		for i in range(len(arr)):
			l += arr[i]
		l.sort()
		return l


class Node:

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

def heapify_down(arr, parent, n):
	index = parent
	lchild = index * 2 + 1
	rchild = index * 2 + 2
	if index >= n or lchild >= n:
		return
	if arr[index].val > arr[lchild].val:
		index = lchild
	if rchild < n and arr[index].val > arr[rchild].val:
		index = rchild
	if index != parent:
		(arr[index], arr[parent]) = (arr[parent], arr[index])
		heapify_down(arr, index, n)

def heapify_up(arr, n):
	if n <= 0:
		return
	if n & 1 == 0:
		parent = n // 2 - 1
	else:
		parent = n // 2
	if arr[parent].val > arr[n].val:
		(arr[parent], arr[n]) = (arr[n], arr[parent])
		heapify_up(arr, parent)

def buildHeap(temp_arr, n):
	parent = n // 2 - 1
	while parent > -1:
		heapify_down(temp_arr, parent, n)
		parent -= 1

class Solution:

	def mergeKArrays(self, arr, K):
		temp_arr = []
		for i in range(K):
			temp_arr.append(Node(arr[i][0], i, 0))
		buildHeap(temp_arr, K)
		ans = []
		while temp_arr:
			ans.append(temp_arr[0].val)
			i = temp_arr[0].i
			j = temp_arr[0].j
			temp_arr[0] = temp_arr[K - 1]
			K -= 1
			temp_arr.pop(K)
			heapify_down(temp_arr, 0, K)
			j += 1
			if j < len(arr[i]):
				temp_arr.append(Node(arr[i][j], i, j))
				heapify_up(temp_arr, K)
				K += 1
		return ans


class Solution:

	def mergeKArrays(self, arr, K):
		brr = []
		for i in range(K):
			for j in range(K):
				brr.append(arr[i][j])
		return sorted(brr)


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		arr.sort(key=lambda x: x[0])
		min_heap = []
		for i in range(K):
			heapq.heappush(min_heap, (arr[i][0], i, 0))
		ans = []
		while len(min_heap):
			(data, pos, idx) = heapq.heappop(min_heap)
			ans.append(data)
			if idx + 1 < len(arr[pos]):
				heapq.heappush(min_heap, (arr[pos][idx + 1], pos, idx + 1))
		return ans


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		arrays = arr
		heap = []
		for i in range(len(arrays)):
			for j in range(len(arrays[i])):
				heapq.heappush(heap, arrays[i][j])
		merged = []
		while len(heap) > 0:
			merged.append(heapq.heappop(heap))
		return merged


class Solution:

	def mergeKArrays(self, arr, K):
		arrays = arr
		elements = []
		for array in arrays:
			elements += array
		elements.sort()
		return elements


class Solution:

	def mergeKArrays(self, arr, K):
		lst = []
		for i in range(K):
			lst.extend(arr[i])
		return sorted(lst)


from queue import PriorityQueue

def merge_k_sorted_arr(input_mat: [[]], k: int):
	data_queue = PriorityQueue()
	for i in range(k):
		data_queue.put((input_mat[i][0], i, 0))
	final_result = []
	while len(data_queue.queue) > 0:
		first_element = data_queue.get()
		row_number = first_element[1]
		col_number = first_element[2]
		if col_number + 1 < k:
			next_element = input_mat[row_number][col_number + 1]
			data_queue.put((next_element, row_number, col_number + 1))
		final_result.append(first_element[0])
	return final_result

class Solution:

	def mergeKArrays(self, arr, K):
		return merge_k_sorted_arr(arr, K)


import heapq

class Solution:

	def mergeKArrays(self, array, k):
		res = []
		heap = []
		for (arrNum, arr) in enumerate(array):
			heapq.heappush(heap, [arr[0], 0, arrNum])
		while heap:
			cur = heapq.heappop(heap)
			num = cur[0]
			idx = cur[1]
			arrNum = cur[2]
			res.append(num)
			if idx + 1 < k:
				newElement = [array[arrNum][idx + 1], idx + 1, arrNum]
				heapq.heappush(heap, newElement)
		return res


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		k = len(arr)
		heap = []
		result = []
		for i in range(k):
			heapq.heappush(heap, (arr[i][0], i, 0))
		while heap:
			(min_val, arr_idx, elem_idx) = heapq.heappop(heap)
			result.append(min_val)
			if elem_idx + 1 < len(arr[arr_idx]):
				next_elem = arr[arr_idx][elem_idx + 1]
				heapq.heappush(heap, (next_elem, arr_idx, elem_idx + 1))
		return result


from queue import PriorityQueue

class Solution:

	def mergeKArrays(self, arr, K):
		pq = PriorityQueue()
		ans = []
		for i in range(K):
			for j in range(K):
				pq.put(arr[i][j])
		while pq.empty() == False:
			ans.append(pq.get())
		return ans


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		minHeap = []
		ans = []
		for i in range(len(arr)):
			heapq.heappush(minHeap, [arr[i][0], 0, i])
		while minHeap:
			(val, ind, arrNo) = heapq.heappop(minHeap)
			ans.append(val)
			if ind + 1 < len(arr[arrNo]):
				heapq.heappush(minHeap, [arr[arrNo][ind + 1], ind + 1, arrNo])
		return ans


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		queue = []
		answer = []
		for i in range(len(arr)):
			heapq.heappush(queue, [arr[i][0], 0, i])
		while queue:
			(val, index, arrNo) = heapq.heappop(queue)
			answer.append(val)
			if index + 1 < len(arr[arrNo]):
				heapq.heappush(queue, [arr[arrNo][index + 1], index + 1, arrNo])
		return answer


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		li = []
		hp = []
		for i in range(len(arr)):
			for j in range(len(arr)):
				heapq.heappush(li, arr[i][j])
		ans = []
		for i in range(len(li)):
			ans.append(heapq.heappop(li))
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def mergeKArrays(self, arr, K):
		if K == 1:
			return arr[0]

		def merge(a1, a2):
			c = [None] * (len(a1) + len(a2))
			(i, j, k) = (0, 0, 0)
			while i < len(a1) and j < len(a2):
				if a1[i] < a2[j]:
					c[k] = a1[i]
					i += 1
					k += 1
				else:
					c[k] = a2[j]
					j += 1
					k += 1
			while i < len(a1):
				c[k] = a1[i]
				(i, k) = (i + 1, k + 1)
			while j < len(a2):
				c[k] = a2[j]
				(j, k) = (j + 1, k + 1)
			return [len(c), c]
		h = []
		heapify(h)
		for l in arr:
			heappush(h, [len(l), l])
		while len(h) >= 2:
			(a1, a2) = (heappop(h)[1], heappop(h)[1])
			heappush(h, merge(a1, a2))
		return heappop(h)[1]


import numpy

class Solution:

	def mergeKArrays(self, arr, K):
		l = []
		for i in arr:
			l += i
		c = sorted(l)
		return c


class Solution:

	def mergeKArrays(self, arr, k):
		l = []
		for i in range(k):
			for j in range(k):
				l.append(arr[i][j])
		l.sort()
		return l


class Solution:

	def mergeKArrays(self, arr, K):
		l = []
		for x in arr:
			l += x
		return sorted(l)


class Solution:

	def mergeKArrays(self, arr, k):
		queue = []
		for i in range(k):
			for j in range(k):
				queue.append(arr[i][j])
		return sorted(queue)


import heapq

class Solution:

	def mergeKArrays(self, arr, K):
		res = []
		h = []
		for i in range(K):
			heapq.heappush(h, [arr[i][0], i, 0])
		while h:
			(val, arri, vali) = heapq.heappop(h)
			res.append(val)
			if vali + 1 < len(arr[arri]):
				heapq.heappush(h, [arr[arri][vali + 1], arri, vali + 1])
		return res


class node:

	def __init__(self, x, y, z):
		self.data = x
		self.lst = y
		self.ind = z

class heapp:

	def __init__(self):
		self.heap = []
		self.size = 0

	def insert(self, x, y, z):
		self.heap.append(node(x, y, z))
		index = len(self.heap) - 1
		while index > 0 and self.heap[index].data < self.heap[(index - 1) // 2].data:
			parent = (index - 1) // 2
			(self.heap[index], self.heap[parent]) = (self.heap[parent], self.heap[index])
			index = parent

	def pop(self):
		ret = (self.heap[0].data, self.heap[0].lst, self.heap[0].ind)
		l = len(self.heap)
		self.heap[0] = self.heap[l - 1]
		self.heap.pop()
		l = l - 1
		i = 0
		while 1:
			if 2 * i + 1 >= l:
				break
			child = 2 * i + 1
			if 2 * i + 2 < l and self.heap[2 * i + 2].data < self.heap[2 * i + 1].data:
				child = 2 * i + 2
			if self.heap[child].data >= self.heap[i].data:
				break
			(self.heap[i], self.heap[child]) = (self.heap[child], self.heap[i])
			i = child
		return ret
		return temp

	def available(self):
		if len(self.heap) > 0:
			return True
		return False

class Solution:

	def mergeKArrays(self, arr, K):
		n = K
		numbers = arr.copy()
		h = heapp()
		for i in range(n):
			h.insert(numbers[i][0], i, 0)
		ans = []
		while h.available():
			k = h.pop()
			val = k[0]
			i = k[1]
			j = k[2]
			ans.append(val)
			if j + 1 < len(numbers[i]):
				h.insert(numbers[i][j + 1], i, j + 1)
		return ans


import heapq

class Solution:

	def mergeKArrays(self, lists, K):
		mp = {}
		count = 0
		for item in lists:
			mp[count] = (item, (count, 0))
			count += 1
		ans = []
		finalAns = []
		count = 0
		for item in lists:
			(arr, info) = mp[count]
			(index, currInd) = info
			ans.append((arr[currInd], currInd, index))
			count += 1
		heapq.heapify(ans)
		while len(ans):
			(ele, currInd, index) = ans[0]
			heapq.heappop(ans)
			finalAns.append(ele)
			(arr, info) = mp[index]
			if currInd + 1 < len(arr):
				heapq.heappush(ans, (arr[currInd + 1], currInd + 1, index))
				mp[index] = (arr, (index, currInd + 1))
		return finalAns


class Solution:

	def mergeKArrays(self, arr, K):
		arrans = [0] * (K * K)
		index = 0
		for i in range(K):
			for j in range(K):
				arrans[index] = arr[i][j]
				index += 1
		arrans.sort()
		return arrans


class Solution:

	def mergeKArrays(self, arr, K):
		return self.helper(arr, 0, K - 1)

	def helper(self, arr, left, right):
		if left == right:
			return arr[left]
		mid = (left + right) // 2
		leftArr = self.helper(arr, left, mid)
		rightArr = self.helper(arr, mid + 1, right)
		return self.mergeTwoArrays(leftArr, rightArr)

	def mergeTwoArrays(self, arr1, arr2):
		i = j = 0
		tmpArr = []
		while i < len(arr1) or j < len(arr2):
			if j >= len(arr2) or (i < len(arr1) and arr1[i] <= arr2[j]):
				tmpArr.append(arr1[i])
				i += 1
			else:
				tmpArr.append(arr2[j])
				j += 1
		return tmpArr


class Solution:

	def mergeKArrays(self, arr, K):
		a = []
		for i in arr:
			a.extend(i)
		a.sort()
		return a


class Solution:

	def margesort(self, arr):
		if len(arr) > 1:
			mid = len(arr) // 2
			l = arr[:mid]
			r = arr[mid:]
			self.margesort(l)
			self.margesort(r)
			i = j = k = 0
			while i < len(l) and j < len(r):
				if l[i] < r[j]:
					arr[k] = l[i]
					i += 1
				else:
					arr[k] = r[j]
					j += 1
				k += 1
			while i < len(l):
				arr[k] = l[i]
				i += 1
				k += 1
			while j < len(r):
				arr[k] = r[j]
				j += 1
				k += 1

	def mergeKArrays(self, arr, K):
		temp = []
		for i in arr:
			temp.extend(i)
		self.margesort(temp)
		return temp