LeetCode 3276 - Select Cells in Grid With Maximum Score

The problem requires us to select cells from a 2D matrix grid such that no two selected cells are in the same row, and all selected values are unique. Our goal is to maximize the sum of these selected values.

leetcodehardarraydynamic-programmingbit-manipulationmatrixbitmask

LeetCode Problem 3276

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Matrix, Bitmask

Solution

Problem Understanding

The problem requires us to select cells from a 2D matrix grid such that no two selected cells are in the same row, and all selected values are unique. Our goal is to maximize the sum of these selected values. In other words, for each row, we can choose at most one value, but across all rows, no value can repeat in our selection.

The input grid is a 2D list of integers where each integer is positive and bounded between 1 and 100. The grid has up to 10 rows and 10 columns. The output is a single integer representing the maximum possible sum of values that meet the constraints.

Constraints tell us that the input size is small (maximum 10x10), which makes solutions with exponential complexity feasible, but we should look for a way to avoid unnecessary recomputation.

Edge cases include rows with identical values, grids with only one row or one column, and grids where every number is the same. These cases may trip up naive approaches if we do not correctly enforce the uniqueness constraint.

Approaches

A brute-force approach would try all possible combinations of selecting one element per row while maintaining uniqueness. For each row, we could recursively try each value, skipping values that are already used. While this guarantees the correct answer, the time complexity is O((m!) * n^m) in the worst case, which is infeasible even for m = 10 and n = 10. Here, m is the number of rows and n is the number of columns.

The key insight for an optimal solution is that we can represent the set of used numbers as a bitmask because values are small (1-100) and the number of unique values is bounded. We can use dynamic programming (DP) with memoization, where the state is (row index, bitmask of used values). For each row, we try selecting each value that has not been used yet, recursively compute the maximum score for the remaining rows, and take the maximum.

This DP approach leverages the small grid size and the bounded value range to avoid recomputation, making it tractable.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^m) O(m) Recursively try all selections with uniqueness check
DP + Bitmask O(m * 2^V * n) O(m * 2^V) Use DP with memoization; V = number of unique values (≤ 100)

Algorithm Walkthrough

  1. Preprocess the grid to identify all unique values. Map each value to a bit position for bitmasking.

  2. Initialize a memoization table dp[row][mask], where row is the current row index, and mask represents which values are already used.

  3. Define a recursive function dfs(row, mask):

  4. If row == m, return 0 since we have processed all rows.

  5. If dp[row][mask] is already computed, return it to avoid recomputation.

  6. Initialize max_score as 0.

  7. For each value in grid[row], check if it is already used in mask. If not, recursively compute dfs(row+1, mask | bit_of_value) and add the current value.

  8. Update max_score if this choice gives a higher score.

  9. Memoize the result for dp[row][mask] and return it.

  10. Start recursion from dfs(0, 0) to compute the maximum possible score.

Why it works: The algorithm maintains the invariant that mask always correctly represents the set of values chosen so far. At each row, we only consider values not yet used, which guarantees uniqueness. Memoization ensures that we do not recompute the same state, which makes the solution efficient.

Python Solution

from typing import List

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # Map each unique value to a bit index
        unique_vals = sorted({v for row in grid for v in row})
        val_to_bit = {v: i for i, v in enumerate(unique_vals)}
        V = len(unique_vals)

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(row: int, mask: int) -> int:
            if row == m:
                return 0
            max_score = 0
            for val in grid[row]:
                bit = val_to_bit[val]
                if not (mask & (1 << bit)):
                    score = val + dfs(row + 1, mask | (1 << bit))
                    max_score = max(max_score, score)
            return max_score

        return dfs(0, 0)

This Python implementation first computes a mapping of unique values to bits for efficient bitmasking. The recursive dfs function explores all valid selections row by row while memoizing results. The maximum score is returned from dfs(0, 0).

Go Solution

func maxScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    valSet := make(map[int]int)
    for _, row := range grid {
        for _, v := range row {
            valSet[v] = 0
        }
    }

    vals := make([]int, 0, len(valSet))
    for v := range valSet {
        vals = append(vals, v)
    }
    valToBit := make(map[int]int)
    for i, v := range vals {
        valToBit[v] = i
    }
    V := len(vals)

    memo := make(map[[2]int]int)

    var dfs func(row int, mask int) int
    dfs = func(row int, mask int) int {
        if row == m {
            return 0
        }
        key := [2]int{row, mask}
        if val, ok := memo[key]; ok {
            return val
        }
        maxScore := 0
        for _, v := range grid[row] {
            bit := valToBit[v]
            if mask&(1<<bit) == 0 {
                score := v + dfs(row+1, mask|(1<<bit))
                if score > maxScore {
                    maxScore = score
                }
            }
        }
        memo[key] = maxScore
        return maxScore
    }

    return dfs(0, 0)
}

In Go, we use a map to implement memoization because Go does not have native support for function memoization like Python. The logic is otherwise identical: we map values to bit positions and recursively compute the maximum score while avoiding duplicates.

Worked Examples

Example 1: grid = [[1,2,3],[4,3,2],[1,1,1]]

Step by step for DP:

Row Mask (bit representation) Selected Score
0 0b000 pick 1 1
1 0b001 pick 4 1 + 4 = 5
2 0b1001 pick 3 (can't pick 1) 5 + 3 = 8

Maximum score = 8.

Example 2: grid = [[8,7,6],[8,3,2]]

Row Mask Selected Score
0 0b000 pick 8 8
1 0b1000 pick 7 8 + 7 = 15

Maximum score = 15.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * 2^V) We process each row and each value, but each state (row, mask) is computed at most once; V = number of unique values (≤100)
Space O(m * 2^V) Memoization table stores results for each (row, mask) state

The small grid size makes the exponential 2^V feasible. Since m and n are ≤10 and V ≤ 100, the solution executes efficiently.

Test Cases

# Provided examples
assert Solution().maxScore([[1,2,3],[4,3,2],[1,1,1]]) == 8  # unique selection per row
assert Solution().maxScore([[8,7,6],[8,3,2]]) == 15       # skip duplicates

# Edge cases
assert Solution().maxScore([[1]]) == 1                     # single cell
assert Solution().maxScore([[1,1,1]]) == 1                 # single row, repeated values
assert Solution().maxScore([[1],[1],[1]]) == 1             # multiple rows, same value
assert Solution().maxScore([[1,2],[2,3]]) == 4             # pick optimal path: 2 + 2 or 1 + 3
assert Solution().maxScore([[10,20],[20,10],[30,40]]) == 90 # select optimal distinct values
Test Why
[[1,2,3],[4,3,2],[1,1,1]] Standard example to