1947. Maximum Compatibility Score Sum

MediumBit ManipulationArrayDynamic ProgrammingBacktrackingBitmask
Leetcode Link

Problem Description

The problem presents a scenario where we have n survey questions answered with either 0 or 1, by m students and m mentors. Each student and each mentor have provided their answers, and these answers are represented by two 2D integer arrays: students and mentors. Every student is to be paired with exactly one mentor, and vice versa.

A compatibility score is defined for each student-mentor pair, which is just the count of the number of identical answers they have given. The goal is to find the pairing between students and mentors that maximizes the total sum of all compatibility scores.

Intuition

To solve this problem, we can think in terms of permutations and combinations because we want to find the maximally compatible pairing. The approach is to try, for each student, every possible mentor that has not been paired yet and calculate the compatibility score. By exploring all possible pairings, we can ensure that no compatibility score is left unchecked.

An efficient way to explore all the possibilities without repetition is to use a depth-first search (DFS) approach. We traverse the possible pairings in a recursive manner, effectively creating a search tree where each level corresponds to a student and each branch from a node represents trying out a mentor for that student.

Here are the steps we follow in the solution:

  1. Create a matrix g where g[i][j] stores the compatibility score between student i and mentor j, which we calculate by comparing their answers.

  2. Keep a visited array vis to track which mentors have been paired already.

  3. Perform DFS starting from the first student (index 0), and for each student, try pairing them with each unvisited mentor. Update the running total of the score and mark the mentor as visited.

  4. After trying out a mentor for a student, we backtrack by marking this mentor as unvisited and trying another unvisited mentor for the same student.

  5. Whenever we reach a pairing where all students are paired (base case of the DFS where i == m), we compare the total score with the current maximum score ans and update ans if the new score is higher.

  6. After all possibilities have been explored, ans holds the maximum compatibility score sum, which is the final answer we return.

Learn more about Dynamic Programming, Backtracking and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

Algorithm and Patterns

The solution uses a Depth-First Search (DFS) recursive algorithm to explore all potential student-mentor pairings.

Data Structures

  • A 2D array g that holds the compatibility scores between all students and mentors.
  • A vis array acting as a boolean visited tracker, indicating whether a mentor has already been paired.

Pattern Used

The pattern used in this problem is backtracking, where we try different options, and as soon as we determine that a current path won't lead us to a solution, or we find a solution, we go back and try other options.

Solution Implementation

Let's break down the given Python function, maxCompatibilitySum, into steps:

  1. Initialization:

    • The function calculates the length m of the students array, which will be used for iterations.
    • It initializes a 2D list g with dimensions m x m where g[i][j] will store the compatibility score of the ith student with the jth mentor.
    • It calculates these scores using a nested for loop and a generator expression with sum(a == b for a, b in zip(students[i], mentors[j])), which sums the number of answers that are identical for student i and mentor j.
    • A list vis is created with m boolean values set to False, representing that initially no mentor has been paired with a student.
    • A variable ans is initialized to 0, which will eventually store the maximum compatibility score sum.

  2. Defining DFS function: The dfs function takes two parameters:

    • Index i that represents the current student being considered.
    • A temporary score t which is the running total of the compatibility scores.

    In this function:

    • The base case checks if i == m, meaning all students have been assigned mentors. It then updates ans if the total compatibility score t is greater than the current ans.
    • The recursive case iterates over all mentors using a loop. For each mentor j that has not yet been visited (vis[j] is False), the function:
      • Sets vis[j] to True to mark the mentor as paired.
      • Recursively calls dfs with the next student i + 1 and the updated score t + g[i][j].
      • Resets vis[j] to False to backtrack and allow the mentor to be paired with another student in subsequent recursion calls.

  3. DFS Traversal:

    • After initializing all data structures and defining the dfs function, the function dfs(0, 0) is called to begin the DFS traversal from the first student and with an initial score of 0.

  4. Return Result:

    • Once all possible pairings have been explored, the function returns ans, which now contains the maximum compatibility score sum that can be achieved.

The solution effectively pairs each student with each possible mentor, backtracks, and tries different pairings, keeping track of the maximum sum found along the way. By searching in this manner, it ensures that the optimal pairing is found, thus maximizing the compatibility score sum.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's consider a case where we have n = 3 survey questions answered by m = 2 students and m = 2 mentors:

The students array is [[1, 0, 1], [0, 1, 0]], and the mentors array is [[0, 0, 1], [1, 1, 0]].

Here is the compatibility matrix g:

  • The compatibility score between student 1 and mentor 1 is 1 (they have one answer in common, the last question).
  • The compatibility score between student 1 and mentor 2 is 2 (they have two answers in common, the first and second question).
  • The compatibility score between student 2 and mentor 1 is 2 (they have two answers in common, the first and second question).
  • The compatibility score between student 2 and mentor 2 is 1 (they have one answer in common, the last question).

Thus, g will look like this: [[1, 2], [2, 1]]

Now, we initialize our visited array vis to [False, False] and set ans to 0.

We apply DFS to calculate the maximum compatibility score:

  1. We start with student 1 (index 0) and try to pair them with each unassigned mentor:
    • If we pair them with mentor 1, we get a score of 1, vis is updated to [True, False].
    • We then move to student 2 (index 1) and since mentor 1 is already paired, we pair student 2 with mentor 2 and get a score of 1. Total score is now 2. We then backtrack since all students are paired.
    • We reset vis to [False, False] and try to pair student 1 with the next mentor.
  2. Now, we pair student 1 with mentor 2, so vis is updated to [False, True], and score is 2.
    • For student 2, the only available mentor is mentor 1, yielding a score of 2. Total score is now 4 which is greater than the previous total. We update ans to 4.

Since we've explored all possible pairings, the final ans is 4, which is the maximum compatibility score sum we can achieve with these pairings.

Thus, the best pairing is student 1 with mentor 2 and student 2 with mentor 1, with each pair having a compatibility score of 2.

The solution methodology ensured every possible pairing was considered, and the best matching was found by exploring all options recursively and backtracking as necessary to try different configurations.

Solution Implementation

1from typing import List
2
3class Solution:
4
5    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
6        # Depth-first search function to recursively explore possible pairings
7        def dfs(index, total_score):
8            nonlocal max_score  # Refer to max_score in the outer scope
9            if index == num_pairs:  # All students have been paired with mentors
10                max_score = max(max_score, total_score)  # Update max_score if a higher score is found
11                return
12            for j in range(num_pairs):
13                # If the mentor j has not been visited, mark as visited and explore further
14                if not visited[j]:
15                    visited[j] = True
16                    dfs(index + 1, total_score + compatibility[index][j])
17                    visited[j] = False  # Backtrack: unmark mentor j, try a new pairing
18
19        # Calculate the number of pairs (students or mentors)
20        num_pairs = len(students)
21        # Initialize the compatibility matrix
22        compatibility = [[0] * num_pairs for _ in range(num_pairs)]
23
24        # Calculate compatibility scores for each student-mentor pair
25        for i in range(num_pairs):
26            for j in range(num_pairs):
27                # Compatibility score is the sum of point-wise similarities
28                compatibility[i][j] = sum(x == y for x, y in zip(students[i], mentors[j]))
29
30        # Initialize the visited array to keep track of assigned mentors
31        visited = [False] * num_pairs
32        # Initialize the maximum compatibility score
33        max_score = 0
34        # Start the depth-first search from the first student (index 0) with an initial score of 0
35        dfs(0, 0)
36
37        # Return the maximum compatibility score found
38        return max_score
39
40# Example use case
41# Instantiate the Solution class
42solution = Solution()
43
44# Given students' answers and mentors' answers
45students = [[1, 1, 0], [1, 0, 1], [0, 0, 1]]
46mentors = [[1, 0, 0], [0, 0, 1], [1, 1, 0]]
47
48# Calculate the maximum compatibility score
49result = solution.maxCompatibilitySum(students, mentors)
50# Output the result
51print(result)  # Should output the maximum score based on the given inputs
52
1class Solution {
2    private int[][] compatibilityMatrix; // stores compatibility scores between students and mentors
3    private boolean[] visited; // keeps track of mentors already paired
4    private int numPairs; // number of student-mentor pairs
5    private int maxCompatibilityScore; // stores the max compatibility sum during DFS
6
7    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
8        numPairs = students.length;
9        compatibilityMatrix = new int[numPairs][numPairs];
10        visited = new boolean[numPairs];
11      
12        // Calculate compatibility score for each student-mentor pair
13        for (int studentIndex = 0; studentIndex < numPairs; ++studentIndex) {
14            for (int mentorIndex = 0; mentorIndex < numPairs; ++mentorIndex) {
15                int score = 0;
16                for (int questionIndex = 0; questionIndex < students[studentIndex].length; ++questionIndex) {
17                    if (students[studentIndex][questionIndex] == mentors[mentorIndex][questionIndex]) {
18                        score += 1;
19                    }
20                }
21                compatibilityMatrix[studentIndex][mentorIndex] = score;
22            }
23        }
24
25        // Start Depth-First Search to find the max compatibility score
26        dfs(0, 0);
27        return maxCompatibilityScore;
28    }
29
30    private void dfs(int studentIndex, int currentScore) {
31        // If all students are paired, update the maximum compatibility score
32        if (studentIndex == numPairs) {
33            maxCompatibilityScore = Math.max(maxCompatibilityScore, currentScore);
34            return;
35        }
36
37        // Try pairing the current student with each mentor
38        for (int mentorIndex = 0; mentorIndex < numPairs; ++mentorIndex) {
39            if (!visited[mentorIndex]) { // ensure the mentor is not already paired
40                visited[mentorIndex] = true;
41                // Recursively pair the next student, adding the current pair's score
42                dfs(studentIndex + 1, currentScore + compatibilityMatrix[studentIndex][mentorIndex]);
43                // Backtrack: unvisit the current mentor and try another pairing
44                visited[mentorIndex] = false;
45            }
46        }
47    }
48}
49
1#include <vector>
2#include <cstring>
3#include <algorithm>
4#include <functional>
5
6class Solution {
7public:
8    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
9        int numStudents = students.size();
10        int numQuestions = students[0].size();
11      
12        // g will store the compatibility scores between students and mentors
13        int compatibility[numStudents][numStudents];
14        memset(compatibility, 0, sizeof compatibility);
15      
16        // visited array to keep track of which mentors have been paired
17        bool visited[numStudents];
18        memset(visited, 0, sizeof visited);
19      
20        // Calculate compatibility score for each student-mentor pair
21        for (int i = 0; i < numStudents; ++i) {
22            for (int j = 0; j < numStudents; ++j) {
23                for (int k = 0; k < numQuestions; ++k) {
24                    compatibility[i][j] += (students[i][k] == mentors[j][k]);
25                }
26            }
27        }
28      
29        // Initialize the variable to store the maximum compatibility sum
30        int maxSum = 0;
31      
32        // Recursive Depth-First Search function to try all possible pairings
33        function<void(int, int)> dfs = [&](int studentIndex, int currentSum) {
34            // If all students have been paired, update the maxSum if necessary
35            if (studentIndex == numStudents) {
36                maxSum = max(maxSum, currentSum);
37                return;
38            }
39          
40            // Try pairing current student with each mentor
41            for (int mentorIndex = 0; mentorIndex < numStudents; ++mentorIndex) {
42                if (!visited[mentorIndex]) {
43                    visited[mentorIndex] = true;
44                    dfs(studentIndex + 1, currentSum + compatibility[studentIndex][mentorIndex]);
45                    visited[mentorIndex] = false;
46                }
47            }
48        };
49      
50        // Start DFS from the first student
51        dfs(0, 0);
52      
53        // Return the maximum compatibility sum found
54        return maxSum;
55    }
56};
57
1// Import statements are not necessary in an algorithmic context such as LeetCode
2// where the runtime environment is preset.
3
4// You also wouldn't typically have global variables in a TypeScript/JavaScript
5// submission on LeetCode; instead, they'd be scoped to the function. However,
6// following your instructions, they are kept global.
7
8// Define the compatibility array to store scores between students and mentors.
9let compatibility: number[][];
10
11// Boolean array to keep track of which mentors have been paired.
12let visited: boolean[];
13
14// Function to calculate the maximum compatibility sum.
15function maxCompatibilitySum(students: number[][], mentors: number[][]): number {
16    let numStudents = students.length;
17    let numQuestions = students[0].length;
18    compatibility = Array.from({ length: numStudents }, () => new Array(numStudents).fill(0));
19    visited = new Array(numStudents).fill(false);
20
21    // Calculate compatibility score for each student-mentor pair.
22    for (let i = 0; i < numStudents; ++i) {
23        for (let j = 0; j < numStudents; ++j) {
24            for (let k = 0; k < numQuestions; ++k) {
25                if (students[i][k] === mentors[j][k]) {
26                    compatibility[i][j]++;
27                }
28            }
29        }
30    }
31
32    // Initialize the variable to store the maximum compatibility sum.
33    let maxSum = 0;
34
35    // Recursive function to try all possible pairings using Depth-First Search approach.
36    const dfs = (studentIndex: number, currentSum: number) => {
37        // If all students have been paired, update the maxSum if the current sum is greater.
38        if (studentIndex === numStudents) {
39            maxSum = Math.max(maxSum, currentSum);
40            return;
41        }
42
43        // Try pairing current student with each mentor.
44        for (let mentorIndex = 0; mentorIndex < numStudents; ++mentorIndex) {
45            if (!visited[mentorIndex]) {
46                visited[mentorIndex] = true;
47                dfs(studentIndex + 1, currentSum + compatibility[studentIndex][mentorIndex]);
48                visited[mentorIndex] = false; // Backtrack to try other pairings.
49            }
50        }
51    };
52
53    // Start the search from the first student.
54    dfs(0, 0);
55
56    // Return the maximum compatibility sum found.
57    return maxSum;
58}
59
60// Note: Since TypeScript is often transpiled to JavaScript before execution,
61// it doesn't typically have direct access to memory management and may not use
62// pointers in the same way as C++. For this reason, things like `memset` are not
63// necessary or availableโ€”arrays can be filled using built-in methods.
64// Additionally, TypeScript is strongly typed, so each variable and function
65// parameter needs a type annotation, which ensures type safety.
66
Not Sure What to Study? Take the 2-min Quiz๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed by examining the following parts:

  1. The compatibility matrix computation (g): For each pair of student and mentor, we calculate the compatibility score which takes O(n) time where n is the number of questions, since we are comparing their answers question-by-question. As there are m students and m mentors, we perform this operation m^2 times. Thus, the time complexity for creating this matrix is O(m^2 * n).

  2. The depth-first search (dfs) with backtracking: The dfs function explores all possible pairings between students and mentors. In the worst case, it has to explore m! (factorial of m) different configurations (each student can be matched with any of the m mentors, the next student with any of the m-1 remaining mentors, and so forth). For each recursive call, we also calculate the total compatibility score t + g[i][j], which is done in O(1) time. Therefore, the total time complexity for this part is O(m!).

Taking both parts into account, the overall time complexity is O(m^2 * n + m!).

Space Complexity

The space complexity of the code is dominated by the following components:

  1. The compatibility matrix (g): This matrix is of size m x m, resulting in O(m^2) space.

  2. The visited array (vis): An array keeping track of which mentors have been visited. This requires O(m) space.

  3. The recursion call stack for dfs: In the worst case, the depth of the recursion is m (matching each student with a mentor), therefore, the recursive call stack will require O(m) space.

Since the space for the compatibility matrix is the largest component, the overall space complexity is O(m^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Bitmask Introduction

Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ