Given a row wise sorted matrix of size R*C where R and C are always odd, find the median of the matrix.
Example 1:
Input:
R = 3, C = 3
M = [[1, 3, 5], 
     [2, 6, 9], 
     [3, 6, 9]]
Output: 5
Explanation: Sorting matrix elements gives 
us {1,2,3,3,5,6,6,9,9}. Hence, 5 is median. 
 
Example 2:
Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output: 2
Explanation: Sorting matrix elements gives 
us {1,2,3}. Hence, 2 is median.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function median() which takes the integers R and C along with the 2D matrix as input parameters and returns the median of the matrix.
Expected Time Complexity: O(32 * R * log(C))
Expected Auxiliary Space: O(1)
Constraints:
1 <= R, C <= 400
1 <= matrix[i][j] <= 2000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def median(self, matrix, R, C):

    	#code here 

Solutions:
class Solution:

	def median(self, matrix, R, C):
		a = []
		for i in range(len(matrix)):
			a += matrix[i]
		a = sorted(a)
		if len(a) % 2 == 0:
			return (a[len(a) // 2] + a[len(a) // 2 - 1]) / 2
		else:
			return a[len(a) // 2]


class Solution:

	def median(self, matrix, R, C):
		arr = []
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				arr.append(matrix[i][j])
		arr.sort()
		return arr[len(arr) // 2]


class Solution:

	def median(self, matrix, R, C):
		check = []
		for i in matrix:
			check.extend(i)
		b = sorted(check)
		return b[len(b) // 2]


from bisect import bisect_right, bisect_left

class Solution:

	def count(self, matrix, R, C, value):
		r = 0
		for i in range(R):
			r += bisect_right(matrix[i], value)
		return r

	def median(self, matrix, R, C):
		min_value = float('inf')
		max_value = 0
		for r in range(R):
			if matrix[r][0] < min_value:
				min_value = matrix[r][0]
			if matrix[r][-1] > max_value:
				max_value = matrix[r][-1]
		while min_value < max_value:
			mid_value = (min_value + max_value) // 2
			cc = self.count(matrix, R, C, mid_value)
			if cc < (R * C + 1) // 2:
				min_value = mid_value + 1
			else:
				max_value = mid_value
		return min_value


class Solution:

	def median(self, matrix, R, C):
		new = []
		for row in matrix:
			new.extend(row)
		new.sort()
		n = R * C
		median = (n + 1) // 2
		return new[median - 1]


class Solution:

	def median(self, matrix, R, C):
		r = []
		for i in range(R):
			for j in range(C):
				r.append(matrix[i][j])
		r = sorted(r)
		return r[int((len(r) - 1) / 2)]


import bisect

class Solution:

	def median(self, M, R, C):
		minVal = float('inf')
		maxVal = float('-inf')
		for i in range(R):
			minVal = min(minVal, M[i][0])
			maxVal = max(maxVal, M[i][C - 1])
		desired = (R * C + 1) // 2
		while minVal < maxVal:
			mid_val = (minVal + maxVal) // 2
			count = 0
			for i in range(R):
				count += bisect.bisect_right(M[i], mid_val)
			if count < desired:
				minVal = mid_val + 1
			else:
				maxVal = mid_val
		return minVal


class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in matrix:
			l.extend(i)
		l.sort()
		return l[len(l) // 2]


class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				l.append(matrix[i][j])
		m = sorted(l)
		le = len(m)
		med = le // 2
		return m[med]


from decimal import Decimal
import statistics

class Solution:

	def median(self, matrix, R, C):
		a = []
		t = 0
		l = 0
		b = 0
		m = list(sorted(matrix))
		for i in range(0, R):
			for j in range(C):
				a.append(matrix[i][j])
		b = sorted(a)
		n = len(a)
		if n % 2 != 0:
			t = n // 2
			l = b[t]
			return l


from bisect import bisect_right as ub

class Solution:

	def median(self, m, R, C):
		mi = m[0][0]
		mx = 0
		for i in range(R):
			if m[i][0] < mi:
				mi = m[i][0]
			if m[i][C - 1] > mx:
				mx = m[i][C - 1]
		d = (R * C + 1) // 2
		while mi < mx:
			mid = mi + mx >> 1
			place = [0]
			for i in range(R):
				j = ub(m[i], mid)
				place[0] += j
			if place[0] < d:
				mi = mid + 1
			else:
				mx = mid
		return mi


class Solution:

	def median(self, matrix, r, c):

		def count(mat, mid):
			l = 0
			h = len(mat) - 1
			while l <= h:
				m = (l + h) // 2
				if mat[m] > mid:
					h = m - 1
				else:
					l = m + 1
			return l
		low = 0
		high = 2001
		while low <= high:
			mid = (low + high) // 2
			cnt = 0
			for mat in matrix:
				cnt += count(mat, mid)
			if cnt <= r * c // 2:
				low = mid + 1
			else:
				high = mid - 1
		return low


def count(row, mid):
	l = 0
	h = len(row) - 1
	while l <= h:
		md = (l + h) // 2
		if row[md] <= mid:
			l = md + 1
		else:
			h = md - 1
	return l

class Solution:

	def median(self, matrix, R, C):
		l = 1
		h = 1000000000.0
		while l <= h:
			mid = (l + h) // 2
			c = 0
			for i in range(R):
				c += count(matrix[i], mid)
			if c <= R * C // 2:
				l = mid + 1
			else:
				h = mid - 1
		return int(l)


class Solution:

	def getSmallers(self, x, matrix, R, C):
		ans = 0
		for r in matrix:
			(i, j) = (0, C - 1)
			while i <= j:
				m = (i + j) // 2
				if r[m] <= x:
					i = m + 1
				else:
					j = m - 1
			ans += i
		return ans

	def median(self, matrix, R, C):
		(i, j) = (1, 2000)
		n = R * C // 2 + 1
		while i <= j:
			m = i + j >> 1
			c = self.getSmallers(m, matrix, R, C)
			if c >= n:
				j = m - 1
			else:
				i = m + 1
		return j + 1


class Solution:

	def median(self, matrix, R, C):
		list = []
		for x in matrix:
			list += x
		list.sort()
		n = len(list)
		if len(list) % 2 != 0:
			return list[int((n + 1) / 2 - 1)]
		return (list[int(n / 2 - 1)] + list[int(n / 2)]) / 2


class Solution:

	def median(self, matrix, R, C):
		matrix = sorted(sum(matrix, []))
		return matrix[R * C // 2]


class Solution:

	def median(self, matrix, R, C):
		a = []
		for row in matrix:
			for column in row:
				a.append(column)
		a = sorted(a)
		return a[R * C // 2]


class Solution:

	def median(self, matrix, R, C):
		p = -1
		n = R * C
		h = [0] * n
		for i in range(R):
			for j in range(C):
				p = p + 1
				h[p] = matrix[i][j]
		h.sort()
		if n % 2 != 0:
			q = n // 2
			ans = h[q]
		else:
			q = n // 2
			ans = (h[q] + h[q - 1]) / 2
		return ans


class Solution:

	def median(self, matrix, R, C):
		result = []
		for i in matrix:
			result.extend(i)
		result = sorted(result)
		return result[R * C // 2]


class Solution:

	def median(self, matrix, R, C):
		temp = []
		for i in matrix:
			temp.extend(i)
		temp.sort()
		length = R * C
		return temp[length // 2]


from bisect import bisect_right

class Solution:

	def median(self, matrix, R, C):
		start = matrix[0][0]
		end = matrix[0][-1]
		for i in matrix:
			start = min(start, i[0])
			end = max(end, i[-1])
		mid = start + (end - start) // 2
		row = R
		col = C
		while start < end:
			place = 0
			for i in matrix:
				count = bisect_right(i, mid)
				place += count
			if place < (row * col + 1) // 2:
				start = mid + 1
			else:
				end = mid
			mid = start + (end - start) // 2
		return start


class Solution:

	def median(self, matrix, R, C):
		nums = []
		for i in matrix:
			nums.extend(i)
		mid = len(nums) // 2
		nums.sort()
		return nums[mid]


class Solution:

	def median(self, matrix, R, C):
		from itertools import chain
		result = list(chain(*matrix))
		result.sort()
		return result[len(result) // 2]


class Solution:

	def median(self, matrix, R, C):
		(minV, maxV) = (matrix[0][0], matrix[0][C - 1])
		for i in range(1, R):
			if matrix[i][0] < minV:
				minV = matrix[i][0]
			if matrix[i][C - 1] > maxV:
				maxV = matrix[i][C - 1]
		res = minV
		(low, high) = (minV, maxV)
		while low <= high:
			mid = (low + high) // 2
			count = 0
			for i in range(R):
				count += self.elementsLessOrEqualToMid(matrix[i], mid, C)
			if count <= R * C // 2:
				low = mid + 1
			else:
				high = mid - 1
		return low

	def elementsLessOrEqualToMid(self, arr, item, C):
		(low, high) = (0, C - 1)
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] <= item:
				low = mid + 1
			else:
				high = mid - 1
		return low


class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				l.append(matrix[i][j])
		l.sort()
		s = 0
		e = len(l) - 1
		mid = (s + e) // 2
		return l[mid]


class Solution(object):

	def median(self, matrix, R, C):

		def countLesserNums(medianNum):
			countOfSmallerNums = 0
			for row in range(R):
				(left, right) = (0, C - 1)
				while left <= right:
					col = (left + right) // 2
					if matrix[row][col] <= medianNum:
						left = col + 1
					else:
						right = col - 1
				countOfSmallerNums += left
			return countOfSmallerNums
		n = R * C
		(start, end) = (0, 2000)
		while start <= end:
			medianNum = (start + end) // 2
			medianIndex = n // 2
			lesserNumsCount = countLesserNums(medianNum)
			if lesserNumsCount <= medianIndex:
				start = medianNum + 1
			else:
				end = medianNum - 1
		return start


class Solution:

	def median(self, matrix, R, C):
		s = 1
		e = 2000
		n = R * C
		mid = 0
		while s <= e:
			mid = (s + e) // 2
			ans = 0
			for i in range(R):
				l = 0
				h = C - 1
				while l <= h:
					m = (l + h) // 2
					if matrix[i][m] <= mid:
						l = m + 1
					else:
						h = m - 1
				ans += l
			if ans <= n // 2:
				s = mid + 1
			else:
				e = mid - 1
		return s


class Solution:

	def median(self, matrix, R, C):
		list1 = []
		for r in range(len(matrix)):
			for c in range(len(matrix[0])):
				list1.append(matrix[r][c])
		n = len(list1)
		list1.sort()
		if n % 2 == 0:
			return (list1[n // 2] + list1[n // 2 + 1]) / 2
		return list1[n // 2]


class Solution:

	def median(self, mat, R, C):
		n = R * C
		mi = n // 2
		s = 1
		e = 2000
		while s <= e:
			t = (s + e) // 2
			c = 0
			for i in mat:
				sm = 0
				em = C - 1
				while sm <= em:
					mid = (sm + em) // 2
					if i[mid] <= t:
						sm = mid + 1
					else:
						em = mid - 1
				c += sm
			if c <= mi:
				s = t + 1
			else:
				e = t - 1
		return s


class Solution:

	def median(self, matrix, R, C):
		main_matrix = []
		for row in matrix:
			main_matrix += row
		main_matrix.sort()
		return main_matrix[len(main_matrix) // 2]


class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in range(R):
			for j in range(C):
				l.append(matrix[i][j])
		l.sort()
		return l[R * C // 2]


class Solution:

	def median(self, matrix, R, C):
		low = 1
		high = 2000
		while low <= high:
			mid = (low + high) // 2
			count = 0
			for i in range(R):
				count += self.countsmallerthanmid(matrix[i], mid)
			if count <= R * C // 2:
				low = mid + 1
			else:
				high = mid - 1
		return int(low)

	def countsmallerthanmid(self, row, mid):
		l = 0
		h = len(row) - 1
		while l <= h:
			md = (l + h) // 2
			if row[md] <= mid:
				l = md + 1
			else:
				h = md - 1
		return l


class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in matrix:
			for j in i:
				l.append(j)
		l.sort()
		n = int(len(l) / 2) + 1
		return l[n - 1]


from statistics import median
from bisect import bisect_right as upper_bound
MAX = 100

def binaryMedian(m, r, d):
	mi = m[0][0]
	mx = 0
	for i in range(r):
		if m[i][0] < mi:
			mi = m[i][0]
		if m[i][d - 1] > mx:
			mx = m[i][d - 1]
	desired = (r * d + 1) // 2
	while mi < mx:
		mid = mi + (mx - mi) // 2
		place = [0]
		for i in range(r):
			j = upper_bound(m[i], mid)
			place[0] = place[0] + j
		if place[0] < desired:
			mi = mid + 1
		else:
			mx = mid
	return mi

class Solution:

	def median(self, arr, R, C):
		return binaryMedian(arr, R, C)


class Solution:

	def median(self, matrix, R, C):
		soln = []
		for i in range(R):
			for j in range(C):
				soln.append(matrix[i][j])
		soln.sort()
		med = len(soln) // 2
		return soln[med]


class Solution:

	def median(self, matrix, R, C):
		arr = []
		for ele in matrix:
			for num in ele:
				arr.append(num)
		arr.sort()
		index = len(arr) // 2
		return arr[index]


class Solution:

	def median(self, matrix, R, C):
		lis = []
		for i in range(R):
			lis += matrix[i]
		lis.sort()
		return lis[len(lis) // 2]


class Solution:

	def median(self, matrix, R, C):
		a = []
		for i in matrix:
			a += i
		a.sort()
		return a[R * C // 2]


class Solution:

	def median(self, matrix, R, C):
		arr = []
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				arr.append(matrix[i][j])
		arr.sort()
		mid = len(arr) // 2
		if len(matrix) % 2 == 0:
			median = (arr[mid] + arr[mid - 1]) / 2
		else:
			median = arr[mid]
		return median


import sys

def findcount(arr, target):
	left = 0
	right = len(arr) - 1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] <= target:
			left = mid + 1
		else:
			right = mid - 1
	return left

class Solution:

	def median(self, arr, R, C):
		left = -1
		right = -1
		for row in range(R):
			left = min(left, arr[row][0])
			right = max(right, arr[row][-1])
		desired = (R * C + 1) // 2
		while left < right:
			mid = (left + right) // 2
			cnt = 0
			for i in range(R):
				cnt += findcount(arr[i], mid)
			if cnt < desired:
				left = mid + 1
			else:
				right = mid
		return left


from bisect import bisect

class Solution:

	def median(self, matrix, R, C):
		arr = []
		for i in range(R):
			for j in range(C):
				arr.append(matrix[i][j])
		arr.sort()
		if len(arr) % 2 == 0:
			return (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) // 2
		return arr[len(arr) // 2]


class Solution:

	def median(self, matrix, R, C):
		l = []
		for r in range(len(matrix)):
			for c in range(len(matrix[0])):
				l.append(matrix[r][c])
		l.sort()
		mid = len(l) // 2
		if len(l) % 2 == 0:
			median = (l[mid - 1] + l[mid]) / 2
		else:
			median = l[mid]
		return median


class Solution:

	def median(self, matrix, R, C):
		l = [j for i in matrix for j in i]
		l.sort()
		if len(l) % 2 == 0:
			v = len(l) // 2
			return l[v] + l[v - 1] / 2
		else:
			v = len(l) // 2
			return l[v]


class Solution:

	def countSmallerThanMid(self, 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 median(self, matrix, R, C):
		low = 1
		high = 1000000000.0
		while low <= high:
			mid = (low + high) // 2
			count = 0
			for i in range(R):
				count += self.countSmallerThanMid(matrix[i], mid)
			if count <= R * C // 2:
				low = mid + 1
			else:
				high = mid - 1
		return int(low)


class Solution:

	def no_of_elements_lesser_or_equal(self, matrix, item, C):
		cnt = 0
		for arr in matrix:
			(low, high) = (0, C - 1)
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] > item:
					high = mid - 1
				else:
					low = mid + 1
			cnt += low
		return cnt

	def median(self, matrix, R, C):
		(low, high, n) = (1, 2000, R * C)
		while low <= high:
			mid = (low + high) // 2
			cnt = self.no_of_elements_lesser_or_equal(matrix, mid, C)
			if cnt > n // 2:
				high = mid - 1
			else:
				low = mid + 1
		return low


class Solution:

	def median(self, matrix, R, C):
		mn = matrix[0][0]
		mx = matrix[0][C - 1]
		for i in range(R):
			if matrix[i][0] < mn:
				mn = matrix[i][0]
			if matrix[i][C - 1] > mx:
				mx = matrix[i][C - 1]
		target_count = (R * C + 1) // 2
		while mn < mx:
			count = 0
			mid = (mn + mx) // 2
			for i in range(R):
				for j in range(C):
					if matrix[i][j] > mid:
						break
					count += 1
			if count < target_count:
				mn = mid + 1
			else:
				mx = mid
		return mx


import statistics

class Solution:

	def median(self, matrix, R, C):
		lst = []
		for i in range(R):
			for j in range(C):
				lst.append(matrix[i][j])
		return int(statistics.median(lst))


class Solution:

	def median(self, matrix, R, C):
		a = []
		for i in range(len(matrix)):
			a.extend(matrix[i])
		a.sort()
		b = len(a)
		if b % 2 != 0:
			d = b // 2
			return a[d]
		else:
			e = b // 2
			c = a[b // 2] + a[e - 1]
			return c / 2


import numpy as np

class Solution:

	def median(self, matrix, R, C):
		matrix.sort()
		b = np.median(matrix)
		return int(b)


from bisect import bisect_right

def binary_search_last(a, l, r, x):
	if x >= a[-1]:
		return bisect_right(a, x, l, r)
	return bisect_right(a, x, l, r) - 1

class Solution:

	def median(self, matrix, R, C):
		mi = matrix[0][0]
		mx = 0
		for i in range(R):
			if matrix[i][0] < mi:
				mi = matrix[i][0]
			if matrix[i][C - 1] > mx:
				mx = matrix[i][C - 1]
		desired = (R * C + 1) // 2
		while mi <= mx:
			mid = mi + (mx - mi) // 2
			place = 0
			for i in range(r):
				j = binary_search_last(matrix[i], 0, C - 1, mid) + 1
				place += j
			if place >= desired:
				mx = mid - 1
			else:
				mi = mid + 1
		return mi


class Solution:

	def median(self, matrix, R, C):
		(miin, maax) = (1, 2000)
		n = R * C
		while miin <= maax:
			mid = (miin + maax) // 2
			ans = 0
			for i in range(R):
				(l, r) = (0, C - 1)
				while l <= r:
					m = (l + r) // 2
					if matrix[i][m] <= mid:
						l = m + 1
					else:
						r = m - 1
				ans += l
			if ans <= n // 2:
				miin = mid + 1
			else:
				maax = mid - 1
		return miin


class Solution:

	def median(self, matrix, R, C):

		def numLessEqualMatrix(num):
			total = 0
			for i in range(R):
				start = 0
				end = C - 1
				ans = -1
				while start <= end:
					mid = (start + end) // 2
					if matrix[i][mid] <= num:
						ans = mid
						start = mid + 1
					else:
						end = mid - 1
				total += ans + 1
			return total
		start = 0
		end = 10 ** 9
		while start < end:
			mid = (start + end) // 2
			if numLessEqualMatrix(mid) < R * C / 2:
				start = mid + 1
			else:
				end = mid
		return start


class Solution:

	def median(self, matrix, R, C):
		l = 1
		h = 2000

		def helper(i, elem):
			lo = 0
			hi = C - 1
			while lo <= hi:
				mid = (lo + hi) // 2
				if matrix[i][mid] <= elem:
					lo = mid + 1
				else:
					hi = mid - 1
			return lo
		while l <= h:
			mid = (l + h) // 2
			count = 0
			for i in range(R):
				count += helper(i, mid)
			if count <= R * C // 2:
				l = mid + 1
			else:
				h = mid - 1
		return l


class Solution:

	def median(self, matrix, R, C):
		final = []
		for i in range(0, R):
			for j in range(0, C):
				final.append(matrix[i][j])
		final = sorted(final)
		mid = R * C // 2
		return final[mid]


class Solution:

	def median(self, matrix, R, C):
		a = []
		for i in range(len(matrix)):
			a.extend(matrix[i])
		a.sort()
		l = len(a) // 2
		if len(a) % 2 == 0:
			return a[l + (l - 1)]
		else:
			return a[l]


class Solution:
	import numpy as np

	def median(self, matrix, R, C):
		arr = []
		i = 0
		while i < R:
			j = 0
			while j < C:
				arr.append(matrix[i][j])
				j = j + 1
			i = i + 1
		arr.sort()
		p = len(arr)
		q = int(p / 2)
		return arr[q]


class Solution:

	def median(self, matrix, R, C):

		def countNums(row, target):
			(l, r) = (0, C - 1)
			while l <= r:
				mid = (l + r) // 2
				if matrix[row][mid] <= target:
					l = mid + 1
				else:
					r = mid - 1
			return l
		(low, high) = (1, 2000)
		total = R * C // 2
		while low <= high:
			numsberLessThanTarget = 0
			mid = (low + high) // 2
			for row in range(0, R):
				numsberLessThanTarget += countNums(row, mid)
			if numsberLessThanTarget > total:
				high = mid - 1
			else:
				low = mid + 1
		return low


import statistics

class Solution:

	def median(self, matrix, R, C):
		l = []
		for i in range(R):
			l += matrix[i]
		l.sort()
		return statistics.median(l)


class Solution:

	def median(self, matrix, R, C):

		def NumOfLess(arr, k):
			l = 0
			r = len(arr)
			count = 0
			while l < r:
				mid = (l + r) // 2
				if arr[mid] <= k:
					count = mid + 1
					l = mid + 1
				else:
					r = mid
			return count
		l = 1
		r = 1000000000.0
		median = 0
		total = R * C
		while l <= r:
			lessEqual = 0
			mid = (l + r) // 2
			for i in range(R):
				ub = NumOfLess(matrix[i], mid)
				lessEqual += ub
			if lessEqual > total // 2:
				median = mid
				r = mid - 1
			else:
				l = mid + 1
		return int(median)


class Solution:

	def median(self, matrix, R, C):

		def binarySearch(arr, low, high, value):
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] > value:
					high = mid - 1
				else:
					low = mid + 1
			return low
		low = 1
		high = 2000
		while low <= high:
			count = 0
			mid = (low + high) // 2
			for i in range(R):
				count = count + binarySearch(matrix[i], 0, C - 1, mid)
			if count <= R * C // 2:
				low = mid + 1
			else:
				high = mid - 1
		return low


class Solution:

	def median(self, matrix, R, C):
		temp = []
		for i in range(R):
			for j in range(C):
				temp.append(matrix[i][j])
		temp.sort()
		s = len(temp)
		m = s // 2
		return temp[m]


import bisect as bs

class Solution:

	def median(self, matrix, R, C):
		(l, h) = (matrix[0][0], matrix[-1][-1])
		for r in range(R):
			l = min(matrix[r][0], l)
			h = max(matrix[r][-1], h)
		while l < h:
			mid_val = (l + h) // 2
			left_count = 0
			for r in range(R):
				left_count += bs.bisect(matrix[r], mid_val)
			if left_count > R * C // 2:
				h = mid_val
			else:
				l = mid_val + 1
		return l


class Solution:

	def median(self, matrix, R, C):
		L = []
		for i in matrix:
			L += i
		mid = R * C // 2
		return sorted(L)[mid]


class Solution:

	def median(self, matrix, R, C):
		list_1 = []
		for sublist in matrix:
			for val in sublist:
				list_1.append(val)
		list_1.sort()
		return list_1[int(R * C / 2)]


class Solution:

	def median(self, matrix, R, C):
		ans = []
		for row in matrix:
			for i in row:
				ans.append(i)
		ans.sort()
		N = len(ans)
		median = ans[N // 2]
		k = 0
		for i in range(R):
			for j in range(C):
				matrix[i][j] = ans[k]
				k += 1
		return median