Skip to main content
Talentd

Select Cells in Grid With Maximum Score - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationMatrix18 min read
Practice this problem

Problem Statement

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:

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 <= 10
  • 1 <= grid[i][j] <= 100

Approach Overview

Problem 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.

Approach 1: Greedy + Sorting Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Backtracking Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 2n) as all combinations are explored.
Space Complexity: O(n + m) for the recursive call stack and used array.

Try this approach in the editor →

Approach 3: State Compression Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m) for storing row values during comparisons.

Backtracking Approach

Time Complexity: O(n * 2n) as all combinations are explored.
Space Complexity: O(n + m) for the recursive call stack and used array.

State Compression Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Row TrackingO(V * 2^R)O(R)Good for understanding the search space or when constraints are very small
Greedy Ordering + Bitmask DPO(V * 2^R * R)O(2^R)Best general solution when rows ≤10 and value grouping is possible

Video Solution

3276 Select Cells in Grid With Maximum Score || How to 🤔 in Interview || Unique || Memo + Bitmasking • Ayush Rao • 3,005 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Select Cells in Grid With Maximum Score easy or hard?
Select Cells in Grid With Maximum Score is classified as a Hard problem. The difficulty comes from recognizing that the row count is small enough for bitmask state compression and restructuring the problem from cell-level choices to value-based dynamic programming.
How to solve Select Cells in Grid With Maximum Score in O(V * 2^R)?
Compress row usage into a bitmask and iterate values sequentially. For each DP mask, attempt to place the current value into any row that contains that value and is not already used in the mask. Updating masks with bit operations avoids exploring redundant combinations and reduces the search space dramatically compared to naive recursion.
What is the best approach for Select Cells in Grid With Maximum Score?
The most efficient approach uses bitmask dynamic programming over rows. Group grid positions by value, then maintain a DP state where each bitmask represents which rows are already used. For each value, try assigning it to a row that contains it and is not set in the mask. This runs in O(V * 2^R * R) time and O(2^R) space, which works well because the number of rows is small.
Is Select Cells in Grid With Maximum Score asked at Google/Amazon/Meta?
Problems combining bitmask dynamic programming and grid selection patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require selecting elements under row or column constraints with state compression are especially common in senior-level algorithm interviews.
What data structure is used in Select Cells in Grid With Maximum Score?
The solution relies on arrays or hash maps to group rows by value, along with a bitmask to represent which rows are already used. Dynamic programming over these bitmask states is the main technique, supported by bit manipulation operations to update row usage efficiently.
What is the time complexity of Select Cells in Grid With Maximum Score?
The optimal bitmask DP solution runs in O(V * 2^R * R) time, where V is the number of distinct values and R is the number of rows. Each DP state represents a subset of rows, and transitions attempt to place the current value in available rows. Space complexity is O(2^R) for storing DP states.
Select Cells in Grid With Maximum Score Python or Java solution approach?
Both Python and Java implementations typically build a map from value to list of rows, then run bitmask dynamic programming. A DP array of size 2^rows stores the best score for each row combination, and transitions update masks using bit operations. The logic is identical across languages with minor syntax differences.

Ready to solve this problem?

Practice Select Cells in Grid With Maximum Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays