MatrixProblem 10 of 10
Common elements in all rows of a given matrix
Problem Statement
Given an m x n matrix where each row is sorted, find all elements that are common to all rows.
Example:
- Input:
matrix = [[1, 2, 3, 4, 5], [2, 4, 5, 8, 10], [3, 5, 7, 9, 11], [1, 3, 5, 7, 9]] - Output:
[5] - Explanation: 5 is the only element present in all rows.
Approach 1: Brute Force (Check Each Element)
Intuition
For each element in the first row, check if it exists in all other rows using binary search (since rows are sorted).
Algorithm
- For each element in the first row
- Binary search for it in every other row
- If found in all rows, add to result
java
import java.util.*;
public class Solution {
private boolean binarySearch(int[] row, int target) {
int left = 0, right = row.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (row[mid] == target) return true;
else if (row[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public List<Integer> commonElementsBrute(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
// Check each element in first row
for (int j = 0; j < n; j++) {
int elem = matrix[0][j];
boolean foundInAll = true;
// Search in all other rows
for (int i = 1; i < m && foundInAll; i++) {
if (!binarySearch(matrix[i], elem)) {
foundInAll = false;
}
}
if (foundInAll) {
result.add(elem);
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n * m * log n) - For each of n elements, binary search in m-1 rows
- Space Complexity: O(1) - Excluding output array
Approach 2: HashMap Counting (Works for Unsorted)
Intuition
Count occurrences of each element across rows. An element common to all rows will have count equal to number of rows.
Algorithm
- Use a hashmap to count how many rows contain each element
- For each row, add unique elements to the count
- Elements with count == m are common to all rows
java
import java.util.*;
public class Solution {
public List<Integer> commonElementsHashMap(int[][] matrix) {
Map<Integer, Integer> count = new HashMap<>();
int m = matrix.length;
for (int i = 0; i < m; i++) {
// Use set to handle duplicates within a row
Set<Integer> seen = new HashSet<>();
for (int val : matrix[i]) {
if (!seen.contains(val)) {
count.put(val, count.getOrDefault(val, 0) + 1);
seen.add(val);
}
}
}
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
if (entry.getValue() == m) {
result.add(entry.getKey());
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(m * n) - Single pass through matrix
- Space Complexity: O(n) - HashMap and set storage
Approach 3: Using Sorted Property (Optimal)
Intuition
Since rows are sorted, we can use a technique similar to merging k sorted arrays. Start with the last element of the first row and search backwards.
Track the last seen position in each row. An element is common if it can be found at or before these positions in all rows.
Algorithm
- Initialize pointers at the last column of each row
- Find the maximum of all current elements
- Move pointers backward until all point to the same value or a pointer exhausts
- Collect common elements
java
import java.util.*;
public class Solution {
public List<Integer> commonElements(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
List<Integer> result = new ArrayList<>();
// Pointers for each row, starting from the end
int[] ptr = new int[m];
Arrays.fill(ptr, n - 1);
while (true) {
// Check if any pointer is exhausted
boolean valid = true;
for (int i = 0; i < m; i++) {
if (ptr[i] < 0) {
valid = false;
break;
}
}
if (!valid) break;
// Find maximum element among current positions
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
maxVal = Math.max(maxVal, matrix[i][ptr[i]]);
}
// Check if all current elements equal maxVal
boolean allEqual = true;
for (int i = 0; i < m; i++) {
// Move pointer backward while element > maxVal
while (ptr[i] >= 0 && matrix[i][ptr[i]] > maxVal) {
ptr[i]--;
}
if (ptr[i] < 0 || matrix[i][ptr[i]] != maxVal) {
allEqual = false;
}
}
if (allEqual) {
result.add(maxVal);
// Move all pointers back to find next common element
for (int i = 0; i < m; i++) {
ptr[i]--;
}
}
}
// Reverse to get ascending order
Collections.reverse(result);
return result;
}
}Complexity Analysis
- Time Complexity: O(m * n) - Each pointer moves at most n positions
- Space Complexity: O(m) - For pointer array
Approach 4: Intersection Using Sets
Complexity: O(m * n * log n) time, O(n) space
Comparison of Approaches
| Approach | Time | Space | Works for Unsorted? | |----------|------|-------|---------------------| | Binary Search | O(mn log n) | O(1) | No | | HashMap | O(mn) | O(n) | Yes | | Sorted Pointers | O(mn) | O(m) | No | | Set Intersection | O(mn log n) | O(n) | Yes |
Key Takeaways
- HashMap counting is the most versatile approach (works for unsorted)
- The sorted property enables more efficient pointer-based solutions
- Handle duplicates within a row carefully when counting
- Set intersection is clean but has higher time complexity
- Binary search approach is straightforward but not optimal
- The problem reduces to finding intersection of m sorted arrays