Count Distinct Rows in a Binary Matrix

Given a binary matrix of size M x N containing only 0s and 1s, print all unique rows of the given matrix.

Examples

Example 1

• Input Matrix:

  [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 1, 1, 0, 0]
  ]
• Output:

  0 1 0 0 1
  1 0 1 1 0
  1 1 1 0 0
• Explanation: Row 1 and Row 3 are duplicates. We remove Row 3 and output only the distinct rows.

Trie Approach

A simple search method like a Binary Search Tree or Hashing requires converting rows to numbers or strings, which can cause overflow if the number of columns is very large.

Using a Trie Data Structure allows us to solve this problem efficiently in O(ROW x COL) time. Since the matrix is binary, each node in our Trie needs only two children: one for 0 and one for 1.

Algorithm

1. Create a Binary Trie where each node has a child pointer array of size 2 (for 0 and 1) and a boolean flag isEndOfRow.
2. For each row in the matrix:
   • Insert the row into the Trie.
   • During insertion, track if any new node was created.
   • If no new node was created and we reached the end of the row, then this row is a duplicate.
   • If at least one new node was created, the row is unique. Print it.

JavaScript Implementation

class TrieNode {
    constructor() {
        this.isEndOfRow = false;
        // Only 2 children: index 0 for '0' and index 1 for '1'
        this.children = new Array(2).fill(null);
    }
}
 
function insertRow(root, matrix, row, colCount) {
    let curr = root;
    let isNewRow = false;
 
    for (let i = 0; i < colCount; i++) {
        let val = matrix[row][i];
 
        if (curr.children[val] === null) {
            curr.children[val] = new TrieNode();
            isNewRow = true; // New node created, meaning row is unique
        }
        curr = curr.children[val];
    }
 
    curr.isEndOfRow = true;
    return isNewRow;
}
 
function printUniqueRows(matrix) {
    const rowCount = matrix.length;
    if (rowCount === 0) return;
    const colCount = matrix[0].length;
 
    const root = new TrieNode();
 
    for (let i = 0; i < rowCount; i++) {
        // If row is unique, print it
        if (insertRow(root, matrix, i, colCount)) {
            console.log(matrix[i].join(" "));
        }
    }
}
 
// Driver code
const matrix = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 1, 1, 0, 0]
];
 
console.log("Unique rows:");
printUniqueRows(matrix);
/*
Output:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0
*/

Complexity Analysis

• Time Complexity: O(ROW * COL)
  • We traverse each element of the matrix exactly once to insert it into the Trie.
• Space Complexity: O(ROW * COL)
  • In the worst case (where all rows are unique and have no common prefixes), we store a node for each cell in the matrix.