Miguel Gargallo 3276. Select Cells in Grid With Maximum Score
IntuitionWe want to pick exactly one value from some (or all) rows in such a way that:
No two selected cells come from the same row.
All selected values are dis
# Intuition

We want to pick exactly one value from some (or all) rows in such a way that:  
1. No two selected cells come from the same row.  
2. All selected values are distinct.  
3. The sum of these values is maximized.  

Since every number in the grid is a positive integer, and we can have at most 10 rows, our problem essentially boils down to finding a maximum matching between rows and distinct values, prioritizing larger values first.  

Why does matching in descending order of the values work?  
- If a row is currently matched with a smaller value, but a bigger value can only fit into that same row, we can attempt to “re-match” the smaller value to another row (if possible), thereby ensuring a strictly larger total sum. This is the standard **augmenting path** logic in bipartite matching, but we greedily process edges (row–value pairs) starting with the largest value first.

---

## Approach

1. **Collect distinct values**  
   - Extract all the distinct values from the grid.  
   - Map each value to the rows in which it appears, i.e., for each distinct value \(v\), keep a list of row indices that contain \(v\).

2. **Sort values in descending order**  
   - Since we want to maximize the sum, we begin with the largest value and attempt to match it to a row.

3. **Greedy matching with augmenting paths**  
   - Initialize an array `rowMatch` of size `R` (number of rows) with `-1`, signifying that initially no row is matched to any value.  
   - For each distinct value (processed from largest to smallest):  
     1. Create a `visited` array of booleans (size `R`) to mark rows visited in the current attempt.  
     2. Run a DFS `canMatch(valueIdx, visited)` trying to match this value to one of its possible rows.  
        - If a row is free (`rowMatch[row] == -1`), match the value immediately.  
        - Otherwise, if the row is taken by a smaller value, attempt to re-match that smaller value to a different row (recursively).  
        - If re-matching is successful, assign the current (larger) value to this row.  
   - This step ensures we always displace smaller values with bigger ones whenever feasible.

4. **Compute the maximum score**  
   - After processing all values, simply sum up the matched values using the information in `rowMatch`.  
   - That sum is our maximum score.

Because we are always trying to match larger values first and we only re-match when it strictly increases the overall sum, we end up with the optimal configuration of row–value pairs.

---

## Time Complexity
- Let \(R\) be the number of rows (up to 10) and let \(C\) be the number of columns (up to 10).  
- In the worst case, the grid has up to 100 distinct values.  
- For each of the at most 100 values, we perform a DFS over at most 10 rows. A DFS might re-match other values, but each row is visited at most once per DFS call.  
- Overall, the matching step is \(O(\text{(number of distinct values)} \times R \times R)\) = \(O(100 \times 10 \times 10) = O(10\,000)\).  

Hence, the **time complexity** is \(O(R^2 \times \text{(number of distinct values)})\), comfortably efficient for \(R \leq 10\) and \(\text{(number of distinct values)} \leq 100\).

---

## Space Complexity
- We store up to 100 distinct values and, for each value, a list of rows (each row up to 10).  
- We also keep a `rowMatch` array and auxiliary data structures (like `visited`) for the DFS.  
- Overall, the **space complexity** is \(O(R + \text{(number of distinct values)})\), which is \(O(10 + 100)\) in the worst case, i.e., \(O(1)\) in the context of these small constraints.

# Code
```python []
class Solution(object):
    def maxScore(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 1) Gather distinct values and which rows they appear in
        from collections import defaultdict
        
        row_count = len(grid)
        col_count = len(grid[0])
        
        value_to_rows = defaultdict(list)
        distinct_values = set()
        
        for r in range(row_count):
            for c in range(col_count):
                val = grid[r][c]
                distinct_values.add(val)
                value_to_rows[val].append(r)
        
        # Convert set to a list and sort in descending order
        distinct_values = sorted(list(distinct_values), reverse=True)
        
        # rowMatch[r] = index in distinct_values that row r is matched to, or -1 if unmatched
        rowMatch = [-1] * row_count
        
        # 2) DFS function to attempt matching 'valueIdx' with a row
        def canMatch(valueIdx, visited):
            # For every row that can contain this value
            for row in value_to_rows[distinct_values[valueIdx]]:
                if not visited[row]:
                    visited[row] = True
                    # If row is free or we can re-match the currently matched value
                    if rowMatch[row] == -1 or canMatch(rowMatch[row], visited):
                        rowMatch[row] = valueIdx
                        return True
            return False
        
        # 3) Try to match each value (descending order) with a suitable row
        for vIdx in range(len(distinct_values)):
            visited = [False] * row_count
            canMatch(vIdx, visited)
        
        # 4) Calculate the sum of matched values
        score = 0
        for r in range(row_count):
            if rowMatch[r] != -1:
                score += distinct_values[rowMatch[r]]
        
        return score

```
['Python']