Maximum Compatibility Score Sum - Video Solutions
LeetCode 1947. Maximum Compatibility Score Sum | π Weekly Contest 251 | Explained
Maximum Compatibility Score Sum - Video Solution
Watch 10 video solutions for Maximum Compatibility Score Sum, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Cherry Coding [IIT-G] has 2,624 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k]is either0or1.mentors[j][k]is either0or1.
Approach Overview
Problem Overview: You are given answers from n students and n mentors. Each student must be paired with exactly one mentor. The compatibility score for a pair equals the number of positions where their answers match. The goal is to assign pairs so the total compatibility score is maximized.
Approach 1: Backtracking with Permutations (Time: O(n! * n * m), Space: O(n))
This approach tries every possible assignment of students to mentors. For each permutation of mentors, compute the compatibility score by comparing answers position-by-position. Use backtracking to generate permutations while tracking which mentors are already used. At each step, add the score for the current student-mentor pair and recurse to the next student. Since there are n! permutations and computing each score requires iterating over m answers, the total complexity becomes O(n! * n * m). This works because n β€ 8, but it still explores many redundant states.
Approach 2: Dynamic Programming with Bitmasking (Time: O(n * 2^n + n^2 * m), Space: O(2^n))
The optimal solution treats mentor assignments as a bitmask state. First precompute a compatibility matrix where score[i][j] stores the match score between student i and mentor j. Then use dynamic programming where a mask represents which mentors are already assigned. If a mask has k bits set, it means the first k students are already matched. Iterate through mentors not in the mask, assign one to the next student, and update the DP value. Bit operations efficiently track used mentors, making this a classic bitmask DP pattern. The state space is 2^n, and each state tries up to n mentors.
Recommended for interviews: Start by explaining the permutation-based backtracking solution to show the brute-force search space. Then transition to the bitmask dynamic programming optimization. Interviewers usually expect the O(n * 2^n) DP solution because it demonstrates familiarity with state compression and efficient subset transitions.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Permutations | O(n! * n * m) | O(n) | Small input sizes where brute force is acceptable and useful for understanding all pair assignments |
| Dynamic Programming with Bitmasking | O(n * 2^n + n^2 * m) | O(2^n) | Optimal solution for n β€ 8; reduces factorial search to subset DP using bitmask states |