Maximum Compatibility Score Sum

Medium
1346.

Maximum Compatibility Score Sum

Maximum Compatibility Score Sum is a medium coding problem on dynamic programming, bit manipulation and backtracking, asked in Amazon and Google interviews.

A survey has n yes/no questions. m students and m mentors answered it: students[i] and mentors[j] are arrays of n answers, each 0 or 1.

The compatibility score of a student and a mentor is the number of questions they answered the same way. Pair every student with a different mentor (a one-to-one assignment).

Return the maximum possible sum of the compatibility scores of the pairs.

Example 1

Input
students = [[1,0],[0,1]], mentors = [[0,1],[1,0]]
Output
4
Explanation
Student 0 with mentor 1 and student 1 with mentor 0 agree on everything.

Example 2

Input
students = [[0,0]], mentors = [[1,1]]
Output
0

Example 3

Input
students = [[1,1,1],[0,0,0]], mentors = [[1,0,1],[0,1,0]]
Output
4

Constraints

  • m == students.length == mentors.length
  • n == students[i].length == mentors[j].length
  • 1 <= m, n <= 8
  • students[i][k] and mentors[j][k] are 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} students
 * @param {number[][]} mentors
 * @return {number}
 */
var maxCompatibilitySum = function(students, mentors) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Compatibility Score Sum — Problem & Solution

Maximum Compatibility Score Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Compatibility Score Sum is a medium coding problem on dynamic programming, bit manipulation and backtracking, asked in Amazon and Google interviews.

Problem statement

A survey has n yes/no questions. m students and m mentors answered it: students[i] and mentors[j] are arrays of n answers, each 0 or 1.

The compatibility score of a student and a mentor is the number of questions they answered the same way. Pair every student with a different mentor (a one-to-one assignment).

Return the maximum possible sum of the compatibility scores of the pairs.

Example 1

Input: students = [[1,0],[0,1]], mentors = [[0,1],[1,0]]
Output: 4
Explanation: Student 0 with mentor 1 and student 1 with mentor 0 agree on everything.

Example 2

Input: students = [[0,0]], mentors = [[1,1]]
Output: 0

Example 3

Input: students = [[1,1,1],[0,0,0]], mentors = [[1,0,1],[0,1,0]]
Output: 4

Constraints

  • m == students.length == mentors.length
  • n == students[i].length == mentors[j].length
  • 1 <= m, n <= 8
  • students[i][k] and mentors[j][k] are 0 or 1

Hints for Maximum Compatibility Score Sum

  1. Hint 1

    Precompute the score of every student–mentor pair: an m x m table.

  2. Hint 2

    With m <= 8 even trying all m! assignments works, but a bitmask DP is cleaner.

  3. Hint 3

    Let dp[mask] be the best total when the first popcount(mask) students are paired with the mentors in mask; extend by pairing the next student with each free mentor.

How to solve Maximum Compatibility Score Sum

This is an assignment problem on a tiny m x m score table: process the students in order and keep a bitmask of mentors already taken.

Approach

  1. Compute score[i][j] = number of equal answers between student i and mentor j.
  2. Set dp[0] = 0; visit masks in increasing order.
  3. For mask, the next student is i = popcount(mask); for every mentor j not in mask, update dp[mask | 1<<j] with dp[mask] + score[i][j].
  4. Return dp[2^m - 1].

Why it works

Any assignment pairs students 0, 1, …, m-1 in turn with distinct mentors, i.e. it is a path from the empty mask to the full mask collecting exactly its scores. The best completion depends only on which mentors remain, so keeping the best score per mask is exact.

Complexity

  • Time — O(m · 2^m + m² · n)
  • Space — O(2^m)

Pitfalls

  • Pairing each student greedily with their best remaining mentor is not optimal.
  • Compatibility counts matching answers, zeros included — not the number of shared 1s.
  • The student index is the popcount of the mask; no second DP dimension is needed.

Reference solution

Python

from typing import List

def maxCompatibilitySum(students: List[List[int]], mentors: List[List[int]]) -> int:
    m = len(students)
    n = len(students[0])
    score = [[sum(1 for q in range(n) if students[i][q] == mentors[j][q]) for j in range(m)] for i in range(m)]
    full = 1 << m
    dp = [-1] * full
    dp[0] = 0
    for mask in range(full):
        if dp[mask] < 0:
            continue
        i = bin(mask).count("1")
        if i >= m:
            continue
        for j in range(m):
            if mask & (1 << j):
                continue
            nm = mask | (1 << j)
            v = dp[mask] + score[i][j]
            if v > dp[nm]:
                dp[nm] = v
    return dp[full - 1]

Java

public static int maxCompatibilitySum(int[][] students, int[][] mentors) {
    int m = students.length, n = students[0].length, full = 1 << m;
    int[][] score = new int[m][m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int q = 0; q < n; q++) if (students[i][q] == mentors[j][q]) score[i][j]++;
        }
    }
    int[] dp = new int[full];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] < 0) continue;
        int i = Integer.bitCount(mask);
        if (i >= m) continue;
        for (int j = 0; j < m; j++) {
            if ((mask & (1 << j)) != 0) continue;
            int nm = mask | (1 << j);
            dp[nm] = Math.max(dp[nm], dp[mask] + score[i][j]);
        }
    }
    return dp[full - 1];
}

C++

int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
    int m = students.size(), n = students[0].size(), full = 1 << m;
    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 q = 0; q < n; q++) if (students[i][q] == mentors[j][q]) score[i][j]++;
        }
    }
    vector<int> dp(full, -1);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] < 0) continue;
        int i = __builtin_popcount(mask);
        if (i >= m) continue;
        for (int j = 0; j < m; j++) {
            if (mask & (1 << j)) continue;
            int nm = mask | (1 << j);
            dp[nm] = max(dp[nm], dp[mask] + score[i][j]);
        }
    }
    return dp[full - 1];
}

JavaScript

var maxCompatibilitySum = function(students, mentors) {
    var m = students.length, n = students[0].length, full = 1 << m;
    var score = [];
    for (var i = 0; i < m; i++) {
        score.push([]);
        for (var j = 0; j < m; j++) {
            var s = 0;
            for (var q = 0; q < n; q++) if (students[i][q] === mentors[j][q]) s++;
            score[i].push(s);
        }
    }
    var dp = new Array(full).fill(-1);
    dp[0] = 0;
    for (var mask = 0; mask < full; mask++) {
        if (dp[mask] < 0) continue;
        var st = 0;
        for (var x = mask; x; x >>= 1) st += x & 1;
        if (st >= m) continue;
        for (var t = 0; t < m; t++) {
            if (mask & (1 << t)) continue;
            var nm = mask | (1 << t), v = dp[mask] + score[st][t];
            if (v > dp[nm]) dp[nm] = v;
        }
    }
    return dp[full - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Bit Manipulation