Select Cells in Grid With Maximum Score - Video Solutions

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.