Common elements in all rows of a given matrix

The problem, simply

You get a grid with m rows and n columns. The rows are not sorted, and a number can appear more than once in the same row.

Give back every number that appears in all of the rows. Each such number should appear only once in the answer, in any order.

A story to remember it

Picture it

Examples

Way 1: the simple way

Take each different number from the first row and look for it in every other row.

1. Put the numbers of row 0 into a set, so repeats are checked once.
2. For each number in the set, scan rows 1 to m - 1. If some row does not have it, drop it.
3. The numbers that survive every row are the answer.

import java.util.*;

class Solution {
    public List<Integer> commonElements(int[][] mat) {
        List<Integer> result = new ArrayList<>();
        if (mat.length == 0) return result;
        Set<Integer> candidates = new LinkedHashSet<>();
        for (int v : mat[0]) candidates.add(v);      // each different number of row 0, once

        for (int v : candidates) {
            boolean everywhere = true;
            for (int i = 1; i < mat.length && everywhere; i++) {
                boolean found = false;
                for (int x : mat[i]) if (x == v) { found = true; break; }   // scan the whole row
                everywhere = found;
            }
            if (everywhere) result.add(v);
        }
        return result;
    }
}

How long it takes: up to n candidates, each scanned against m - 1 rows of n numbers, O(m*n^2). Extra room: the set of candidates, O(n).

Way 2: the clever way

Read the grid once, row by row, keeping a notebook (a hash map) from a number to how many rows, starting at row 0, it has been seen in without a gap.

1. For row 0, set count[v] = 1 for every number v.
2. For row i from 1 to m - 1, for every number v in the row:
   • If count[v] == i, the number was in all rows before this one. Set count[v] = i + 1.
   • If this is the last row, that bump means v is in every row. Add it to the answer.
   • Otherwise do nothing: the number is missing from some earlier row, is not in the notebook at all, or was already counted in this row.

The check count[v] == i does three jobs at once: it ignores strangers, it ignores numbers that fell behind, and it ignores a second copy in the same row.

import java.util.*;

class Solution {
    public List<Integer> commonElements(int[][] mat) {
        List<Integer> result = new ArrayList<>();
        int m = mat.length;
        if (m == 0) return result;

        Map<Integer, Integer> count = new HashMap<>();   // number -> rows survived so far
        for (int v : mat[0]) count.put(v, 1);
        if (m == 1) {                                     // one row: every different number counts
            result.addAll(count.keySet());
            return result;
        }

        for (int i = 1; i < m; i++) {
            for (int v : mat[i]) {
                Integer c = count.get(v);
                if (c != null && c == i) {                // in every row before this one, first time in this row
                    count.put(v, i + 1);
                    if (i == m - 1) result.add(v);        // survived the last row too
                }
            }
        }
        return result;
    }
}

How long it takes: every cell is read once with an O(1) map lookup, O(m*n). Extra room: the notebook only ever holds numbers from row 0, so O(n).

Watch out for

• Adding new numbers to the map after row 0. They can never be common, and they make the map grow to O(m*n).
• Forgetting the one row grid. The loop over rows 1 and up never runs, so handle m == 1 on its own.
• Returning a number twice. The count == i check makes each number join the answer once.
• Assuming the rows are sorted. The grid in this problem is not sorted. If it were, the pointer method below would also work.

What interviewers ask next

• What if every row is sorted? Keep one pointer per row, all starting at the right end. Find the smallest of the numbers under the pointers. Every row whose number is bigger than that smallest one moves its pointer left until its number is no longer bigger. If all pointers then show the same number, record it and move every pointer left past all copies of it. Stop when any pointer falls off. O(m*n) time and O(m) room, and no hash map.
• Can you do it without a hash map and unsorted rows? Sort each row first, O(m*n*log(n)), then use the pointer method.
• Common numbers of only two arrays? Put one in a set and scan the other. This problem is that idea repeated across many rows.
• Return how many rows each number appears in, not only the common ones. Then you do need a map from number to a set of rows, or count with a "last row seen" value per number.
• Huge grid that does not fit in memory? The method reads rows one at a time and keeps only row 0's numbers, so it works as a stream.

Remember this

Grown-up words: the teacher's notebook is a hash map, the tally that must match the row number is a "last seen row" check that removes duplicates, and the whole thing is the intersection of m sets done in one pass.