Find distinct elements common to all rows of a matrix

Problem

Given an n x n matrix, find all the distinct elements common to all rows of the matrix. The elements can be printed in any order.

Examples

Example 1

Input:
mat = [
  [2, 1, 4, 3],
  [1, 2, 3, 2],
  [3, 6, 2, 3],
  [5, 2, 5, 3]
]
Output: [2, 3]
Explanation: 2 and 3 are present in every row.

Example 2

Input:
mat = [
  [12, 1, 14, 3, 16],
  [14, 2, 1, 3, 35],
  [14, 1, 14, 3, 11],
  [14, 25, 3, 2, 1],
  [1, 18, 3, 21, 14]
]
Output: [1, 3, 14]
Explanation: 1, 3, and 14 are present in every row.

Constraints

• 1 <= n <= 1000
• Matrix elements are integers (may be negative or positive)

Solution

Method 1 – Brute Force

Intuition

Check every element in the first row and see if it appears in every other row. If so, and it hasn't already been added, include it in the answer.

Approach

1. For each element in the first row:
   • For each subsequent row, check if the element is present.
   • If it is present in all rows and not already in the answer, add it.
2. Return the answer list.

Code

C++

class Solution {
public:
  vector<int> commonElements(vector<vector<int>>& mat) {
    int n = mat.size();
    vector<int> ans;
    for (int x : mat[0]) {
      bool found = true;
      for (int i = 1; i < n; ++i) {
        if (find(mat[i].begin(), mat[i].end(), x) == mat[i].end()) {
          found = false;
          break;
        }
      }
      if (found && find(ans.begin(), ans.end(), x) == ans.end()) ans.push_back(x);
    }
    return ans;
  }
};

Go

func commonElements(mat [][]int) []int {
  n := len(mat)
  ans := []int{}
  for _, x := range mat[0] {
    found := true
    for i := 1; i < n; i++ {
      ok := false
      for _, y := range mat[i] {
        if y == x {
          ok = true
          break
        }
      }
      if !ok {
        found = false
        break
      }
    }
    already := false
    for _, v := range ans {
      if v == x {
        already = true
        break
      }
    }
    if found && !already {
      ans = append(ans, x)
    }
  }
  return ans
}

Java

class Solution {
  public List<Integer> commonElements(int[][] mat) {
    int n = mat.length;
    List<Integer> ans = new ArrayList<>();
    for (int x : mat[0]) {
      boolean found = true;
      for (int i = 1; i < n; ++i) {
        boolean ok = false;
        for (int y : mat[i]) if (y == x) { ok = true; break; }
        if (!ok) { found = false; break; }
      }
      if (found && !ans.contains(x)) ans.add(x);
    }
    return ans;
  }
}

Python

class Solution:
  def commonElements(self, mat: list[list[int]]) -> list[int]:
    n = len(mat)
    ans: list[int] = []
    for x in mat[0]:
      if all(x in row for row in mat[1:]) and x not in ans:
        ans.append(x)
    return ans

Complexity

• ⏰ Time complexity: O(n^3), since for each element in the first row, we may scan all rows and all columns.
• 🧺 Space complexity: O(n), for the answer list.

Method 2 – Hash Set Intersection

Intuition

Use a hash set to keep track of elements common to all rows. Intersect the set with each row to efficiently filter out non-common elements.

Approach

1. Initialize a set with all elements from the first row.
2. For each subsequent row, create a set of its elements and intersect it with the running set.
3. After all rows, the set contains the common elements.
4. Return the set as a list.

Code

C++

#include <unordered_set>
class Solution {
public:
  vector<int> commonElements(vector<vector<int>>& mat) {
    unordered_set<int> s(mat[0].begin(), mat[0].end());
    for (int i = 1; i < mat.size(); ++i) {
      unordered_set<int> row(mat[i].begin(), mat[i].end());
      for (auto it = s.begin(); it != s.end(); ) {
        if (!row.count(*it)) it = s.erase(it);
        else ++it;
      }
      if (s.empty()) break;
    }
    return vector<int>(s.begin(), s.end());
  }
};

Go

func commonElements(mat [][]int) []int {
  s := map[int]bool{}
  for _, x := range mat[0] {
    s[x] = true
  }
  for i := 1; i < len(mat); i++ {
    row := map[int]bool{}
    for _, x := range mat[i] {
      row[x] = true
    }
    for k := range s {
      if !row[k] {
        delete(s, k)
      }
    }
    if len(s) == 0 {
      break
    }
  }
  ans := []int{}
  for k := range s {
    ans = append(ans, k)
  }
  return ans
}

Java

import java.util.*;
class Solution {
  public List<Integer> commonElements(int[][] mat) {
    Set<Integer> s = new HashSet<>();
    for (int x : mat[0]) s.add(x);
    for (int i = 1; i < mat.length; ++i) {
      Set<Integer> row = new HashSet<>();
      for (int x : mat[i]) row.add(x);
      s.retainAll(row);
      if (s.isEmpty()) break;
    }
    return new ArrayList<>(s);
  }
}

Python

class Solution:
  def commonElements(self, mat: list[list[int]]) -> list[int]:
    s = set(mat[0])
    for row in mat[1:]:
      s &= set(row)
      if not s:
        break
    return list(s)

Complexity

• ⏰ Time complexity: O(n^2), since each row is scanned and set operations are O(1) per element.
• 🧺 Space complexity: O(n), for the sets.