Median Of A Row Wise Sorted Matrix - Leetcode Solution

Problem Description:

Given a m x n matrix, find the median element of the matrix. The matrix is sorted row-wise.

Example 1:

Input: [[1,3,5], [2,6,9], [3,6,9]]

Output: 5 Example 2:

Input: [[1,2,3], [4,5,6]]

Output: 3.5

Solution:

To solve this problem we can use binary search. We first find the minimum and maximum elements in the matrix. Then we perform a binary search on this range of minimum to maximum elements, and find the mid. We then count the number of elements less than or equal to the mid, and compare it with the median.

If the count is less than or equal to the median, then we increase the mid value and repeat the process. If the count is greater than the median, then we decrease the mid value and repeat the process. We do this until we find the median.

Let's consider the following dry run of the algorithm on the given example:

[[1,3,5], [2,6,9], [3,6,9]]

Minimum element: 1 Maximum element: 9

Mid element: (1+9)/2 = 5

Count of elements less than or equal to 5: (1,3,5,2,6,3) = 6

The count is less than the median, hence we increase the mid.

New mid element: (5+9)/2 = 7

Count of elements less than or equal to 7: (1,3,5,2,6,3,6,9) = 8

The count is greater than the median, hence we decrease the mid.

New mid element: (5+7)/2 = 6

Count of elements less than or equal to 6: (1,3,5,2,6,3,6) = 7

The count is greater than the median, hence we decrease the mid.

New mid element: (5+6)/2 = 5

Count of elements less than or equal to 5: (1,3,5,2,3) = 5

The count is equal to the median, hence we have found the median which is 5.

Time Complexity:

The time complexity of this solution is O(mlogn), where m is the range of elements (maximum-minimum), and n is the number of columns in the matrix.

Space Complexity:

The space complexity of this solution is O(1), as we are not using any extra space to solve the problem.

1