Scale Engineer

Maximum Compatibility Score Sum

Med
#1776Time: 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.
Patterns
Dynamic ProgrammingBacktrackingBit ManipulationBitmask
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;            }        }    }}

Complexity

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.

Trade-offs

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.

Solutions

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;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem