Print unique rows in a given boolean matrix
Problem Statement
Given a binary matrix (containing only 0s and 1s), print all unique rows of the matrix. A row is considered duplicate if another row has the exact same sequence of 0s and 1s.
Example:
Input:
[[1, 1, 0, 1],
[1, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 0, 1],
[1, 0, 0, 1]]
Output:
[1, 1, 0, 1]
[1, 0, 0, 1]
[0, 0, 0, 1]
Explanation: Row 0 and Row 2 are identical, Row 1 and Row 4 are identical.
We print each unique row only once.
Noob-Friendly Explanation
Imagine you have a bunch of light switch panels, each with switches that are either ON (1) or OFF (0). Some panels have the exact same pattern of on/off switches. Your job is to find and display only the unique panels — no duplicates!
One clever approach: treat each row as a "word" made of 0s and 1s, and store them in a Trie (like a dictionary). When we try to add a row that already exists in the Trie, we skip it. This way, we naturally filter out duplicates.
Approach 1: Brute Force
Intuition
For each row, compare it with all previously seen rows. If it hasn't been seen before, add it to the result.
Algorithm
- Maintain a list of unique rows seen so far
- For each row in the matrix, compare it with all rows in the list
- If no match is found, add it to the list
- Print all rows in the list
import java.util.*;
class Solution {
private static boolean areEqual(int[] row1, int[] row2) {
if (row1.length != row2.length) return false;
for (int i = 0; i < row1.length; i++) {
if (row1[i] != row2[i]) return false;
}
return true;
}
public static List<int[]> uniqueRows(int[][] matrix) {
List<int[]> unique = new ArrayList<>();
for (int[] row : matrix) {
boolean isDuplicate = false;
for (int[] seen : unique) {
if (areEqual(row, seen)) {
isDuplicate = true;
break;
}
}
if (!isDuplicate) {
unique.add(row);
}
}
return unique;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 1, 0, 1},
{1, 0, 0, 1},
{1, 1, 0, 1},
{0, 0, 0, 1},
{1, 0, 0, 1}
};
List<int[]> result = uniqueRows(matrix);
for (int[] row : result) {
System.out.println(Arrays.toString(row));
}
// [1, 1, 0, 1]
// [1, 0, 0, 1]
// [0, 0, 0, 1]
}
}Complexity Analysis
- Time Complexity: O(R^2 * C) — For each of R rows, compare with up to R unique rows, each comparison takes O(C)
- Space Complexity: O(R * C) — Storing unique rows
Approach 2: Optimal (Trie-Based)
Intuition
Build a Trie where each path represents a row. Since each element is 0 or 1, each node only needs 2 children. If inserting a row creates a new path (reaches a node that didn't exist before or a new endpoint), it's unique. If the path already exists completely, it's a duplicate.
Algorithm
- Create a Trie with nodes having 2 children (for 0 and 1)
- For each row, try to insert it into the Trie
- During insertion, track if we created any new node or reached a new endpoint
- If the row is new (not fully present in Trie), add it to result
import java.util.*;
class Solution {
static class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[2]; // only 0 and 1
isEnd = false;
}
}
private static TrieNode root;
/**
* Insert a row into the Trie.
* Returns true if the row is newly inserted (unique).
* Returns false if the row already exists (duplicate).
*/
private static boolean insert(int[] row) {
TrieNode current = root;
boolean isNew = false;
for (int val : row) {
if (current.children[val] == null) {
current.children[val] = new TrieNode();
isNew = true;
}
current = current.children[val];
}
// Even if all nodes existed, check if this endpoint is new
if (!current.isEnd) {
current.isEnd = true;
isNew = true;
}
return isNew;
}
public static List<int[]> uniqueRows(int[][] matrix) {
root = new TrieNode();
List<int[]> result = new ArrayList<>();
for (int[] row : matrix) {
if (insert(row)) {
result.add(row);
}
}
return result;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 1, 0, 1},
{1, 0, 0, 1},
{1, 1, 0, 1},
{0, 0, 0, 1},
{1, 0, 0, 1}
};
List<int[]> result = uniqueRows(matrix);
for (int[] row : result) {
System.out.println(Arrays.toString(row));
}
// [1, 1, 0, 1]
// [1, 0, 0, 1]
// [0, 0, 0, 1]
}
}Complexity Analysis
- Time Complexity: O(R * C) — Each row insertion takes O(C), done for R rows
- Space Complexity: O(R * C) — Trie stores at most R * C nodes in the worst case
Key Takeaways
- Binary Trie: Since matrix has only 0s and 1s, each node needs only 2 children — very efficient
- Insert-and-Check: By returning whether insertion created new nodes, we identify unique rows in one pass
- Preserves Order: Unlike HashSet, Trie approach preserves the original order of first appearance
- Alternative: You could also convert each row to a string and use a HashSet, but Trie avoids string conversion overhead