Log inSign up
mediumGeeksforGeeksNot Started

Unique Rows in a Boolean Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a binary matrix M of size row x col, find all unique rows in the matrix and print them in order of their first appearance.

A row is considered unique if it has not appeared previously in the matrix.

Example 1 · Example 1: 3x4 Binary Matrix:

Input: row = 3, col = 4 M = [ [1, 1, 0, 1], [1, 0, 0, 1], [1, 1, 0, 1] ]
Output: [ [1, 1, 0, 1], [1, 0, 0, 1] ]
Explanation: Row 0: [1, 1, 0, 1] is unique (first appearance). Row 1: [1, 0, 0, 1] is unique (first appearance). Row 2: [1, 1, 0, 1] is a duplicate of Row 0 -> skipped. Binary Trie Structure: (root) | 1 / \ 0 1 | | 0 0 | | 1* 1* (row 0 & 1 stored)

Constraints:

  • 1 <= row, col <= 1000
  • 0 <= M[i][j] <= 1
  • row * col <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model binary matrix rows as strings in a 0/1 Binary Trie.
  • Detect duplicate sequences in streaming linear time O(col).
  • Preserve order of first appearance during in-place deduplication.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Deduplicating rows of a binary matrix.
  • Preserving order of first appearance.
  • Large matrix where string conversion or hash set overhead is undesirable.

Algorithmic Decision Tree:

  • Use a Binary Trie with children[2] (bit 0 and bit 1) and boolean isEnd.
  • Traverse each row from 0 to row - 1.
  • If insert(row) discovers a new path, keep the row in results.

Connected Patterns:

Maximum XOR of Two Numbers in an ArrayImplement TrieShortest Unique Prefix

1. Pairwise Row Equality Comparison

Intuition

Loop through each row i. Compare against all previous rows j < i. If M[i] == M[j] for all columns, row is duplicate. Otherwise add to output.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Initialize result = [].
  2. Step 2: Loop i from 0 to row - 1.
  3. Step 3: Check if row i equals any row j < i.
  4. Step 4: If not seen, append row i to result.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 vector<vector<int>> uniqueRow(int M[1000][1000], int row, int col) {
8 vector<vector<int>> result;
9 for (int i = 0; i < row; i++) {
10 bool isDuplicate = false;
11 for (int j = 0; j < i; j++) {
12 bool match = true;
13 for (int k = 0; k < col; k++) {
14 if (M[i][k] != M[j][k]) {
15 match = false;
16 break;
17 }
18 }
19 if (match) {
20 isDuplicate = true;
21 break;
22 }
23 }
24 if (!isDuplicate) {
25 vector<int> r(col);
26 for (int k = 0; k < col; k++) r[k] = M[i][k];
27 result.push_back(r);
28 }
29 }
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 int M[1000][1000] = {{1, 1, 0, 1}, {1, 0, 0, 1}, {1, 1, 0, 1}};
37 auto res = sol.uniqueRow(M, 3, 4);
38 for (const auto& r : res) {
39 for (int v : r) cout << v << " ";
40 cout << endl;
41 }
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(row^2 * col) — Checks all O(row2) pairs of rows with O(col) element comparisons each.
  • Space complexity: O(1) — No extra data structures allocated.

Why Brute Force Doesn't Scale:

Pairwise row checks fail on large matrices due to quadratic row scaling.

Binary Trie runs in 1,000,000 pointer transitions, executing in less than 15ms.

2. Hash Set of Serialized Binary Strings

Intuition

Maintain unordered_set<string> seen. For each row, concatenate its elements into a string like "1101". If seen.insert(rowStr) succeeds, add row to output.

When to apply: Quick prototype when memory allows string serialization.

Algorithm

  1. Step 1: Set seen stores serialized binary strings.
  2. Step 2: For each row: build string str.
  3. Step 3: If str not in seen, insert into seen and add row to result.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> uniqueRow(int M[1000][1000], int row, int col) {
10 unordered_set<string> seen;
11 vector<vector<int>> result;
12
13 for (int i = 0; i < row; i++) {
14 string s = "";
15 for (int j = 0; j < col; j++) {
16 s += (M[i][j] + '0');
17 }
18 if (seen.insert(s).second) {
19 vector<int> r(col);
20 for (int j = 0; j < col; j++) r[j] = M[i][j];
21 result.push_back(r);
22 }
23 }
24 return result;
25 }
26};
27
28int main() {
29 Solution sol;
30 int M[1000][1000] = {{1, 1, 0, 1}, {1, 0, 0, 1}, {1, 1, 0, 1}};
31 auto res = sol.uniqueRow(M, 3, 4);
32 for (const auto& r : res) {
33 for (int v : r) cout << v << " ";
34 cout << endl;
35 }
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(row * col) — String serialization takes O(col) per row. Set insert is O(col) on average.
  • Space complexity: O(row * col) — Stores serialized strings in the hash set.

3. Binary Trie (0/1 Prefix Tree) In-Place Insertion

Intuition

Define TrieNode with children[2] and boolean isEnd. For each row, walk down the Trie bit by bit. Track whether any new node was allocated or if the terminal node had isEnd == false. If so, set isEnd = true and keep the row. If isEnd == true already, the row is a duplicate.

When to apply: Standard optimal solution with zero string allocation and deterministic O(row * col) runtime.

Algorithm

  1. Step 1: Define TrieNode with array children[2] (initialized to null) and boolean isEnd = false.
  2. Step 2: Helper insertRow(M, rowIdx, col): walk bits. If child missing, allocate new node. Return true if !curr.isEnd.
  3. Step 3: Loop i from 0 to row - 1: if insertRow(M, i, col) is true, append row i to result.
  4. Step 4: Return result.

Interactive Trace for Binary Trie Row Insertion

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process Row 0: [1, 0]
Visual state
Values and pointers at this exact step
tree
Root
(root)
bit 1
1 (new)
bit 0*
0* (new, isEnd)

Node order shown; add connections to display explicit tree edges.

row 0: 10
Check / comparison
New nodes created -> isEnd marked true
Decision / next transition
Keep Row 0 in output.
Why this step matters

Step 1: Process Row 0: [1, 0]. Root creates child 1, then child 1 creates child 0. Mark isEnd = true. Row 0 is UNIQUE.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TrieNode {
6 TrieNode* children[2];
7 bool isEnd;
8 TrieNode() : isEnd(false) {
9 children[0] = nullptr;
10 children[1] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16
17 bool insertRow(int M[1000][1000], int r, int col) {
18 TrieNode* curr = root;
19 bool isNew = false;
20 for (int j = 0; j < col; j++) {
21 int bit = M[r][j];
22 if (!curr->children[bit]) {
23 curr->children[bit] = new TrieNode();
24 isNew = true;
25 }
26 curr = curr->children[bit];
27 }
28 if (!curr->isEnd) {
29 curr->isEnd = true;
30 return true;
31 }
32 return false;
33 }
34
35public:
36 vector<vector<int>> uniqueRow(int M[1000][1000], int row, int col) {
37 root = new TrieNode();
38 vector<vector<int>> result;
39
40 for (int i = 0; i < row; i++) {
41 if (insertRow(M, i, col)) {
42 vector<int> r(col);
43 for (int j = 0; j < col; j++) r[j] = M[i][j];
44 result.push_back(r);
45 }
46 }
47 return result;
48 }
49};
50
51int main() {
52 Solution sol;
53 int M[1000][1000] = {{1, 1, 0, 1}, {1, 0, 0, 1}, {1, 1, 0, 1}};
54 auto res = sol.uniqueRow(M, 3, 4);
55 for (const auto& r : res) {
56 for (int v : r) cout << v << " ";
57 cout << endl;
58 }
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(row * col) — Processes exactly row * col bits with O(1) pointer operations each.
  • Space complexity: O(row * col) — Allocates at most row * col Binary Trie nodes.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Compare Every Row with Previous RowsO(row^2 * col)O(1)For each row i, check if it equals any previously seen row j < i.Pairwise row comparisons.
2.Better — Hash Set of Serialized Row StringsO(row * col)O(row * col)Convert each row into a string or 64-bit bitset and store in an unordered_set.String copying and hash table rehashing.
3.Optimal — Binary Trie In-Place TraversalOptimalO(row * col)O(row * col)Stream bits directly into a Binary Trie. Unique status detected in O(col) steps without string allocation.None. Classical textbook algorithm for binary row deduplication.

Common Pitfalls & Crucial Edge Cases

Re-sorting output

The problem strictly demands preserving original first appearance order.

Allocating strings for large col (col=1000)

String allocations in inner loops cause high memory churn and slow performance.

Forgetting to set `isEnd = true`

Failing to mark the terminal node causes duplicate rows to be accepted repeatedly.

Crucial Edge Cases to Validate:

  • Matrix has only 1 row — Trivially unique, returned immediately.
  • All rows identical — Exactly 1 row returned in output.
  • All rows distinct — All row rows returned in original top-to-bottom order.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight how Binary Trie replaces costly string serialization with O(1) bitwise branch traversal.
  2. Point out that the order of insertion naturally preserves the order of first appearance.
  3. Mention that the maximum number of Trie nodes is bounded by min(row * col, 2^(col + 1)).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the Binary Trie determine whether a matrix row is unique?

2.What is the time complexity to process a matrix of size row x col using the Binary Trie?

Back to DSA Sheet