Python | Java DFS in descending orders with detailed explanation.
\n# Intuition\nThere are two constraints to consider:\n- Each row can only contain one value.\n- All values must be unique.\n\nThese constraints imply that, whe
\n# Intuition\nThere are two constraints to consider:\n- Each row can only contain one value.\n- All values must be unique.\n\nThese constraints imply that, when aiming to maximize the values in all cells, the largest value in the grid must be included. This is because, for any set of values chosen from the grid that excludes the maximum value, substituting one selected value by the maximum value in the same row will not violate the constraints and will result in a higher score.\n\nGiven this, it makes sense to adopt a strategy that selects values from the grid in descending order. Thus, a DFS approach comes to mind.\n\n\n# Approach\nThere are 3 steps to follow:\n\n- Create a mapping from each unique value in the grid to the indexes of the rows containing that value.\n- Execute a DFS algorithm for each unique value in descending order.\n- For each value, iterate through the list of row indexes and determine the maximum score. During this process, keep track of rows that have already been selected, and ensure to skip these rows to adhere to the restriction of having only one value per row.\n\n# Code\n```python []\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        rows = len(grid)\n        cols = len(grid[0])\n        # flatten all the values in the grid and deduplicate\n        value_set = set([grid[r][c] for r in range(rows) for c in range(cols)])\n        \n        # sort values from in descending order\n        value_list = sorted(list(value_set))[::-1]\n\n        # create a map mapping from each value to the list of row indexes with these values\n        val_to_rows = defaultdict(list)\n        for value in value_list:\n            val_to_rows[value] = [r for r in range(rows) if value in grid[r]]\n\n        # Run dfs on rows with cell values in descending order.\n        def dfs(row_set, remaining_values, score):\n            if not remaining_values:\n                return score\n\n            value = remaining_values[0]\n            remaining_values = remaining_values[1:]\n\n            score_list = []\n\n            for row in val_to_rows[value]:\n                if row not in row_set:\n                    score_list.append(dfs(row_set | {row}, remaining_values, score + value))\n            if not score_list:\n                score_list.append(dfs(row_set, remaining_values, score))\n            return max(score_list)\n\n        return dfs(set(), value_list, 0)\n        \n```\n\n\n```java []\nclass Solution {\n    private int dfs(\n        final Set<Integer> rows, \n        final List<Integer> sortedVals,\n        final Map<Integer, Set<Integer>> valToIndex,\n        final int score,\n        int depth\n    ) {\n        if (++depth == sortedVals.size()) {\n            return score;\n        }\n        final int value = sortedVals.get(depth);\n        \n        final List<Integer> scores = new ArrayList<>();\n        final int nxt_depth = depth;\n        valToIndex.get(value)\n                  .stream()\n                  .filter(row -> !rows.contains(row))\n                  .forEach(row -> {\n            final Set<Integer> updatedRows = new HashSet<>(rows);\n            updatedRows.add(row);\n            scores.add(dfs(updatedRows, sortedVals, valToIndex, score + value, nxt_depth));\n        });\n        if (scores.isEmpty()) {\n            return dfs(rows, sortedVals, valToIndex, score, depth);\n        } else {\n           return Collections.max(scores);\n        }\n    }\n\n    public int maxScore(List<List<Integer>> grid) {\n        final Set<Integer> vals =  grid.stream().flatMap(List::stream).collect(Collectors.toSet());\n        final Map<Integer, Set<Integer>> valToIndex = new HashMap<>();\n        vals.forEach(val -> valToIndex.put(val, new HashSet<>()));\n        IntStream.range(0, grid.size()).forEach(row -> {\n            vals.forEach(val -> {\n                if (grid.get(row).contains(val)) {\n                    valToIndex.get(val).add(row);\n                }\n            });\n        });\n        final List<Integer> sortedVals = new ArrayList<>(vals);\n        Collections.sort(sortedVals, Collections.reverseOrder());\n        return dfs(new HashSet<>(), sortedVals, valToIndex, 0, -1);\n    }\n}\n```
['Depth-First Search', 'Java', 'Python3']