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

1
2
3
4
5
6
7
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

1
2
3
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.

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

  1. Precompute the compatibility score for every student-mentor pair.
  2. 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.
  3. The answer is the maximum score when all students are assigned.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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), where m is the number of students/mentors. We process each bitmask (2^m), and for each, try all m mentors, and precompute m^2 scores.
  • 🧺 Space complexity: O(m^2 + 2^m), for the score matrix and DP array.