1947. Maximum Compatibility Score Sum LeetCode Solution

Last updated: February 25, 2025

In this guide, you will get 1947. Maximum Compatibility Score Sum LeetCode Solution with the best time and space complexity. The solution to Maximum Compatibility Score Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Compatibility Score Sum solution in C++
Maximum Compatibility Score Sum solution in Java
Maximum Compatibility Score Sum solution in Python
Additional Resources

1947. Maximum Compatibility Score Sum LeetCode Solution image

Problem Statement of Maximum Compatibility Score Sum

There is a survey that consists of n questions where each question’s answer is either 0 (no) or 1 (yes).
The survey was given to m students numbered from 0 to m – 1 and m mentors numbered from 0 to m – 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.

For example, if the student’s answers were [1, 0, 1] and the mentor’s answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.

You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
Given students and mentors, return the maximum compatibility score sum that can be achieved.

Example 1:

Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
Output: 8
Explanation: We assign students to mentors in the following way:
– student 0 to mentor 2 with a compatibility score of 3.
– student 1 to mentor 0 with a compatibility score of 2.
– student 2 to mentor 1 with a compatibility score of 3.
The compatibility score sum is 3 + 2 + 3 = 8.

Example 2:

Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
Output: 0
Explanation: The compatibility score of any student-mentor pair is 0.

Constraints:

m == students.length == mentors.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k] is either 0 or 1.
mentors[j][k] is either 0 or 1.

Complexity Analysis

Time Complexity: O(m! \cdot mn)
Space Complexity: O(n)

1947. Maximum Compatibility Score Sum LeetCode Solution in C++

class Solution {
 public:
  int maxCompatibilitySum(vector<vector<int>>& students,
                          vector<vector<int>>& mentors) {
    int ans = 0;
    dfs(students, mentors, 0, /*score=*/0, vector<bool>(students.size()), ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& students,
           const vector<vector<int>>& mentors, int i, int scoreSum,
           vector<bool>&& used, int& ans) {
    if (i == students.size()) {
      ans = max(ans, scoreSum);
      return;
    }
    for (int j = 0; j < students.size(); ++j) {
      if (used[j])
        continue;
      used[j] = true;  // The `mentors[j]` is used.
      dfs(students, mentors, i + 1,
          scoreSum + getScore(students[i], mentors[j]), std::move(used), ans);
      used[j] = false;
    }
  }

  int getScore(const vector<int>& student, const vector<int>& mentor) {
    int score = 0;
    for (int i = 0; i < student.size(); ++i)
      if (student[i] == mentor[i])
        ++score;
    return score;
  }
};
/* code provided by PROGIEZ */

1947. Maximum Compatibility Score Sum LeetCode Solution in Java

class Solution {
  public int maxCompatibilitySum(int[][] students, int[][] mentors) {
    dfs(students, mentors, 0, /*score=*/0, new boolean[students.length]);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] students, int[][] mentors, int i, int scoreSum, boolean[] used) {
    if (i == students.length) {
      ans = Math.max(ans, scoreSum);
      return;
    }
    for (int j = 0; j < students.length; ++j) {
      if (used[j])
        continue;
      used[j] = true; // The `mentors[j]` is used.
      dfs(students, mentors, i + 1, scoreSum + getScore(students[i], mentors[j]), used);
      used[j] = false;
    }
  }

  private int getScore(int[] student, int[] mentor) {
    int score = 0;
    for (int i = 0; i < student.length; ++i)
      if (student[i] == mentor[i])
        ++score;
    return score;
  }
}
// code provided by PROGIEZ

1947. Maximum Compatibility Score Sum LeetCode Solution in Python

class Solution:
  def maxCompatibilitySum(
      self,
      students: list[list[int]],
      mentors: list[list[int]],
  ) -> int:
    ans = 0

    def dfs(i: int, scoreSum: int, used: list[bool]) -> None:
      nonlocal ans
      if i == len(students):
        ans = max(ans, scoreSum)
        return

      for j, mentor in enumerate(mentors):
        if used[j]:
          continue
        used[j] = True  # The `mentors[j]` is used.
        dfs(i + 1, scoreSum + sum(s == m
                                  for s, m in zip(students[i], mentor)), used)
        used[j] = False

    dfs(0, 0, [False] * len(students))
    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents