199. Print Unique Rows in a Boolean Matrix

Given a matrix of 0s and 1s, print only its distinct rows, in their original relative order (the first occurrence of each distinct row pattern is kept; later duplicates are dropped). Print each kept row on its own line, space-separated.

Input: The first line contains two integers - the number of rows and columns. Each of the following rows lines contains cols space-separated 0/1 values. Output: Print each distinct row, in its first-occurrence order, space-separated, one per line.

1 <= rows, cols <= 1000

A binary row is really just a 'word' over a 2-character alphabet instead of 26 - recognizing that a trie's usefulness isn't limited to actual English letters is the key generalization this problem is testing.

Given a grid of 0s and 1s, keep only the FIRST occurrence of each distinct row pattern, dropping any row that's an exact repeat of an earlier one. Brute force: Compare each row against every PREVIOUSLY kept row directly (element by element) to check for an exact match - this costs O(rows² * cols) in the worst case, which is slow for a large matrix. Optimised: Inserting each row into a trie (treating each row as a sequence of 0/1 characters) lets you detect a full duplicate in time proportional only to the row's own length, since the trie insertion process itself naturally reveals whether the entire path already existed - no need to compare the new row against every previously-seen row individually.

Build a binary trie where each row's sequence of 0/1 values defines a root-to-leaf path of length cols. Insert rows into the trie one at a time in original order: while inserting a row, if the traversal has to create at least one brand-new trie node along the way, that row is the first occurrence of its pattern and gets printed immediately; if the entire path already existed, the row is an exact duplicate of an earlier one and is skipped. This processes each row through direct pointer traversal of the trie rather than hashing or comparing whole rows against each other, naturally detecting first-occurrence status as a side effect of insertion. Time: O(rows * cols) Space: O(rows * cols) worst case (trie nodes)

Convert each row into a single hashable key, such as a string formed by concatenating its 0/1 values (or an equivalent tuple), and maintain a hash set of keys seen so far. Process rows in order: for each row, compute its key and check the set - if the key is new, print the row and add the key to the set; if it's already present, skip the row as a duplicate. This replaces the pairwise comparisons of the brute approach with a single hash lookup per row. Time: O(rows * cols) average Space: O(rows * cols)

Process rows in order, and for each new row compare it element-by-element against every row already kept as unique so far; only if it doesn't exactly match any previously kept row is it printed and added to the kept collection. Because every new row may need to be compared against all previously kept rows, and each comparison itself takes time proportional to the number of columns, this becomes expensive as the number of rows grows. Time: O(rows^2 * cols) Space: O(rows * cols)

1. Treat each row of 0s and 1s as if it were a 'word' made of two possible characters instead of 26 letters. 2. Insert each row into a trie, one value at a time, exactly like inserting a word into a trie of letters. 3. If a row's entire path (all its values in sequence) already existed in the trie BEFORE this insertion, it's a duplicate of something seen earlier - skip printing it. 4. If any part of the path is new (meaning this exact row pattern hasn't been seen before), it's unique - print it and mark it as seen.

Time: Proportional to the total number of cells across the whole matrix (rows times columns) - a single pass, regardless of how many rows have already been processed. Space: Proportional to the total number of DISTINCT cells' worth of trie nodes created - bounded by the matrix size, and often much smaller if many rows share common prefixes.

Test a matrix where every row is identical (only the first is kept), a matrix where every row is distinct (all kept), a single-row or single-column matrix, and rows/cols up to 1000 for performance.

This problem shows tries aren't just for actual TEXT words - any sequence of a small, fixed alphabet (here, just 0 and 1) can be treated the same way, a useful generalization to recognize.