Design an algorithm that identifies all elements that appear in every row of a given m x n matrix. The implementation keeps candidate values from the first row and checks their membership in each later row. It may perform repeated membership checks rather than a strict O(mn) single pass.
Create two arrays, output for storing the current candidates, and cache for temporarily storing the next candidates. For the first row, copy its values into output. For each later row, keep an output value only when it also occurs in the current row. After processing the row, replace output with cache. Return the values left in output after all rows have been checked.
matrix = [
[5, 1, 3, 4, 1],
[6, 9, 6, 5, 1],
[5, 3, 3, 7, 1],
[1, 9, 6, 5, 3]
]
output = []
cache = []
h = len(matrix)
w = len(matrix[0])
for i in range(h):
for j in range(w):
item = matrix[i][j]
if i == 0:
cache.append(item)
else:
if item in output:
cache.append(item)
output[:] = cache[:]
del cache[:]
print(output)
const matrix = [
[5, 1, 3, 4, 1],
[6, 9, 6, 5, 1],
[5, 3, 3, 7, 1],
[1, 9, 6, 5, 3]
];
let output = [];
let cache = [];
const h = matrix.length;
const w = matrix[0].length;
for (let i = 0; i < h; i++) {
for (let j = 0; j < w; j++) {
let item = matrix[i][j]
if (i == 0) {
cache.push(item);
} else {
if (output.includes(item)) {
cache.push(item);
}
}
}
output = [...cache];
cache = [];
}
console.log([...output]);