# Select Cells in Grid With Maximum Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/select-cells-in-grid-with-maximum-score)
Canonical: https://scaleengineer.com/dsa/problems/select-cells-in-grid-with-maximum-score
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, Matrix
---
## Problem
You are given a 2D matrix `grid` consisting of positive integers.

You have to select _one or more_ cells from the matrix such that the following conditions are satisfied:

* No two selected cells are in the **same** row of the matrix.
* The values in the set of selected cells are **unique**.

Your score will be the **sum** of the values of the selected cells.

Return the **maximum** score you can achieve.

**Example 1:**

**Input:** grid = \[\[1,2,3\],\[4,3,2\],\[1,1,1\]\]

**Output:** 8

**Explanation:**

![](https://assets.glich.co/dsa/select-cells-in-grid-with-maximum-score/image0.png)

We can select the cells with values 1, 3, and 4 that are colored above.

**Example 2:**

**Input:** grid = \[\[8,7,6\],\[8,3,2\]\]

**Output:** 15

**Explanation:**

![](https://assets.glich.co/dsa/select-cells-in-grid-with-maximum-score/image1.png)

We can select the cells with values 7 and 8 that are colored above.

**Constraints:**

* `1 <= grid.length, grid[i].length <= 10`
* `1 <= grid[i][j] <= 100`

# Approaches
## Brute-Force Backtracking
This approach uses a classic recursive backtracking technique. It explores every possible valid combination of cell selections by making a decision for each row: either to skip it or to pick one of its cells. The validity of a selection is checked by ensuring the chosen cell's value is unique among all previously selected cells.
**Time:** O((n+1)^m), where `m` is the number of rows and `n` is the number of columns. For each of the `m` rows, we explore `n` options for selecting a cell plus one option for skipping the row. This leads to a recursion tree with approximately `(n+1)^m` nodes, making it infeasible for the given constraints. · **Space:** O(m), where `m` is the number of rows. This space is used for the recursion stack. The `usedValues` set also requires space, but its size is at most `m`.
**Pros:** Conceptually simple and easy to implement.; Correctly explores the entire search space to guarantee the right answer if given enough time.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force backtracking approach systematically explores every valid combination of cells. The core of this method is a recursive function that traverses through the rows of the grid. For each row, it considers two possibilities: either skipping the row entirely or selecting one cell from it. If a cell is selected, its value must not have been chosen from any of the previous rows. This process builds a search tree where each path from the root to a leaf represents a valid selection. The score of each path is calculated, and the maximum score found across all paths is the answer.

```java
class Solution {
    int maxScore = 0;

    public int selectCells(int[][] grid) {
        backtrack(0, 0, new HashSet<>(), grid);
        return maxScore;
    }

    private void backtrack(int rowIndex, int currentScore, Set<Integer> usedValues, int[][] grid) {
        if (rowIndex == grid.length) {
            maxScore = Math.max(maxScore, currentScore);
            return;
        }

        // Option 1: Skip the current row
        backtrack(rowIndex + 1, currentScore, usedValues, grid);

        // Option 2: Pick one cell from the current row
        for (int col = 0; col < grid[rowIndex].length; col++) {
            int value = grid[rowIndex][col];
            if (!usedValues.contains(value)) {
                usedValues.add(value);
                backtrack(rowIndex + 1, currentScore + value, usedValues, grid);
                usedValues.remove(value); // backtrack
            }
        }
    }
}
```
### Algorithm
- Define a recursive function `backtrack(rowIndex, currentScore, usedValues, grid)`.
- The base case for the recursion is when `rowIndex` equals the total number of rows. At this point, update the global maximum score with `currentScore`.
- In the recursive step, for the current `rowIndex`, explore two main branches:
  1. **Skip the row:** Make a recursive call for the next row: `backtrack(rowIndex + 1, currentScore, usedValues, grid)`.
  2. **Select a cell:** Iterate through each column `col` of the current row.
     - Let `value = grid[rowIndex][col]`.
     - If `value` is not present in the `usedValues` set, it's a valid choice.
     - Add `value` to `usedValues`.
     - Make a recursive call for the next row with the updated score and used values: `backtrack(rowIndex + 1, currentScore + value, usedValues, grid)`.
     - After the recursive call returns, remove `value` from `usedValues` to backtrack and explore other possibilities.
- The initial call to start the process is `backtrack(0, 0, new HashSet<>(), grid)`.

## Dynamic Programming on Values with Memoization
A more efficient solution involves changing the perspective of the problem. Instead of making decisions row-by-row, we make decisions for each unique value present in the grid. By processing unique values from largest to smallest, we can decide whether to include a value in our sum and, if so, which available row to take it from. This structure allows for dynamic programming with memoization, drastically reducing redundant computations.
**Time:** O(m*n + U*log(U) + U * 2^m * m), where `m` is rows, `n` is columns, and `U` is the number of unique values. `O(m*n)` is for preprocessing the grid, `O(U*log(U))` for sorting unique values, and `O(U * 2^m * m)` for the DP calculation. Given `m <= 10` and `U <= 100`, this is very efficient. · **Space:** O(U * 2^m + U*m), where `U` is the number of unique values and `m` is the number of rows. The memoization table requires `O(U * 2^m)` space. The `locations` map can take up to `O(U*m)` space in the worst case.
**Pros:** Highly efficient and solves the problem within the given time constraints.; Guarantees the optimal solution by using dynamic programming to avoid re-computation of overlapping subproblems.
**Cons:** More complex to conceptualize and implement compared to simple backtracking.; Requires additional space for the memoization table and preprocessing data structures.
### Explanation
This approach reframes the problem to make it suitable for dynamic programming. The state of our DP is defined by `(k, usedRowsMask)`, where `k` is the index of the unique value we are currently considering, and `usedRowsMask` is a bitmask representing the rows that are already occupied. By iterating through the unique values and for each, deciding whether to use it (and in which available row) or skip it, we can build the solution optimally. Memoization is crucial to store the results of subproblems `(k, usedRowsMask)` to avoid re-calculating them.

```java
class Solution {
    private List<Integer> uniqueValues;
    private Map<Integer, List<Integer>> locations;
    private int[][] memo;
    private int numRows;

    public int selectCells(int[][] grid) {
        numRows = grid.length;
        locations = new HashMap<>();
        Set<Integer> valueSet = new HashSet<>();

        for (int r = 0; r < numRows; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                int val = grid[r][c];
                valueSet.add(val);
                locations.computeIfAbsent(val, k -> new ArrayList<>()).add(r);
            }
        }

        uniqueValues = new ArrayList<>(valueSet);
        Collections.sort(uniqueValues, Collections.reverseOrder());

        memo = new int[uniqueValues.size()][1 << numRows];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return solve(0, 0);
    }

    private int solve(int k, int usedRowsMask) {
        if (k == uniqueValues.size()) {
            return 0;
        }

        if (memo[k][usedRowsMask] != -1) {
            return memo[k][usedRowsMask];
        }

        // Option 1: Skip the current value
        int maxScore = solve(k + 1, usedRowsMask);

        // Option 2: Try to use the current value
        int currentValue = uniqueValues.get(k);
        if (locations.containsKey(currentValue)) {
            for (int row : locations.get(currentValue)) {
                // Check if the row is not used yet
                if ((usedRowsMask & (1 << row)) == 0) {
                    // Use this value in this row
                    maxScore = Math.max(maxScore, currentValue + solve(k + 1, usedRowsMask | (1 << row)));
                }
            }
        }

        return memo[k][usedRowsMask] = maxScore;
    }
}
```
### Algorithm
- **Preprocessing:**
  - Create a map `locations` to store the row indices for each unique value in the grid. For example, `locations.get(v)` will return a list of rows containing the value `v`.
  - Extract all unique values from the grid into a list, `uniqueValues`. Sort this list in descending order. This helps in finding larger scores earlier, though it's not strictly necessary for correctness.
- **DP with Memoization:**
  - Define a recursive function `solve(k, usedRowsMask)` which returns the maximum score obtainable from considering values `uniqueValues[k:]`, given that the rows indicated by `usedRowsMask` are already occupied.
  - `k` is the index of the current value being considered from the `uniqueValues` list.
  - `usedRowsMask` is a bitmask where the `i`-th bit is 1 if a cell has already been selected from row `i`.
  - Use a 2D array `memo[k][usedRowsMask]` to store and retrieve results of subproblems.
- **Base Case:** If `k` equals the number of unique values, we have considered all values, so we return 0.
- **Recursive Step:** For the current value `val = uniqueValues[k]`, calculate the maximum score by considering two choices:
  1. **Skip `val`:** The score is `solve(k + 1, usedRowsMask)`.
  2. **Select `val`:** Iterate through all rows `r` where `val` is located (from the `locations` map). If row `r` is not yet used (i.e., the `r`-th bit in `usedRowsMask` is 0), calculate the score as `val + solve(k + 1, usedRowsMask | (1 << r))`.
- The function returns the maximum score found among all these choices, storing it in the memoization table before returning.
- The initial call is `solve(0, 0)`.

# Solutions
### Java

```java
class Solution {
public
  int maxScore(List<List<Integer>> grid) {
    int m = grid.size();
    int mx = 0;
    boolean[][] g = new boolean[101][m + 1];
    for (int i = 0; i < m; ++i) {
      for (int x : grid.get(i)) {
        g[x][i] = true;
        mx = Math.max(mx, x);
      }
    }
    int[][] f = new int[mx + 1][1 << m];
    for (int i = 1; i <= mx; ++i) {
      for (int j = 0; j < 1 << m; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k = 0; k < m; ++k) {
          if (g[i][k] && (j >> k & 1) == 1) {
            f[i][j] = Math.max(f[i][j], f[i - 1][j ^ 1 << k] + i);
          }
        }
      }
    }
    return f[mx][(1 << m) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScore(vector<vector<int>> &grid) {
    int m = grid.size();
    int mx = 0;
    bool g[101][11]{};
    for (int i = 0; i < m; ++i) {
      for (int x : grid[i]) {
        g[x][i] = true;
        mx = max(mx, x);
      }
    }
    int f[mx + 1][1 << m];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= mx; ++i) {
      for (int j = 0; j < 1 << m; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k = 0; k < m; ++k) {
          if (g[i][k] && (j >> k & 1) == 1) {
            f[i][j] = max(f[i][j], f[i - 1][j ^ 1 << k] + i);
          }
        }
      }
    }
    return f[mx][(1 << m) - 1];
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, grid: List[List[int]]) -> int: g = defaultdict(set) mx = 0 for i, row in enumerate(grid): for x in row: g[x]. add(i) mx = max(mx, x) m = len(grid) f = [[0] * (1 << m) for _ in range(mx + 1)] for i in range(1, mx + 1): for j in range(1 << m): f[i][j] = f[i - 1][j] for k in g[i]: if j >> k & 1: f[i][j] = max(f[i][j], f[i - 1][j ^ 1 << k] + i) return f[- 1][- 1]

```