Maximum Compatibility Score Sum
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 thesum of the compatibility scores.
Given students and mentors, return themaximum compatibility score sum that can be achieved.
Examples
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.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k]is either0or1.mentors[j][k]is either0or1.
Solution
Method 1 – Bitmask Dynamic Programming
Intuition
Since the number of students/mentors is small (≤ 8), we can try all possible assignments efficiently using bitmasking. For each possible assignment of students to mentors, we calculate the total compatibility score and keep the maximum.
Approach
- Precompute the compatibility score for every student-mentor pair.
- Use dynamic programming with bitmasking:
- The state is the set of mentors already assigned (represented as a bitmask).
- For each state, try assigning the next student to any unassigned mentor and update the DP.
- The answer is the maximum score when all students are assigned.
Code
C++
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size(), n = students[0].size();
vector<vector<int>> score(m, vector<int>(m, 0));
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < n; ++k)
score[i][j] += students[i][k] == mentors[j][k];
vector<int> dp(1 << m, 0);
for (int mask = 0; mask < (1 << m); ++mask) {
int cnt = __builtin_popcount(mask);
if (cnt >= m) continue;
for (int j = 0; j < m; ++j) {
if (!(mask & (1 << j))) {
dp[mask | (1 << j)] = max(dp[mask | (1 << j)], dp[mask] + score[cnt][j]);
}
}
}
return dp[(1 << m) - 1];
}
};
Go
func maxCompatibilitySum(students [][]int, mentors [][]int) int {
m, n := len(students), len(students[0])
score := make([][]int, m)
for i := range score {
score[i] = make([]int, m)
for j := 0; j < m; j++ {
for k := 0; k < n; k++ {
if students[i][k] == mentors[j][k] {
score[i][j]++
}
}
}
}
dp := make([]int, 1<<m)
for mask := 0; mask < (1<<m); mask++ {
cnt := bits.OnesCount(uint(mask))
if cnt >= m { continue }
for j := 0; j < m; j++ {
if mask&(1<<j) == 0 {
next := mask | (1 << j)
if dp[next] < dp[mask]+score[cnt][j] {
dp[next] = dp[mask] + score[cnt][j]
}
}
}
}
return dp[(1<<m)-1]
}
Java
class Solution {
public int maxCompatibilitySum(int[][] students, int[][] mentors) {
int m = students.length, n = students[0].length;
int[][] score = new int[m][m];
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < n; k++)
if (students[i][k] == mentors[j][k]) score[i][j]++;
int[] dp = new int[1 << m];
for (int mask = 0; mask < (1 << m); mask++) {
int cnt = Integer.bitCount(mask);
if (cnt >= m) continue;
for (int j = 0; j < m; j++) {
if ((mask & (1 << j)) == 0) {
dp[mask | (1 << j)] = Math.max(dp[mask | (1 << j)], dp[mask] + score[cnt][j]);
}
}
}
return dp[(1 << m) - 1];
}
}
Kotlin
class Solution {
fun maxCompatibilitySum(students: Array<IntArray>, mentors: Array<IntArray>): Int {
val m = students.size
val n = students[0].size
val score = Array(m) { IntArray(m) }
for (i in 0 until m)
for (j in 0 until m)
for (k in 0 until n)
if (students[i][k] == mentors[j][k]) score[i][j]++
val dp = IntArray(1 shl m)
for (mask in 0 until (1 shl m)) {
val cnt = mask.countOneBits()
if (cnt >= m) continue
for (j in 0 until m) {
if ((mask and (1 shl j)) == 0) {
dp[mask or (1 shl j)] = maxOf(dp[mask or (1 shl j)], dp[mask] + score[cnt][j])
}
}
}
return dp[(1 shl m) - 1]
}
}
Python
class Solution:
def maxCompatibilitySum(self, students: list[list[int]], mentors: list[list[int]]) -> int:
m, n = len(students), len(students[0])
score = [[sum(s == t for s, t in zip(students[i], mentors[j])) for j in range(m)] for i in range(m)]
dp = [0] * (1 << m)
for mask in range(1 << m):
cnt = bin(mask).count('1')
if cnt >= m: continue
for j in range(m):
if not (mask & (1 << j)):
dp[mask | (1 << j)] = max(dp[mask | (1 << j)], dp[mask] + score[cnt][j])
return dp[(1 << m) - 1]
Rust
impl Solution {
pub fn max_compatibility_sum(students: Vec<Vec<i32>>, mentors: Vec<Vec<i32>>) -> i32 {
let m = students.len();
let n = students[0].len();
let mut score = vec![vec![0; m]; m];
for i in 0..m {
for j in 0..m {
for k in 0..n {
if students[i][k] == mentors[j][k] {
score[i][j] += 1;
}
}
}
}
let mut dp = vec![0; 1 << m];
for mask in 0..(1 << m) {
let cnt = mask.count_ones() as usize;
if cnt >= m { continue; }
for j in 0..m {
if (mask & (1 << j)) == 0 {
let next = mask | (1 << j);
dp[next] = dp[next].max(dp[mask] + score[cnt][j]);
}
}
}
dp[(1 << m) - 1]
}
}
TypeScript
class Solution {
maxCompatibilitySum(students: number[][], mentors: number[][]): number {
const m = students.length, n = students[0].length;
const score = Array.from({length: m}, () => Array(m).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < m; j++)
for (let k = 0; k < n; k++)
if (students[i][k] === mentors[j][k]) score[i][j]++;
const dp = Array(1 << m).fill(0);
for (let mask = 0; mask < (1 << m); mask++) {
const cnt = mask.toString(2).split('1').length - 1;
if (cnt >= m) continue;
for (let j = 0; j < m; j++) {
if ((mask & (1 << j)) === 0) {
dp[mask | (1 << j)] = Math.max(dp[mask | (1 << j)], dp[mask] + score[cnt][j]);
}
}
}
return dp[(1 << m) - 1];
}
}
Complexity
- ⏰ Time complexity:
O(m^2 * 2^m), wheremis the number of students/mentors. We process each bitmask (2^m), and for each, try allmmentors, and precomputem^2scores. - 🧺 Space complexity:
O(m^2 + 2^m), for the score matrix and DP array.