✅easiest-soln | Goldman Sachs🔥| well-explained👁️
If you found my answer helpful, please consider giving it an upvote\uD83D\uDE0A\nReviseWithArsh #6Companies30Days Challenge 2023\nChallenge Company 2 : Goldman 
## If you found my answer helpful, please consider giving it an upvote\uD83D\uDE0A\n**ReviseWithArsh #6Companies30Days Challenge 2023\nChallenge Company 2 : Goldman Sachs\nQ15. Maximum Good People Based on Statements**\n\n![15.jpg](https://assets.leetcode.com/users/images/7974e00e-afb6-45be-b1c4-8d4d7902b480_1673453967.692707.jpeg)\n\n\n### Complexity\n- The **time complexity** of this code is O(2^N * N^2) where N is the number of people. The space complexity is O(N).\nThe time complexity of the code is determined by the number of recursive calls that are made. In the worst case, the function will be called for each possible combination of good and bad people, which is 2^N. In each recursive call, the isValid function is called, which takes O(N) time as it needs to check the consistency of each person\'s statement with the current configuration. Therefore, the total time complexity is O(2^N * N^2).\n\n- The **space complexity** is determined by the amount of memory used by the function. The function uses a boolean array goodPeople of length N to store the current configuration of good and bad people, and an integer array maxGoodPeople of length 1 to store the maximum number of good people found so far. Therefore, the space complexity is O(N)\nIt should be noted that this algorithm is very slow for large inputs. There are other methods such as backtracking to solve this problem which have a much better time complexity O(N*2^(N/2))\n\n### Code\n```\nclass Solution {\n    public int maximumGood(int[][] statements) {  \n        // Declare variable to store the max number of good people\n        int[] maxGoodPeople = { 0 };      \n        // Recursive function to find the maximum number of good people\n        maximumGood(statements, new boolean[statements.length], 0, 0, maxGoodPeople);\n        return maxGoodPeople[0];\n    }\n    \n    private void maximumGood(int[][] statements, boolean[] goodPeople, int currentPerson, int currentGoodPeople, int[] maxGoodPeople) {\n        // Base case: if all people have been checked\n        if (currentPerson == goodPeople.length) {\n            // Update maxGoodPeople if necessary\n            maxGoodPeople[0] = Math.max(maxGoodPeople[0], currentGoodPeople);\n            return;\n        }\n        \n        // Set current person as good\n        goodPeople[currentPerson] = true;\n        // If remaining people cannot beat the current max, return\n        if (goodPeople.length - currentPerson + currentGoodPeople < maxGoodPeople[0]) {\n            return;\n        }\n        // If current configuration is valid, move forward\n        if (isValid(statements, goodPeople, currentPerson)) {\n            maximumGood(statements, goodPeople, currentPerson + 1, currentGoodPeople + 1, maxGoodPeople);\n        }\n\n        // Set current person as bad\n        goodPeople[currentPerson] = false; \n        // If remaining people cannot beat the current max, return\n        if (goodPeople.length - currentPerson - 1 + currentGoodPeople < maxGoodPeople[0]) {\n            return;\n        }\n        // If current configuration is valid, move forward\n        if (isValid(statements, goodPeople, currentPerson)) {\n            maximumGood(statements, goodPeople, currentPerson + 1, currentGoodPeople, maxGoodPeople);\n        }\n        \n        return;\n    }\n    \n    // Function to check if the current configuration is valid\n    private boolean isValid(int[][] statements, boolean[] goodPeople, int currentPerson) {\n        // Check if all previous people\'s statements are consistent with current configuration\n        for (int i = 0; i < currentPerson; ++i) {\n            if (goodPeople[i]) {\n                if (goodPeople[currentPerson] && statements[i][currentPerson] == 0) {\n                    return false;\n                }\n                if (!goodPeople[currentPerson] && statements[i][currentPerson] == 1) {\n                    return false;\n                }\n            }\n        }\n        // Check if current person\'s statements are consistent with current configuration\n        if (goodPeople[currentPerson]) {\n            for (int i = 0; i < currentPerson; ++i) {\n                if (goodPeople[i] && statements[currentPerson][i] == 0) return false;\n                if (!goodPeople[i] && statements[currentPerson][i] == 1) return false;\n            }\n        }\n\n        return true;\n    }\n}\n\n```\nThis code is a solution to a problem where given a 2D array of statements, where each statement is a binary value (0 or 1) representing whether a person is good (1) or bad (0), the task is to find the maximum number of good people. The code does this by using a recursive function called maximumGood that explores different configurations of good and bad people and checks the validity of each configuration using the isValid function.\n- maximumGood function: It is a recursive function that takes four parameters, first is the 2D array of statements, second is a boolean array indicating whether a person is good or bad, third is an integer indicating the current person being checked, and fourth is an integer array that stores the maximum number of good people found so far.\n- The function explores different configurations of good and bad people by setting the current person being checked as good or bad, and recursively calling itself with the next person and updated number of good people.\n- isValid function: It is used to check if a given configuration of good and bad people is consistent with the statements in the input 2D array. It returns false if any person\'s statement is not consistent with their good/bad status in the current configuration, and true otherwise.\n- The code makes use of memoization by adding an early return when the remaining people cannot beat the current max, to improve performance.
['Java']