Design an algorithm that efficiently identifies all elements that appear in every row of a given m x n matrix. The algorithm must have a time complexity of O(mn) and should only require a single pass through the matrix.

Hint

Create two arrays, output for storing the final results, and cache for temporarily storing intermediate calculations. For each row in the matrix, examine each element in the current row. Determine which values can be stored in the cache based on the current values in the output array. After processing the entire row, copy the contents of the cache array into the output array. For the very first row of the matrix, directly place all its elements into the cache array.

# Python implementation

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)

// Javascript implementation

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]);

Find common elements in all rows in one iteration

Hint