Matrix Median Problem in Java
The Matrix Median Problem is a computational problem that requires to find the median value among elements in a two-dimensional matrix, which is usually represented as array of arrays in programming languages such as Java. In this problem, we are given a matrix of size m x n, where m denotes the number of rows and n is the number of columns. The matrix contains numerical values in each cell. unlike the one-dimensional array for which the midpoint can be obtained after sorting. The matrix median problem is a complex problem due to the two-dimensional nature of the data structure to form a matrix.
Example
Input
Output
Median is 5
Explanation
If we put all the values in a sorted array A[] = 2 3 3 1 5 6 6 6 7. So, the median is 5.
Approach 1: Brute Force
The brute force approach to solving the matrix median problem involves a straightforward but computationally intensive method of finding the median of a row-wise sorted matrix. In this method the concept is simple but may not be the most efficient for large matrices due to its time complexity, but it provides a clear starting point for understanding the problem and can serve as a baseline for comparison with more optimized algorithms.
Algorithm
Step 1: Take a two-dimensional matrix (matrix) as input and extract the number of rows (rows) and columns (cols) in the matrix.
Step 2: Calculate Total Elements: Calculate the total number of elements in the matrix by multiplying the number of rows by the number of columns.
Step 3: Flatten Matrix: Create a one-dimensional array (flattened) with a size equal to the total number of elements in the matrix.
Step 4: Initialize an index variable (index) to keep track of the current position in the flattened array.
Step 5: Iterate through each row and column of the matrix. For each element in the matrix, append it to the flattened array at the current index position. Increment the index variable.
Step 6: Sort Flattened Array: Sort the flattened array in ascending order. You can use any sorting algorithm, such as quicksort or mergesort, or built-in functions like Arrays.sort() in Java.
Step 7: Determine Median: If the total number of elements in the flattened array is even: Calculate the indices of the two middle elements: midIndex1 = totalElements / 2 - 1 and midIndex2 = totalElements / 2.
Step 8: Compute the median as the average of the two middle elements: median = (flattened[midIndex1] + flattened[midIndex2]) / 2.0.
Step 9: If the total number of elements in the flattened array is odd: Calculate the index of the middle element: midIndex = totalElements / 2.
Step 10: Assign the middle element directly as the median: median = flattened[midIndex] and return the computed median value.
Filename: MatrixMedianBruteForce.java
import java.util.Arrays;
public class MatrixMedianBruteForce {
// Function to find the median of a row-wise sorted matrix
public static int findMedian(int[][] matrix) {
// Extract the number of rows and columns in the matrix
int rows = matrix.length;
int cols = matrix[0].length;
// Calculate the total number of elements in the matrix
int totalElements = rows * cols;
// Create a one-dimensional array to store all matrix elements
int[] flattened = new int[totalElements];
int index = 0;
// Flatten the matrix into the one-dimensional array
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
flattened[index++] = matrix[i][j];
}
}
// Sort the flattened array in ascending order
Arrays.sort(flattened);
// Determine the median based on the total number of elements
int median;
if (totalElements % 2 == 0) {
// If the total number of elements is even, compute the average of the two middle elements
int midIndex1 = totalElements / 2 - 1;
int midIndex2 = totalElements / 2;
median = (flattened[midIndex1] + flattened[midIndex2]) / 2;
} else {
// If the total number of elements is odd, simply select the middle element as the median
int midIndex = totalElements / 2;
median = flattened[midIndex];
}
return median;
}
// Main method to test the brute force approach
public static void main(String[] args) {
// Example matrix
int[][] matrix = {
{2, 3, 3},
{1, 5, 6},
{6, 6, 7}
};
// Find the median of the matrix using the brute force approach
int median = findMedian(matrix);
// Display the median
System.out.println("Median of the matrix: " + median);
}
}
Output:
Median of the matrix: 5
Time Complexity
Sorting the flattened array using a sorting algorithm such as quicksort or mergesort typically has a time complexity of O(totalElements * log(totalElements)), where totalElements is the total number of elements in the array. Overall, the dominant factor in the time complexity is the sorting step, which contributes O(totalElements * log(totalElements)).
Space Complexity
Creating a one-dimensional array to store all elements of the matrix requires additional space proportional to the number of elements in the matrix, resulting in a space complexity of O(rows * cols). Other variables used, such as indices and the median variable, occupy constant space that is O(1). Therefore, the overall space complexity of the brute force approach is O(rows * cols).
Approach 2: Optimized Approach
The optimized approach for finding the median of a row-wise sorted matrix using binary search represents a refined strategy that leverages the inherent structure of the matrix to efficiently locate the median value. In this approach we address the limitations of the brute force method by exploiting the sorted nature of the matrix rows to achieve superior time complexity while maintaining minimal space requirements.
Algorithm
Step 1: Initialize the input matrix matrix with the given values and determine the number of rows (rows) and columns (cols) in the matrix.
Step 2: Find Minimum and Maximum Elements: Iterate through each row of the matrix to find the minimum and maximum elements. Initialize variables min and max to Integer.MAX_VALUE and Integer.MIN_VALUE respectively.
Step 3: For each row i: If the first element matrix[i][0] is less than min, update min. If the last element matrix[i][cols - 1] is greater than max, update max.
Step 4: Calculate Desired Position: Calculate the desired position (desired) of the median element using the formula: (rows * cols + 1) / 2. This gives the position of the median element when the matrix elements are sorted in ascending order.
Step 5: Binary Search for Median: Initialize variables min and max to the minimum and maximum values found in step 3. Perform binary search within the range [min, max] to find the median element.
Step 6: While min is less than max: Calculate the midpoint mid as min + (max - min) / 2. Count the number of elements less than or equal to mid in the matrix using the countElementsLessThanOrEqualTo method.
Step 7: If the count is less than the desired position, update min to mid + 1. Otherwise, update max to mid.
Step 8: After the binary search converges (min becomes equal to max), return min as the median element.
Filename: MatrixMedianBinarySearch.java
import java.util.Arrays;
public class MatrixMedianBinarySearch {
// Function to find the median using binary search
static int findMedian() {
int[][] matrix = {
{2, 3, 3},
{1, 5, 6},
{6, 6, 7}
};
int rows = matrix.length;
int cols = matrix[0].length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// Find the minimum and maximum elements in the matrix
for(int i = 0; i < rows; i++) {
if(matrix[i][0] < min)
min = matrix[i][0];
if(matrix[i][cols - 1] > max)
max = matrix[i][cols - 1];
}
int desired = (rows * cols + 1) / 2;
while(min < max) {
int mid = min + (max - min) / 2;
int count = countElementsLessThanOrEqualTo(matrix, mid);
if(count < desired)
min = mid + 1;
else
max = mid;
}
return min;
}
// Function to count the number of elements less than or equal to a given value
static int countElementsLessThanOrEqualTo(int[][] matrix, int value) {
int count = 0;
for(int[] row : matrix) {
int index = Arrays.binarySearch(row, value);
if(index >= 0)
count += index + 1;
else
count += Math.abs(index) - 1;
}
return count;
}
// Main method to test the binary search approach
public static void main(String[] args) {
System.out.println("Median is " + findMedian());
}
}
Output:
Median of the matrix: 5
Time Complexity
The main time complexity is attributed to the binary search algorithm. Since we perform binary search on each row of the matrix, and each binary search operation has a time complexity of O(log(cols)), the overall time complexity is O(rows×log(cols)).
Space Complexity
The space complexity of the algorithm is O(1) which is constant, irrespective of the input size. It does not depend on the size of the input matrix or any other input parameters. The algorithm utilizes a constant amount of extra space for storing variables such as min, max, mid, and count.