Print unique rows in a given boolean matrix

The problem, simply

You get a grid with R rows and C columns. Every cell is 0 or 1. Some rows are exact copies of earlier rows.

Print every row, but skip any row that is a copy of a row already printed. Keep the order in which rows first show up.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a list of rows already printed. For each new row, compare it with every row in the list.

1. For each row of the grid, check it against every saved row, cell by cell.
2. If no saved row is equal, print it and save it.

import java.util.*;

class Solution {
    public static List<int[]> uniqueRows(int[][] grid) {
        List<int[]> seen = new ArrayList<>();
        for (int[] row : grid) {
            boolean copy = false;
            for (int[] old : seen) {
                if (Arrays.equals(row, old)) { copy = true; break; }   // cell by cell
            }
            if (!copy) seen.add(row);
        }
        return seen;
    }
}

How long it takes: each of the R rows may be compared with up to R saved rows, each compare reading C cells, O(R^2 * C). Extra room: the list of saved rows, which only holds references, O(R).

Way 2: the clever way

Treat each row as a word over the letters 0 and 1, and put it in a trie whose nodes have only two children. All rows have the same length, so a row is new exactly when its path is not already finished with a word end mark.

1. For each row, walk from the root, one cell at a time, going down the 0 or 1 child.
2. If a child is missing, create it.
3. At the end of the row, look at the word end mark. If it is already set, the row is a copy. If not, set it and print the row.

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[2];   // a 0 branch and a 1 branch
        boolean end;                 // a full row ends here
    }

    public static List<int[]> uniqueRows(int[][] grid) {
        Node root = new Node();
        List<int[]> out = new ArrayList<>();
        for (int[] row : grid) {
            Node cur = root;
            for (int cell : row) {
                if (cur.next[cell] == null) cur.next[cell] = new Node();
                cur = cur.next[cell];
            }
            if (!cur.end) {          // first time a row reaches this spot
                cur.end = true;
                out.add(row);
            }
        }
        return out;
    }
}

How long it takes: every cell is visited once, O(R * C), which is the time to read the grid anyway. Extra room: at most one node per cell, O(R * C), and much less when rows share starts.

Watch out for

• Printing the row when you first create a node, in the middle of the walk. Finish the row first, then decide.
• Cells that are not 0 or 1. next[cell] would go out of bounds. Check the input if it is not promised.
• Changing the order. A HashSet of rows loses the first appearance order unless you print while scanning, as the trie code does.

What interviewers ask next

• Can a hash set do this? Yes. Turn each row into a string, or into a long when C is at most 63, and add it to a HashSet. Print the row when add returns true. Also O(R * C).
• How many unique rows are there? Count how many times the word end mark was set for the first time.
• Find the rows that appear the most? Store a counter at each end node instead of a mark.
• Same question for columns? Walk the grid column by column instead, or transpose it first.
• Maximum XOR of two rows read as numbers? A 0 and 1 trie again: for each number, walk the trie and prefer the opposite bit at each step.

Remember this

Grown-up words: the path of forks is a binary trie, the flag is the end of word mark, threading a row is inserting a key, and the punch card is a bit vector.