Understanding the Problem
We are given a matrix in which each row is sorted in increasing order, but the columns may not be sorted. Our task is to find the median of all elements in this matrix.
Unlike a fully sorted array, we cannot directly access the median without extra work. Flattening and sorting the entire matrix would take O(r × c × log(r × c)) time. However, we can do better by using binary search on the value range.
This is possible because although the matrix is not globally sorted, each row is individually sorted. This allows us to use binary search within each row to efficiently count how many elements are ≤ a given value.
Step-by-Step Solution with Example
Step 1: Understand the structure of the matrix
Let's take the following matrix as an example:
[
[1, 3, 5],
[2, 6, 9],
[3, 6, 9]
]
Each row is sorted, but columns are not necessarily sorted. That’s acceptable for our approach.
Step 2: Determine the search space
To apply binary search, we need a range of possible values. We choose:
- min: the smallest first element among all rows → 1
- max: the largest last element among all rows → 9
Step 3: Define what we are searching for
There are 9 elements in total. Since 9 is odd, we are looking for the 5th smallest element (median).
Step 4: Apply binary search on the value range
Perform binary search between min
and max
. For each middle value mid
, count how many numbers in the matrix are ≤ mid
. This is done by using binary search in each row (e.g., upper_bound
logic).
Step 5: Adjust the search space based on the count
- If the count of elements ≤ mid
is less than desired count (e.g., <= 4), move the search right (increase low
).
- Else, move the search left (decrease high
).
Step 6: Continue until the search converges
Eventually, when low > high
, the low
will point to the smallest value that satisfies the condition, and that will be our median.
Step 7: Apply the logic on the example
Initial range: low = 1, high = 9
mid = 5 → count = 5 → enough → go left → high = 4
mid = 2 → count = 2 → too few → go right → low = 3
mid = 3 → count = 4 → too few → go right → low = 4
mid = 4 → count = 4 → too few → go right → low = 5
Now low = 5, high = 4 → done.
Answer: Median = 5
Edge Cases
Case 1: Even number of elements
[[1, 3],
[2, 4]] → Median can be chosen as floor of middle two = 2
Case 2: All elements same
[[7, 7],
[7, 7]] → Median = 7
Case 3: One row
[[1, 2, 3, 4, 5]] → Median = 3
Case 4: One column
[[2], [4], [6]] → Median = 4
Case 5: Duplicates
[
[1, 2, 2],
[2, 2, 3],
[3, 3, 4]
] → Median = 2
Case 6: Large values
[[100000, 100001],
[100002, 100003]] → Median = 100001
Finally
This problem is an excellent example of using binary search on value range rather than indices. It's efficient and scalable, running in O(32 × r × log c) time due to the 32-bit integer search range and binary searches within each row.
Always check if the problem allows for binary search on values. Also, ensure the rows are sorted, as this is key to optimizing the count step efficiently.
Comments
Loading comments...