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.
[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.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k] is either 0 or 1.mentors[j][k] is either 0 or 1.In #1947 Maximum Compatibility Score Sum, each student must be paired with exactly one mentor. The compatibility score is the number of identical answers between a student and a mentor. The goal is to maximize the total compatibility score across all pairings.
A useful strategy is to first precompute the compatibility score for every student–mentor pair. Once these scores are known, the problem becomes an assignment problem where we must choose the best one-to-one matching.
A common optimal approach uses Dynamic Programming with Bitmasking. A bitmask represents which mentors have already been assigned. The number of set bits determines which student we are currently assigning. For each state, try assigning any unused mentor and update the maximum score.
This approach efficiently explores all valid pairings while avoiding redundant computation. The time complexity is typically O(n^2 * 2^n) with O(2^n) space. A simpler alternative is backtracking with permutations, though it is less efficient for larger inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Dynamic Programming | O(n^2 * 2^n) | O(2^n) |
| Backtracking / Permutations | O(n! * m) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Calculate the compatibility score for each student-mentor pair.
Try every permutation of students with the original mentors array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving assignment optimization, bitmask DP, and permutation search are common in technical interviews at large tech companies. This problem is a good practice example for understanding state compression and matching strategies.
Yes, the problem can be solved with backtracking by generating all permutations of mentor assignments and calculating the total compatibility score. However, this approach has factorial complexity and is less efficient than the bitmask DP method.
A 2D array is commonly used to store precomputed compatibility scores between students and mentors. A DP array indexed by bitmask is then used to track the maximum score for each assignment state.
The optimal approach typically uses dynamic programming with bitmasking. By representing assigned mentors using a bitmask and assigning students sequentially, you can efficiently explore all valid pairings while avoiding repeated calculations.