Common elements in all rows of a matrix

Medium

Problem

Return the distinct values that appear in every row of the matrix. The rows are not sorted.

Example 1

Input:  [[1,2,1,4,8], [3,7,8,5,1], [8,7,7,3,1], [8,1,2,7,9]]
Output: [1, 8]

Also asked as: Common elements in all rows of a given matrix

Test cases

Case 1

Input:    [[1,2,1,4,8],[3,7,8,5,1],[8,7,7,3,1],[8,1,2,7,9]]
Expected (any order): [1,8]

Case 2

Input:    [[2,2],[2,3]]
Expected (any order): [2]

Case 3

Input:    [[1,2,3]]
Expected (any order): [1,2,3]

Case 4

Input:    [[1,2],[3,4]]
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Frequency map seeded by the first row

Time O(R·C)Space O(C)

Put row 0 in a map (value → 1). For each later row, bump a value only if its stored count equals the current row index. At the end, values with count === R are common to all.

function commonInAllRows(m) {
const R = m.length;
const cnt = new Map();
for (const v of m[0]) cnt.set(v, 1);
for (let r = 1; r < R; r++)
for (const v of m[r])
if (cnt.get(v) === r) cnt.set(v, r + 1);
return [...cnt].filter(([, c]) => c === R).map(([v]) => v);
}