LeetCode 1947: Maximum Compatibility Score Sum Solution

Master LeetCode problem 1947 (Maximum Compatibility Score Sum), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1947. Maximum Compatibility Score Sum

Medium

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

Problem Explanation

Explanation

To solve this problem, we can use backtracking with memoization. We will iterate through all possible pairings of students and mentors and calculate the compatibility score for each pairing. We will keep track of the maximum compatibility score sum that can be achieved.

Here are the steps:

Define a recursive function that takes the current student index, a bitmask representing the mentors already paired with students, and a memoization array to store the maximum compatibility score sum for each state.
In the recursive function, iterate through all mentors and check if the current mentor is already paired. If not, calculate the compatibility score for the current student-mentor pairing and recursively call the function for the next student.
Update the memoization array with the maximum compatibility score sum for the current state.
Return the maximum compatibility score sum.

Time Complexity: O(m * 2^n), where m is the number of students and n is the number of questions. Space Complexity: O(m * 2^n) for memoization.

Solution Code

class Solution {
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int n = students.length;
        int[] memo = new int[1 << n];
        return backtrack(0, 0, students, mentors, memo);
    }

    private int backtrack(int studentIdx, int mask, int[][] students, int[][] mentors, int[] memo) {
        if (studentIdx == students.length) return 0;
        if (memo[mask] != 0) return memo[mask];

        int maxScore = 0;
        for (int i = 0; i < students.length; i++) {
            if ((mask & (1 << i)) == 0) {
                int score = calculateScore(students[studentIdx], mentors[i]);
                maxScore = Math.max(maxScore, score + backtrack(studentIdx + 1, mask | (1 << i), students, mentors, memo));
            }
        }

        memo[mask] = maxScore;
        return maxScore;
    }

    private int calculateScore(int[] student, int[] mentor) {
        int score = 0;
        for (int i = 0; i < student.length; i++) {
            if (student[i] == mentor[i]) {
                score++;
            }
        }
        return score;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1947 (Maximum Compatibility Score Sum)?

This page provides optimized solutions for LeetCode problem 1947 (Maximum Compatibility Score Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1947 (Maximum Compatibility Score Sum)?

The time complexity for LeetCode 1947 (Maximum Compatibility Score Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1947 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1947 in Java, C++, or Python.

Back to LeetCode Solutions