Unique Maximum Values with Memoization
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:\n1. Arrange all the unique numbers in descending order\n2. Map which row they belong to\n3. Condense each row to a descending set\n4. Starting from the greatest number, find if it is unique to a bucket\n5. If it is, select it and mark the row as done\n6. If not, then branch out to the number of buckets it is present in\n7. Use memoization to avoid recomputing repeat cases\n\n# Complexity\n- Time complexity: O(m * n log n + m * 2^m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m * n + m * 2^m)\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    TreeMap<Integer, List<Set<Integer>>> intMap = new TreeMap<>(Comparator.reverseOrder());\n\n    public int maxScore(List<List<Integer>> grid) {\n        Map<Set<Integer>, Boolean> candidates = new IdentityHashMap<>();\n        for (List<Integer> integers : grid) {\n            Set<Integer> set = new TreeSet<>(Comparator.reverseOrder());\n            set.addAll(integers);\n            for (int j : set) {\n                intMap.computeIfAbsent(j, k -> new ArrayList<>()).add(set);\n            }\n            candidates.put(set, Boolean.TRUE);\n        }\n        return computeMax(0, intMap.firstEntry(), candidates);\n    }\n\n    private int computeMax(int max, Map.Entry<Integer, List<Set<Integer>>> target, Map<Set<Integer>, Boolean> candidates) {\n        if (candidates.isEmpty() || target == null) return max;\n        Long memoKey = computeMemoKey(candidates, max, target.getKey());\n        if (memo.containsKey(memoKey)) return memo.get(memoKey);\n        int newMax = max;\n        boolean isUtilized = false;\n        for (Set<Integer> set : target.getValue()) {\n            if (!candidates.containsKey(set)) continue;\n            candidates.remove(set);\n            newMax = Math.max(newMax, computeMax(max + target.getKey(), intMap.higherEntry(target.getKey()), candidates));\n            candidates.put(set, Boolean.TRUE);\n            isUtilized = true;\n        }\n        if (!isUtilized) newMax = Math.max(newMax, computeMax(max, intMap.higherEntry(target.getKey()), candidates));\n        memo.put(memoKey, newMax);\n        return newMax;\n    }\n\n    private long computeMemoKey(Map<Set<Integer>, Boolean> candidates, int max, int targetKey) {\n        long hash = 0L;\n        for (Set<Integer> set : candidates.keySet()) {\n            hash += System.identityHashCode(set);\n        }\n        return (hash << 32) | ((long) targetKey << 24) | (max);\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/f0a9b676-852f-49fd-be44-c4fd7d86b7c7_1725799693.0301301.png)\n
['Java']