Technical Mickey
Menu
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0s.
Constraints:
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1The problem requires a modification of the input matrix based on the presence of zero elements. The intuitive approach is to:
Identify rows and columns containing zeros.
Modify these rows and columns in place, ensuring efficient space usage.
While using additional memory (like auxiliary arrays) to track zero positions is simple, the challenge lies in achieving this with constant space, apart from the matrix itself.
Flagging Rows and Columns:
Use the first row and the first column of the matrix as markers. If matrix[i][j] is zero, mark the corresponding matrix[i][0] and matrix[0][j] as zero.
A separate variable, col0, tracks whether the first column needs to be zeroed out.
Matrix Update:
Iterate through the matrix (excluding the first row and column), and update elements to zero if their row or column marker is zero.
Handle First Row and Column:
After processing the rest of the matrix, update the first row and first column based on their respective markers.
This approach ensures constant space usage (O(1)), apart from the input matrix.
matrix = [
[1, 2, 3],
[4, 0, 6],
[7, 8, 9]
]Mark Zeroes:
Identify zeros and mark corresponding row and column in the first row/column.
Updated matrix:
[1, 0, 3]
[0, 0, 6]
[7, 8, 9]col0 = 1 (first column is unaffected so far).
Propagate Zeroes:
Traverse from the second row and column, setting elements to zero based on markers.
Updated matrix:
[1, 0, 3]
[0, 0, 0]
[7, 0, 9]Update First Row and Column:
If matrix[0][0] == 0, update the first row.
If col0 == 0, update the first column.
Final matrix:
[1, 0, 3]
[0, 0, 0]
[0, 0, 0]matrix = [[1, 0, 3],
[0, 0, 0],
[0, 0, 0]]
public class Solution {
// Helper function to count elements <= value in a sorted array
public static int countSmall(int[] row, int value) {
int low = 0, high = row.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] <= value) {
low = mid + 1; // Move to the right half
} else {
high = mid - 1; // Move to the left half
}
}
return low; // Position of the first element greater than 'value'
}
public int findMedian(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
// Step 1: Find the range of values
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < rows; i++) {
min = Math.min(min, matrix[i][0]); // First element of each row
max = Math.max(max, matrix[i][cols - 1]); // Last element of each row
}
// Step 2: Binary search for the median
while (min < max) {
int mid = (min + max) / 2;
int count = 0;
// Count elements <= mid in each row
for (int i = 0; i < rows; i++) {
count += countSmall(matrix[i], mid);
}
// Adjust search range based on count
if (count < (rows * cols + 1) / 2) {
min = mid + 1; // Median is in the higher range
} else {
max = mid; // Median is in the lower range
}
}
return min; // The median value
}
}
countSmallThis function performs a binary search on a sorted row to count how many elements are smaller than or equal to a given value.
Input: A sorted array and the target value.
Output: Number of elements <= target value.
Time Complexity: O(rows * log(cols)).
findMedianInitialization: Find the smallest and largest values in the matrix to define the search range.
Binary Search:
For each mid-point in the range, count the number of elements less than or equal to it.
Adjust the search range based on the count.
Return: The median value after the binary search.
Time Complexity:
Counting elements for a single mid-point takes .
Binary search on the value range takes .
Total: .
Space Complexity: as no extra memory is used.
int[][] matrix = {
{1, 3, 5},
{2, 6, 9},
{3, 6, 9}
};Sorted matrix: [1, 2, 3, 3, 5, 6, 6, 9, 9]
Median position: (9 + 1) / 2 = 5
Median value: 5
5Efficient Counting: Leveraging binary search on rows ensures efficient computation of counts.
Scalable Solution: Works for large matrices within the given constraints.
Direct Binary Search: Avoids extra memory usage by working directly on the value range.
This approach provides an optimal solution to find the median in a row-wise sorted matrix while adhering to the constraints.
Our Program make you Job Ready for your Dream Company 🚀