Skip to main content
Talentd

Maximum Compatibility Score Sum - Solution & Explanation

MediumArrayDynamic ProgrammingBacktrackingBit Manipulation16 min readAsked at: Meta
Practice this problem

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.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.

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.

Approach 1: Backtracking with Permutations

This approach involves generating all possible permutations of mentor assignments for the students. We calculate the compatibility score for each permutation and keep track of the maximum score found. This method exhaustively tries each possible pairing and selects the optimal one.

This Python solution uses the itertools.permutations function to produce all possible assignments of m mentors to m students. For each permutation, it calculates the total compatibility score by summing up individual scores of assigned student-mentor pairs. The maximum score is updated whenever a new higher score is found.

Code

PythonJava

Python

Java

Complexity

The time complexity is O((m!) * m * n), where m is the number of students and n is the number of questions. The space complexity is O(m!).

Try this approach in the editor →

Approach 2: Dynamic Programming with Bitmasking

This approach uses dynamic programming with bitmasking to efficiently calculate the maximum compatibility score. The DP state is represented as a bitmask that keeps track of which mentors have already been assigned to a student, optimizing both time and space usage.

This C++ solution uses dynamic programming with bitmasking. The dp array is used to store the maximum compatibility scores for different combinations of assigned mentors (represented as bitmask states). The findMaxScore function is a recursive function that attempts to assign available mentors (those not set in the mask) to the current student and recursively solves subproblems.

Code

C++C#

C++

C#

Complexity

The time complexity is O(m * (2^m) * n), and the space complexity is O(2^m).

Try this approach in the editor →

Approach 3: Preprocessing + Backtracking

We can first preprocess the compatibility score g[i][j] between each student i and mentor j, and then use a backtracking algorithm to solve the problem.

Define a function dfs(i, s), where i represents the current student being processed, and s represents the current sum of compatibility scores.

In dfs(i, s), if i geq m, it means all students have been assigned, and we update the answer to max(ans, s). Otherwise, we enumerate which mentor the i-th student can be assigned to, and then recursively process the next student. During the process, we use an array vis to record which mentors have already been assigned to avoid duplicate assignments.

We call dfs(0, 0) to get the maximum compatibility score sum.

The time complexity is O(m!), and the space complexity is O(m^2). Here, m is the number of students and mentors.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Permutations

The time complexity is O((m!) * m * n), where m is the number of students and n is the number of questions. The space complexity is O(m!).

Dynamic Programming with Bitmasking

The time complexity is O(m * (2^m) * n), and the space complexity is O(2^m).

Preprocessing + Backtracking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with PermutationsO(n! * n * m)O(n)Small input sizes where brute force is acceptable and useful for understanding all pair assignments
Dynamic Programming with BitmaskingO(n * 2^n + n^2 * m)O(2^n)Optimal solution for n ≤ 8; reduces factorial search to subset DP using bitmask states

Video Solution

LeetCode 1947. Maximum Compatibility Score Sum | 🏆 Weekly Contest 251 | Explained • Cherry Coding [IIT-G] • 2,624 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Compatibility Score Sum easy or hard?
Maximum Compatibility Score Sum is rated Medium on LeetCode. The brute-force permutation solution is straightforward, but recognizing the bitmask dynamic programming optimization requires familiarity with subset DP patterns.
How to solve Maximum Compatibility Score Sum in O(n * 2^n)?
Precompute compatibility scores between every student and mentor. Use a DP array indexed by a bitmask where each bit represents whether a mentor is assigned. If the mask has k bits set, assign the next student (k) to any unused mentor and update the DP value.
What is the best approach for Maximum Compatibility Score Sum?
Dynamic Programming with bitmasking is the most efficient approach. It represents mentor assignments as a bitmask and builds the optimal compatibility score using DP over subsets. This reduces the search space from n! permutations to O(n * 2^n) states.
What data structure is used in Maximum Compatibility Score Sum?
The optimal solution uses arrays for the compatibility matrix and a DP array indexed by bitmasks. Bit manipulation operations track which mentors are already assigned, making subset transitions efficient.
What is the time complexity of Maximum Compatibility Score Sum?
The optimal bitmask DP solution runs in O(n * 2^n + n^2 * m) time, where n is the number of students/mentors and m is the number of answers per person. The extra n^2 * m cost comes from precomputing compatibility scores between every student and mentor pair.
Maximum Compatibility Score Sum Python or Java solution approach?
A common Python or Java approach uses backtracking to generate mentor permutations and compute scores recursively. For better performance, implement dynamic programming with a bitmask to store the best score for each assignment state.
Is Maximum Compatibility Score Sum asked at Google, Amazon, or Meta?
Problems involving bitmask dynamic programming and assignment optimization frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of state compression, permutation search, and DP over subsets.

Ready to solve this problem?

Practice Maximum Compatibility Score Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays