Prerequisites: Matrix, Binary Search.
Problem: Given a N x M row-wise sorted matrix, find the median of the matrix. (Note: N*M is always odd)
Solution Approach:
The naive solution is to store all elements of the matrix in an array, sort it and return the middle element. That will take O(NMlog(NM)) time and O(N*M) space. However since the matrix is row-wise sorted, we can use binary search to find the median value of the matrix.
We can perform binary search on the possible range of values that the median can take. We initialize a low value as the minimum possible value in the matrix and a high value as the maximum possible value. We then iterate through the search space, finding the middle value. For each middle value, we count the number of elements in the matrix that are smaller than or equal to the middle value using binary search in each row. If the count of such elements is less than or equal to half of the total number of elements in the matrix, we update the low value to move towards higher values. Otherwise, we update the high value to move towards lower values. We continue this process until we find the median value. This approach efficiently identifies the median value by narrowing down the search space using binary search.
Time Complexity: O(log(maxValue - minValue) * N * log(M)). The first log factor is due to BS on possible range of median, and in each iteration of while loop, we’re again iterating through each row taking log(M) time to count smaller elements.
Space Complexity: O(1) as no extra space required except few variables.