Find median in matrix

Question

Given a matrix of integers, write a function to find the median value of the elements in the matrix. The matrix may have varying numbers of rows and columns, and you should return the median as a float. If the total number of elements is odd, return the middle element; if even, return the average of the two middle elements.

Codemia · Accepted Answer

To find the median in a matrix, we can leverage the properties of sorted data. The median is defined as the middle value in a sorted list of numbers. In this case, since the matrix can have varying dimensions, it’s essential to flatten all the elements into a single list for sorting. The specific pattern that applies here is sorting and searching, as we will need to sort the elements to determine the median accurately. We can also consider binary search if we were to find the median without fully sorting the data, which can be more efficient in terms of time complexity.

1. **Flatten the Matrix**: Extract all elements from the matrix into a single list. For example, given the matrix:[[1, 3, 5], [2, 4, 6]], the flattened list becomes [1, 3, 5, 2, 4, 6].
2. **Sort the List**: Sort the flattened list. After sorting, the list would be [1, 2, 3, 4, 5, 6].
3. **Find the Median**: 
   - If the total number of elements is odd, return the middle element. 
   - If even, calculate the average of the two middle elements. In our example, there are 6 elements (even), so the median will be (3 + 4) / 2 = 3.5.

Here is the Python solution for finding the median in a matrix:

```python
def find_median(matrix):
    # Flatten the matrix into a single list
    flat_list = [num for row in matrix for num in row]
    # Sort the flattened list
    flat_list.sort()
    n = len(flat_list)
    # Calculate the median
    if n % 2 == 1:
        return float(flat_list[n // 2])  # Odd case
    else:
        mid1 = flat_list[n // 2 - 1]
        mid2 = flat_list[n // 2]
        return (mid1 + mid2) / 2.0  # Even case
```
This code efficiently flattens, sorts, and calculates the median based on the number of elements.

The time complexity of this solution is O(n log n), where n is the total number of elements in the matrix, due to the sorting step. The space complexity is O(n) as we are storing all elements in a flattened list. This is optimal for this problem since we need to look at all elements at least once to find the median.

1. **Empty Matrix**: If the input matrix is empty, the function should handle it gracefully, possibly returning None or raising an error. 
2. **Single Element Matrix**: If the matrix has only one element (e.g., [[1]]), the median should return that element (1.0). 
3. **Matrix with Negative Numbers**: Ensure the function correctly calculates the median with negative values (e.g., [[-1, -2], [0, 2]]). The median should be 0. 
4. **Non-rectangular Matrix**: Matrices with varying row lengths (e.g., [[1, 2], [3], [4, 5, 6]]) should be correctly flattened and processed.

Find median in matrix

Twitter/X

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Twitter/X Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string