# Maximum Compatibility Score Sum **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-compatibility-score-sum) Canonical: https://scaleengineer.com/dsa/problems/maximum-compatibility-score-sum **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask) **Data structures:** Array --- ## 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** 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`. # Approaches ## Brute Force using Backtracking The problem asks for an optimal pairing between students and mentors to maximize the total compatibility score. Since each of the `m` students must be paired with a unique mentor from the `m` available mentors, any valid pairing corresponds to a permutation of the mentors. The brute-force approach is to generate every possible permutation of mentors, calculate the total score for each permutation, and find the maximum among them. This can be implemented using a recursive backtracking algorithm that explores all possible assignments. **Time:** O(m^2 * n + m! * m). The pre-computation of the `scores` matrix takes `O(m * m * n)`. The backtracking part explores `m!` permutations. For each permutation, we do `m` additions to calculate the total score, but in our recursive implementation, the additions are done along the path. The number of nodes in the recursion tree is on the order of `m!`, leading to a time complexity of `O(m! * m)`. The total time is the sum of these two parts. · **Space:** O(m^2). We need `O(m^2)` space for the pre-computed `scores` matrix. The recursion depth is `m`, and we use a boolean array of size `m`, so the space for recursion is `O(m)`. Thus, the total space is dominated by the scores matrix. **Pros:** It is guaranteed to find the optimal solution because it checks every possibility.; The logic is relatively straightforward to understand and implement. **Cons:** The time complexity is `O(m!)`, which is very high and only feasible for very small values of `m` (like `m <= 8` in this problem).; It explores many redundant paths, which is improved upon by dynamic programming. ### Explanation This approach systematically explores every single possible assignment of students to mentors. We can think of this as building an assignment one student at a time. ```java class Solution { int maxScore = 0; public int maxCompatibilitySum(int[][] students, int[][] mentors) { int m = students.length; int n = students[0].length; // Pre-compute scores for all student-mentor pairs int[][] scores = new int[m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { int score = 0; for (int k = 0; k < n; k++) { if (students[i][k] == mentors[j][k]) { score++; } } scores[i][j] = score; } } boolean[] visitedMentors = new boolean[m]; backtrack(0, 0, scores, visitedMentors); return maxScore; } private void backtrack(int studentIndex, int currentScore, int[][] scores, boolean[] visitedMentors) { int m = scores.length; if (studentIndex == m) { maxScore = Math.max(maxScore, currentScore); return; } // Iterate through all mentors for the current student for (int mentorIndex = 0; mentorIndex < m; mentorIndex++) { if (!visitedMentors[mentorIndex]) { // Choose visitedMentors[mentorIndex] = true; // Recurse backtrack(studentIndex + 1, currentScore + scores[studentIndex][mentorIndex], scores, visitedMentors); // Unchoose (Backtrack) visitedMentors[mentorIndex] = false; } } } } ``` ### Algorithm * **Pre-computation:** First, it's helpful to pre-compute the compatibility scores for every possible student-mentor pair and store them in an `m x m` matrix, let's call it `scores`. `scores[i][j]` will hold the score for student `i` and mentor `j`. This takes `O(m*m*n)` time. * **Backtracking Function:** Define a recursive function, for example, `backtrack(studentIndex, currentScore)`. This function will try to assign a mentor to `studentIndex`. * **State:** The state of the recursion is defined by the `studentIndex` we are currently considering and the set of mentors who have already been assigned. We can use a boolean array, `visitedMentors`, to keep track of used mentors. * **Base Case:** The recursion stops when `studentIndex` equals `m`, which means all students have been assigned a mentor. At this point, we compare the `currentScore` with a global maximum score and update it if the `currentScore` is higher. * **Recursive Step:** For the current `studentIndex`, we iterate through all available mentors (`j` from `0` to `m-1`). If `mentors[j]` has not been visited: 1. Mark `mentors[j]` as visited. 2. Add the score `scores[studentIndex][j]` to `currentScore`. 3. Make a recursive call for the next student: `backtrack(studentIndex + 1, newCurrentScore)`. 4. After the recursive call returns, we backtrack by un-marking `mentors[j]` as visited and subtracting the score. This allows us to explore other possible assignments for `studentIndex`. ## Backtracking with Memoization and Bitmasking This approach optimizes the brute-force backtracking by using dynamic programming with memoization. We can notice that in the backtracking solution, we might solve the same subproblem multiple times. A subproblem can be defined as finding the maximum score for a subset of students and a subset of mentors. By using a bitmask to represent the set of used mentors, we can define a state `(studentIndex, mask)` and store its result in a memoization table. This prevents re-computation and significantly reduces the time complexity from factorial to exponential with a smaller base. **Time:** O(m^2 * n + m^2 * 2^m). Pre-computation takes `O(m^2 * n)`. The DP part involves `m * 2^m` states. For each state, we iterate through `m` mentors to decide the assignment. So, the DP calculation takes `O(m * 2^m * m) = O(m^2 * 2^m)`. The total time is the sum of these two. · **Space:** O(m^2 + m * 2^m). We use `O(m^2)` for the `scores` matrix and `O(m * 2^m)` for the `memo` table. The recursion stack depth is `O(m)`. The memoization table dominates the space complexity. **Pros:** Significantly more efficient than the simple backtracking approach.; It is a standard and powerful technique for solving assignment-style problems with small constraints. **Cons:** The space complexity of `O(m * 2^m)` can be large, though it's acceptable for `m <= 8`.; The time complexity is still exponential, making it unsuitable for larger `m` (e.g., `m > 20`). ### Explanation The state `(i, mask)` uniquely identifies the subproblem of assigning students `i, i+1, ..., m-1` to the set of available mentors not included in `mask`. By storing the solution for each state, we ensure that we compute it only once. ```java class Solution { public int maxCompatibilitySum(int[][] students, int[][] mentors) { int m = students.length; int n = students[0].length; int[][] scores = new int[m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { int score = 0; for (int k = 0; k < n; k++) { if (students[i][k] == mentors[j][k]) { score++; } } scores[i][j] = score; } } // memo[i][mask] stores the max score for students i..m-1 with available mentors NOT in mask Integer[][] memo = new Integer[m][1 << m]; return solve(0, 0, scores, memo); } private int solve(int studentIndex, int mask, int[][] scores, Integer[][] memo) { int m = scores.length; if (studentIndex == m) { return 0; } if (memo[studentIndex][mask] != null) { return memo[studentIndex][mask]; } int maxScore = 0; // Iterate through all mentors for (int mentorIndex = 0; mentorIndex < m; mentorIndex++) { // Check if mentor at mentorIndex is available (j-th bit is 0) if ((mask & (1 << mentorIndex)) == 0) { // Assign student `studentIndex` to mentor `mentorIndex` and recurse int currentTotalScore = scores[studentIndex][mentorIndex] + solve(studentIndex + 1, mask | (1 << mentorIndex), scores, memo); maxScore = Math.max(maxScore, currentTotalScore); } } return memo[studentIndex][mask] = maxScore; } } ``` ### Algorithm * **Pre-computation:** As with the brute-force approach, we first compute the `scores[i][j]` matrix in `O(m^2 * n)` time. * **DP State:** The state of our DP can be defined as `(i, mask)`, representing the maximum score we can get by assigning students from index `i` to `m-1` to the set of available mentors represented by `mask`. A `1` at the `j`-th position in `mask` means mentor `j` is taken, and a `0` means available. * **Memoization:** We use a 2D array, `memo[i][mask]`, to store the results of subproblems to avoid re-computation. `memo` will have dimensions `m x 2^m`. * **Recursive Function:** We define a function `solve(studentIndex, mask)`. * **Base Case:** If `studentIndex == m`, all students have been assigned, so we return a score of 0. * **Transitions:** For the current `studentIndex`, we iterate through all mentors `j`. If mentor `j` is available (i.e., `(mask & (1 << j)) == 0`), we consider assigning student `studentIndex` to mentor `j`. The score for this choice would be `scores[studentIndex][j]` plus the result of the subproblem for the next student and the updated mask: `solve(studentIndex + 1, mask | (1 << j))`. We take the maximum over all possible choices for `j`. * **Final Answer:** The answer to the original problem is the result of the initial call `solve(0, 0)`. ## Maximum Weight Bipartite Matching (Hungarian Algorithm) The most efficient way to solve this problem is to recognize it as a classic instance of the Assignment Problem, or Maximum Weight Bipartite Matching. We can construct a bipartite graph where one set of nodes represents the students and the other represents the mentors. The weight of the edge between a student and a mentor is their compatibility score. We then need to find a perfect matching with the maximum total weight. The Hungarian algorithm is a well-known polynomial-time algorithm that solves this problem. **Time:** O(m^2 * n + m^3). The pre-computation of scores takes `O(m^2 * n)`. The standard Hungarian algorithm runs in `O(m^3)`. Therefore, the total time complexity is dominated by the sum of these two parts. · **Space:** O(m^2). The algorithm operates on the `m x m` cost matrix and typically requires a few other `O(m^2)` or `O(m)` arrays for its internal state, making the total space complexity `O(m^2)`. **Pros:** Provides a polynomial-time solution (`O(m^3)`), which is highly efficient and scales much better than exponential solutions.; It is a standard, well-studied algorithm for this class of problems. **Cons:** The Hungarian algorithm is non-trivial to implement correctly from scratch.; For the given small constraints (`m <= 8`), the performance gain over the DP with bitmasking approach is not substantial, and the DP approach is often simpler to code in a contest setting. ### Explanation This approach leverages a standard algorithm from graph theory to solve the problem in polynomial time, which is asymptotically the best possible. Below is the code structure for this approach. Note that a full implementation of the Hungarian algorithm is omitted due to its complexity, but the setup illustrates the concept. ```java class Solution { public int maxCompatibilitySum(int[][] students, int[][] mentors) { int m = students.length; int n = students[0].length; // Step 1: Pre-compute the compatibility scores for all pairs. int[][] scores = new int[m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { int score = 0; for (int k = 0; k < n; k++) { if (students[i][k] == mentors[j][k]) { score++; } } scores[i][j] = score; } } // Step 2: Create a cost matrix for the assignment problem. // We want to maximize score, which is equivalent to minimizing cost, // where cost = max_score - score. Max possible score is n. int[][] costMatrix = new int[m][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { costMatrix[i][j] = n - scores[i][j]; } } // Step 3: Apply the Hungarian algorithm to find the minimum cost assignment. // int[] assignment = hungarianAlgorithm(costMatrix); // This function would return an array where assignment[i] = j, // meaning student i is assigned to mentor j. // Let's assume minCost is the result from the algorithm. // int minCost = 0; // for (int i = 0; i < m; i++) { // minCost += costMatrix[i][assignment[i]]; // } // return m * n - minCost; // Since implementing the Hungarian algorithm is complex, and the DP approach // is sufficient for the given constraints, we would typically use the DP approach in a contest. // The conceptual framing as an assignment problem is the key takeaway. // For a working solution, we can use the DP code from the previous approach. Integer[][] memo = new Integer[m][1 << m]; return solve(0, 0, scores, memo); } private int solve(int studentIndex, int mask, int[][] scores, Integer[][] memo) { int m = scores.length; if (studentIndex == m) return 0; if (memo[studentIndex][mask] != null) return memo[studentIndex][mask]; int maxScore = 0; for (int mentorIndex = 0; mentorIndex < m; mentorIndex++) { if ((mask & (1 << mentorIndex)) == 0) { maxScore = Math.max(maxScore, scores[studentIndex][mentorIndex] + solve(studentIndex + 1, mask | (1 << mentorIndex), scores, memo)); } } return memo[studentIndex][mask] = maxScore; } } ``` ### Algorithm * **Model as Bipartite Graph:** View students and mentors as two sets of vertices in a bipartite graph. An edge exists between every student `i` and mentor `j`. * **Assign Weights:** The weight of the edge between student `i` and mentor `j` is their compatibility score, `score(i, j)`. * **Problem Formulation:** The task is to find a perfect matching (a set of `m` edges where no two edges share a vertex) such that the sum of the weights of the edges in the matching is maximized. This is the Maximum Weight Bipartite Matching problem, also known as the Assignment Problem. * **Transform for Minimization:** The Hungarian algorithm solves the minimum cost assignment problem. To use it for maximization, we transform our scores (profits) into costs. We create a cost matrix `cost[i][j] = C - score(i, j)`, where `C` is a constant at least as large as the maximum possible score (e.g., `C=n`). Minimizing `sum(C - score)` is equivalent to maximizing `sum(score)`. * **Apply Hungarian Algorithm:** Run the Hungarian algorithm on the `m x m` cost matrix. This will give the minimum possible total cost for a valid assignment. * **Calculate Final Result:** The minimum cost found by the algorithm, `min_total_cost`, can be converted back to the maximum score: `max_score_sum = m * C - min_total_cost`. # Solutions ### Java ```java class Solution { private int[][] g; private boolean[] vis; private int m; private int ans; public int maxCompatibilitySum(int[][] students, int[][] mentors) { m = students.length; g = new int[m][m]; vis = new boolean[m]; for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k < students[i].length; ++k) { g[i][j] += students[i][k] == mentors[j][k] ? 1 : 0; } } } dfs(0, 0); return ans; } private void dfs(int i, int t) { if (i == m) { ans = Math.max(ans, t); return; } for (int j = 0; j < m; ++j) { if (!vis[j]) { vis[j] = true; dfs(i + 1, t + g[i][j]); vis[j] = false; } } } } ``` ### JavaScript ```javascript /** * @param {number[][]} students * @param {number[][]} mentors * @return {number} */ var maxCompatibilitySum = function (students, mentors) { let ans = 0; const m = students.length; const vis = Array(m).fill(false); const g = 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 < students[i].length; ++k) { if (students[i][k] === mentors[j][k]) { g[i][j]++; } } } } const dfs = function (i, s) { if (i >= m) { ans = Math.max(ans, s); return; } for (let j = 0; j < m; ++j) { if (!vis[j]) { vis[j] = true; dfs(i + 1, s + g[i][j]); vis[j] = false; } } }; dfs(0, 0); return ans; }; ``` ### CPP ```cpp class Solution { public: int maxCompatibilitySum ( vector < vector < int >>& students , vector < vector < int >>& mentors ) { int m = students . size (); int n = students [ 0 ]. size (); int g [ m ][ m ]; memset ( g , 0 , sizeof g ); bool vis [ m ]; memset ( vis , 0 , sizeof vis ); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { for ( int k = 0 ; k < n ; ++ k ) { g [ i ][ j ] += students [ i ][ k ] == mentors [ j ][ k ]; } } } int ans = 0 ; function < void ( int , int ) > dfs = [ & ]( int i , int t ) { if ( i == m ) { ans = max ( ans , t ); return ; } for ( int j = 0 ; j < m ; ++ j ) { if ( ! vis [ j ]) { vis [ j ] = true ; dfs ( i + 1 , t + g [ i ][ j ]); vis [ j ] = false ; } } }; dfs ( 0 , 0 ); return ans ; } }; ``` ### Python ```python class Solution: def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int: def dfs(i, t): if i == m: nonlocal ans ans = max(ans, t) return for j in range(m): if not vis[j]: vis[j] = True dfs(i + 1, t + g[i][j]) vis[j] = False m = len(students) g = [[0] * m for _ in range(m)] for i in range(m): for j in range(m): g[i][j] = sum(a == b for a, b in zip(students[i], mentors[j])) vis = [False] * m ans = 0 dfs(0, 0) return ans ```