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:
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:
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:
We can select the cells with values 7 and 8 that are colored above.
Constraints:
1 <= grid.length, grid[i].length <= 101 <= grid[i][j] <= 100Problem Overview: Given a grid of integers, pick cells to maximize the total score while respecting two constraints: you can select at most one cell from each row and you cannot select two cells with the same value. The challenge is coordinating row usage and value uniqueness across the entire grid.
Approach 1: Backtracking with Row Tracking (Exponential)
This method explores every valid combination of selections. First group all cells by their value so decisions are processed value by value. For each value, try selecting one of its candidate rows if that row is still unused, or skip the value entirely. Maintain a set or bitmask of used rows while recursively exploring the search space. The recursion effectively branches on choose a row or skip for each value. Time complexity is O(V * 2^R) in the worst case where V is the number of distinct values and R is the number of rows, with O(R) recursion space. This approach is straightforward but becomes slow when many rows share the same values.
Approach 2: Greedy Ordering + Bitmask Dynamic Programming (Optimal)
A more efficient strategy treats rows as a bitmask state and processes values in increasing or decreasing order. First build a mapping from each value to the rows where it appears. Then run dynamic programming where the state dp[mask] represents the best score achievable using the set of rows encoded in mask. For each value, iterate through existing masks and attempt to assign that value to any row containing it that is not already used in the mask. Update the new mask using bit operations such as mask | (1 << row). The row mask ensures the "one cell per row" constraint, while iterating values guarantees each value is used at most once. Because rows are typically ≤10, the number of states is small (2^R). Time complexity is O(V * 2^R * R) and space complexity is O(2^R). This technique heavily relies on bit manipulation to encode row usage efficiently.
Grids are naturally modeled using a matrix, but the key transformation is switching from cell-level decisions to value-level decisions combined with row bitmasks. That shift drastically reduces the search space.
Recommended for interviews: The bitmask dynamic programming approach is the expected solution. Interviewers want to see recognition that the number of rows is small enough for 2^R state compression. Explaining the brute-force backtracking first demonstrates understanding of the constraints, while transitioning to bitmask DP shows optimization skills and familiarity with state compression techniques.
This method involves treating each row independently and sorting the values in descending order to get the largest possible set without duplicates across rows.
In this solution, we sort each row to access the largest non-repeating element by traversing the matrix row by row and using sorting. We use a hash table to ensure values are unique. The process iterates over each row and sorts it to choose the largest unchosen value for summing up the maximum score.
Time Complexity: O(n * m log m) where n is the number of rows and m is the number of columns due to sorting.
Space Complexity: O(m) for storing row values during comparisons.
This approach involves exploring each row with potential cell selections using backtracking, carefully avoiding selected rows and ensuring unique values to maximize the score cumulatively.
This backtracking solution tries each valid placement per row while leveraging a recursive strategy. It iteratively considers row positions and links viable selections avoiding duplicates using a boolean array.
It may not be optimal for larger constraints.
Time Complexity: O(n * 2n) as all combinations are explored.
Space Complexity: O(n + m) for the recursive call stack and used array.
We define f[i][j] to represent the maximum score when selecting numbers from [1,..i] and the state of the rows corresponding to the selected numbers is j. Initially, f[i][j] = 0, and the answer is f[mx][2^m - 1], where mx represents the maximum value in the matrix, and m represents the number of rows in the matrix.
First, we preprocess the matrix using a hash table g to record the set of rows corresponding to each number. Then, we can use state compression dynamic programming to solve the problem.
For the state f[i][j], we can choose not to select the number i, in which case f[i][j] = f[i-1][j]. Alternatively, we can choose the number i. In this case, we need to enumerate each row k in the set g[i] corresponding to the number i. If the k-th bit of j is 1, it means we can select the number i. Thus, f[i][j] = max(f[i][j], f[i-1][j \oplus 2^k] + i).
Finally, we return f[mx][2^m - 1].
The time complexity is O(m times 2^m times mx), and the space complexity is O(mx times 2^m). Here, m is the number of rows in the matrix, and mx is the maximum value in the matrix.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy + Sorting Approach | Time Complexity: O(n * m log m) where n is the number of rows and m is the number of columns due to sorting. |
| Backtracking Approach | Time Complexity: O(n * 2n) as all combinations are explored. |
| State Compression Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Row Tracking | O(V * 2^R) | O(R) | Good for understanding the search space or when constraints are very small |
| Greedy Ordering + Bitmask DP | O(V * 2^R * R) | O(2^R) | Best general solution when rows ≤10 and value grouping is possible |
3276 Select Cells in Grid With Maximum Score || How to 🤔 in Interview || Unique || Memo + Bitmasking • Ayush Rao • 2,972 views views
Watch 9 more video solutions →Practice Select Cells in Grid With Maximum Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor