Blazing Fast 🔥 5ms | Beats 100% | Rundown + Bitmask + Memo
Intuition\n Describe your first thoughts on how to solve this problem. \nThe most straightforward approach, i.e. backtracking can quickly get very expensive for
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe most straightforward approach, i.e. **backtracking** can quickly get very expensive for some cases, hence this is one of those cases where you have to look at the data constraints.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere are the steps to solve this particular problem:\n\n1. Arrange all the unique numbers in descending order\n2. Map which row they belong to by **bitmasking**\n3. Starting from the greatest number, find if it is unique to a bucket\n4. If it is, select it and mark the row as done\n5. If not, then branch out to the number of buckets it is present in\n6. Use memoization to avoid recomputing repeat cases\n\n# Complexity\n- Time complexity: O(n * 2^n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2^n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    Map<Long, Integer> memo = new HashMap<>();\n    int[] intMap = new int[101];\n    int[] intPos = new int[101];\n\n    public int maxScore(List<List<Integer>> grid) {\n        int candidates = 0;\n        for (int i = 0; i < grid.size(); i++) {\n            List<Integer> integers = grid.get(i);\n            int mask = 1 << i;\n            for (int j : integers) {\n                intMap[j] |= mask;\n            }\n            candidates |= mask;\n        }\n        int lastId = 0;\n        for (int i = 0; i < 101; i++) {\n            if (intMap[i] == 0) continue;\n            intPos[i] = lastId;\n            lastId = i;\n        }\n        return computeMax(0, lastId, candidates);\n    }\n\n    private int computeMax(int max, int target, int candidates) {\n        if (candidates == 0 || target == 0) return max;\n        Long memoKey = computeMemoKey(candidates, max, target);\n        if (memo.containsKey(memoKey)) return memo.get(memoKey);\n        int newMax = max;\n        int v = intMap[target];\n        int curMax = max + target;\n        for (int mask = v & candidates; mask > 0; mask &= mask - 1) {\n            int newCandidates = candidates ^ (mask & -mask);\n            newMax = Math.max(newMax, computeMax(curMax, intPos[target], newCandidates));\n        }\n        if (newMax == max)\n            newMax = Math.max(newMax, computeMax(max, intPos[target], candidates));\n        memo.put(memoKey, newMax);\n        return newMax;\n    }\n\n    private long computeMemoKey(int candidates, int max, int targetKey) {\n        return ((long) candidates << 32) | ((long) targetKey << 24) | (max);\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/ec6f1f8b-eecc-4911-9755-b843a47a808e_1725799734.5978045.png)\n
['Java']