LeetCode 1947 - Maximum Compatibility Score Sum

LeetCode Problem 1947

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem is asking us to optimally pair students with mentors such that the sum of their compatibility scores is maximized. Each student and each mentor has answered n yes/no questions represented by 0s and 1s. A student-mentor pair's compatibility score is the count of matching answers. For instance, if a student answers [1, 0, 1] and the mentor answers [0, 0, 1], the score is 2 because two answers match.

The input consists of two m x n matrices: students and mentors. Each row of students represents one student's answers, and each row of mentors represents one mentor's answers. The output is a single integer representing the maximum sum of compatibility scores achievable by assigning each student to exactly one mentor and vice versa.

The constraints are small: 1 <= m, n <= 8. This allows us to consider solutions that involve examining all permutations of student-mentor assignments since 8! = 40320 is computationally feasible. We also know that each answer is binary, which allows for bit manipulation to speed up score calculations.

Important edge cases include: all students and mentors having identical answers (maximum score), all answers completely opposite (score of zero), and the smallest case where m = 1 and n = 1.

Approaches

The brute-force approach is to generate all permutations of mentor indices and assign each permutation to students. For each assignment, we calculate the total compatibility score by summing the scores for each student-mentor pair. This guarantees correctness because it exhaustively examines every possible assignment. However, its time complexity is O(m! * m * n) due to m! permutations and calculating compatibility for each student-mentor pair, which is inefficient for larger m.

The key insight for an optimal solution is to use backtracking with pruning. Instead of generating all permutations at once, we recursively assign students to mentors, marking mentors as assigned. For each partial assignment, we track the accumulated score. If a branch cannot beat the current maximum score (for example, if all remaining possible matches cannot improve the score), we prune that branch. This reduces redundant computation while guaranteeing the optimal solution. Bitmasking can also be used to efficiently track which mentors are assigned.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m! * m * n)	O(m)	Generate all permutations of mentor assignments and calculate scores
Backtracking with Bitmask	O(m * 2^m * n)	O(2^m)	Use recursion with a bitmask to track assigned mentors and prune suboptimal paths

Algorithm Walkthrough

1. Precompute compatibility scores for all student-mentor pairs in a 2D array score[i][j], where i is the student index and j is the mentor index. This allows constant-time lookup during backtracking.
2. Define a recursive function dfs(student_index, mask) that tries to assign the current student to any unassigned mentor. mask is a bitmask where the j-th bit is 1 if mentor j is assigned.
3. If student_index equals m, return 0 since all students are assigned.
4. For each mentor j from 0 to m-1, check if mask & (1 << j) is 0 (mentor j is unassigned). If yes, recursively call dfs(student_index + 1, mask | (1 << j)) and add score[student_index][j] to the result.
5. Track the maximum sum across all recursive calls for the current student.
6. Return the maximum sum obtained from assigning all students.

Why it works: The backtracking explores all valid student-mentor assignments while pruning invalid states using the bitmask. Precomputing scores allows constant-time evaluation for each assignment. Since all permutations are considered, the algorithm guarantees the maximum compatibility sum is found.

Python Solution

from typing import List

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m, n = len(students), len(students[0])
        
        # Precompute compatibility scores
        score = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(m):
                score[i][j] = sum(students[i][k] == mentors[j][k] for k in range(n))
        
        memo = {}
        
        def dfs(student_index: int, mask: int) -> int:
            if student_index == m:
                return 0
            if (student_index, mask) in memo:
                return memo[(student_index, mask)]
            
            max_sum = 0
            for j in range(m):
                if not mask & (1 << j):
                    current_sum = score[student_index][j] + dfs(student_index + 1, mask | (1 << j))
                    max_sum = max(max_sum, current_sum)
            memo[(student_index, mask)] = max_sum
            return max_sum
        
        return dfs(0, 0)

The Python implementation first precomputes the compatibility scores in score[i][j]. The dfs function uses recursion and a bitmask to efficiently track which mentors are assigned. Memoization ensures that repeated subproblems are not recomputed, reducing the effective time complexity from exponential to O(m * 2^m).

Go Solution

func maxCompatibilitySum(students [][]int, mentors [][]int) int {
    m, n := len(students), len(students[0])
    
    // Precompute compatibility scores
    score := make([][]int, m)
    for i := 0; i < m; i++ {
        score[i] = make([]int, m)
        for j := 0; j < m; j++ {
            count := 0
            for k := 0; k < n; k++ {
                if students[i][k] == mentors[j][k] {
                    count++
                }
            }
            score[i][j] = count
        }
    }
    
    memo := make(map[[2]int]int)
    
    var dfs func(int, int) int
    dfs = func(studentIndex int, mask int) int {
        if studentIndex == m {
            return 0
        }
        key := [2]int{studentIndex, mask}
        if val, ok := memo[key]; ok {
            return val
        }
        maxSum := 0
        for j := 0; j < m; j++ {
            if mask&(1<<j) == 0 {
                currentSum := score[studentIndex][j] + dfs(studentIndex+1, mask|(1<<j))
                if currentSum > maxSum {
                    maxSum = currentSum
                }
            }
        }
        memo[key] = maxSum
        return maxSum
    }
    
    return dfs(0, 0)
}

In Go, the approach is nearly identical. The main differences are Go’s type system, using slices instead of lists, and using a [2]int array as the memoization key instead of a tuple. Integer bit operations work the same as in Python.

Worked Examples

Example 1

students = [[1,1,0],[1,0,1],[0,0,1]]

mentors = [[1,0,0],[0,0,1],[1,1,0]]

Compatibility scores:

Student \ Mentor	0	1	2
0	2	1	3
1	2	2	1
2	0	3	1

Backtracking assignment steps:

1. Start with student 0: assign mentor 2 → score 3
2. Student 1: assign mentor 0 → score 2
3. Student 2: assign mentor 1 → score 3

Total = 3 + 2 + 3 = 8

Example 2

All students [0,0], all mentors [1,1]. Every score is 0. Any assignment yields a total score of 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * 2^m * n)	Each student has up to 2^m mask states; for each, we check m mentors and compute scores in O(1) using precomputation
Space	O(2^m + m^2)	2^m for memoization and m^2 for precomputed score table

The backtracking with memoization reduces the factorial complexity of brute-force permutations to exponential but manageable due to small m.

Test Cases

# Provided examples
assert Solution().maxCompatibilitySum([[1,1,0],[1,0,1],[0,0,1]], [[1,0,0],[0,0,1],[1,1,0]]) == 8  # mixed case
assert Solution().maxCompatibilitySum([[0,0],[0,0],[0,0]], [[1,1],[1,1],[1,1]]) == 0  # no matches

# Edge cases
assert Solution().maxCompatibilitySum([[1]], [[1]]) == 1  # smallest