Count median in grid

Question

Given a 2D grid of integers, write a function to calculate the median value of all the elements in the grid. The function should take the grid as input and return the median as output, ensuring that the solution handles grids of varying sizes and values efficiently.

Codemia · Accepted Answer

To find the median of a 2D grid of integers, we need to first understand the definition of the median in a dataset: it's the middle value when the numbers are sorted. If the size of the dataset is odd, the median is the middle element; if even, it's the average of the two middle elements. Given that the grid can be of varying sizes and values, we need a strategy that efficiently sorts or retrieves the middle values without excessive space or time complexity. The most applicable pattern here is sorting, which is straightforward for calculating the median, but we can also use a binary search approach on the value range to optimize the search for the median directly.

1. **Flatten the Grid**: Convert the 2D grid into a 1D list of integers. For instance, given the grid:
   [[1, 5, 3], 
    [7, 8, 9], 
    [2, 4, 6]], 
   the flattened list would be [1, 5, 3, 7, 8, 9, 2, 4, 6].

2. **Sort the List**: Sort the flattened list. After sorting, our example list becomes [1, 2, 3, 4, 5, 6, 7, 8, 9].

3. **Find the Median**: Depending on whether the length of the list is odd or even, we select the median:
   - For odd length (9), the median is the 5th element (index 4): `5`.
   - For even length, we would take the average of the two middle values.

4. **Return the Median**: Finally, return the calculated median.

Here is the Python implementation of the above approach:

```python
def find_median(grid):
    # Flatten the grid into a 1D list
    flat_list = [num for row in grid for num in row]
    # Sort the list
    flat_list.sort()
    n = len(flat_list)
    # Calculate the median
    if n % 2 == 1:
        return flat_list[n // 2]  # Odd length
    else:
        mid1 = flat_list[n // 2 - 1]
        mid2 = flat_list[n // 2]
        return (mid1 + mid2) / 2  # Even length
```
This function first flattens the 2D grid, sorts the numbers, and then calculates the median based on the length of the sorted list.

The time complexity of this solution is O(N log N), where N is the total number of elements in the grid. This is primarily due to the sorting step. The space complexity is O(N) as we create a flattened list of all elements. Given the constraints of varying grid sizes, this approach is efficient for moderate-sized grids, but we could consider further optimization for very large grids, such as using a binary search approach directly on the range of values instead of sorting.

1. **Empty Grid**: If the grid is empty, we should handle this gracefully, perhaps by returning None or raising an exception. 
   ```python
   if not grid or not grid[0]:
       return None  # or raise ValueError('Grid is empty')
   ```
2. **Single Element Grid**: A grid with a single element should return that element as the median. 
3. **All Elements Same**: A grid where all elements are the same should correctly return that element as the median.
4. **Large Range of Values**: Ensure that the function can handle grids with very large or very small integers without overflow errors.

Count median in grid

Salesforce

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

Salesforce 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