Problem Description

You have a 2D matrix grid containing positive integers. Your task is to select one or more cells from this matrix to maximize your score, which is the sum of all selected cell values.

However, there are two important constraints you must follow:

1. No two selected cells can be in the same row - If you pick a cell from row 0, you cannot pick any other cell from row 0.

2. All selected cell values must be unique - If you pick a cell with value 5, you cannot pick any other cell with value 5, even if it's in a different row.

Your goal is to find the maximum possible score by strategically selecting cells that satisfy both constraints.

For example, if you have a matrix:

[[1, 2, 3],
 [4, 3, 2],
 [1, 5, 4]]

You could select:

• Cell with value 3 from row 0
• Cell with value 4 from row 1
• Cell with value 5 from row 2

This gives you a score of 3 + 4 + 5 = 12, with no two cells in the same row and all values being unique.

The problem asks you to return the maximum score achievable under these constraints.

Intuition

Let's think about what makes this problem challenging. We need to pick unique values, and each value can only come from one row. This creates a complex dependency - when we pick a value, we're not just choosing the value itself, but also "using up" a row.

The key insight is to flip our perspective: instead of thinking "which cells should I pick from the grid?", we should think "for each unique value in the grid, from which row should I pick it (if at all)?"

First, let's preprocess the grid to understand which rows contain each value. For example, if value 3 appears in rows 0 and 2, we need to remember this relationship. This way, when deciding whether to include value 3 in our selection, we know our options are either row 0 or row 2.

Now comes the crucial observation: we can process values in order (from 1 to the maximum value). For each value i, we need to track which rows have already been used. This is where state compression becomes powerful - we can represent the "used rows" as a bitmask where each bit indicates whether that row has been used.

For example, if we have 3 rows and rows 0 and 2 are used, our bitmask would be 101 (in binary), which equals 5.

The dynamic programming state f[i][j] represents: "What's the maximum score when considering values from 1 to i, with row usage state j?"

For each value i and each possible row state j, we have two choices:

1. Skip value i entirely: f[i][j] = f[i-1][j]
2. Include value i by picking it from one of its available rows k. But we can only do this if row k is currently marked as "used" in state j. If we pick it, we transition from a state where row k was used to one where it's not (since we're working backwards), adding i to our score.

This approach elegantly handles both constraints: unique values (by processing each value once) and different rows (by tracking row usage in the state).

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

Let's implement the dynamic programming solution step by step:

Step 1: Preprocessing the Grid

First, we create a hash table g to map each value to the set of rows containing it:

g = defaultdict(set)
mx = 0
for i, row in enumerate(grid):
    for x in row:
        g[x].add(i)
        mx = max(mx, x)

• g[x] stores all row indices where value x appears
• mx tracks the maximum value in the entire grid

Step 2: Initialize DP Table

We create a 2D DP table where:

• First dimension represents values from 0 to mx
• Second dimension represents all possible row states using bitmask (from 0 to 2^m - 1)

m = len(grid)
f = [[0] * (1 << m) for _ in range(mx + 1)]

The state f[i][j] means: maximum score when considering values 1 to i, where j is a bitmask indicating which rows are used.

Step 3: Fill the DP Table

For each value i from 1 to mx and each possible row state j:

for i in range(1, mx + 1):
    for j in range(1 << m):
        f[i][j] = f[i - 1][j]  # Case 1: Don't select value i
      
        for k in g[i]:  # Case 2: Try selecting value i from row k
            if j >> k & 1:  # Check if row k is marked as used in state j
                f[i][j] = max(f[i][j], f[i - 1][j ^ (1 << k)] + i)

Breaking down the transition:

• f[i - 1][j]: Inherit the best score without using value i
• j >> k & 1: Check if the k-th bit of j is 1 (row k is used)
• j ^ (1 << k): Toggle the k-th bit to get the previous state (before using row k)
• f[i - 1][j ^ (1 << k)] + i: Add value i to the score from the previous state

Step 4: Return the Answer

The final answer is f[-1][-1] or f[mx][2^m - 1], which represents the maximum score when:

• All values up to mx have been considered
• All rows are available for use (all bits set to 1)

The time complexity is O(mx × 2^m × m) where mx is the maximum value and m is the number of rows. The space complexity is O(mx × 2^m) for the DP table.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 grid:

[[1, 2, 3],
 [4, 3, 2],
 [1, 5, 4]]

Step 1: Preprocessing First, we map each value to its row locations:

• Value 1: rows {0, 2}
• Value 2: rows {0, 1}
• Value 3: rows {0, 1}
• Value 4: rows {1, 2}
• Value 5: rows {2}
• Maximum value (mx) = 5

Step 2: DP Table Setup We create a DP table f[i][j] where:

• i ranges from 0 to 5 (values)
• j ranges from 0 to 7 (binary 000 to 111 for 3 rows)

The bitmask j represents which rows are "available":

• j = 7 (111): all rows available
• j = 5 (101): rows 0 and 2 available
• j = 0 (000): no rows available

Step 3: Fill DP Table Let's trace through key states:

Initially, f[0][j] = 0 for all j (no values considered).

For value 1 (appears in rows 0, 2):

• f[1][7] (all rows available):
  • Option 1: Skip value 1 → score = 0
  • Option 2: Pick from row 0 → f[0][6] + 1 = 0 + 1 = 1
  • Option 3: Pick from row 2 → f[0][3] + 1 = 0 + 1 = 1
  • Result: f[1][7] = 1

For value 3 (appears in rows 0, 1):

• f[3][7] (all rows available):
  • Option 1: Skip value 3 → f[2][7] (best score with values 1-2)
  • Option 2: Pick from row 0 → f[2][6] + 3 (row 0 becomes unavailable)
  • Option 3: Pick from row 1 → f[2][5] + 3 (row 1 becomes unavailable)

Let's say we picked value 2 from row 1 earlier, making f[2][5] = 2. Then:

• f[3][7] = max(f[2][7], f[2][5] + 3) = max(2, 2 + 3) = 5

Continuing this process through value 5:

• Eventually, we find the optimal selection: value 3 from row 0, value 4 from row 1, and value 5 from row 2
• This gives us f[5][7] = 3 + 4 + 5 = 12

Step 4: Result The final answer is f[5][7] = 12, representing the maximum score when all values have been considered and all rows were initially available.

The key insight: by processing values in order and tracking row usage with bitmasks, we ensure both constraints are satisfied - each selected value is unique (processed once) and comes from a different row (tracked in the bitmask).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × 2^m × mx)

The algorithm uses dynamic programming with bitmask to track which rows have been selected. Breaking down the time complexity:

• The outer loop iterates through all values from 1 to mx (maximum value in the grid): O(mx)
• The middle loop iterates through all possible bitmask states representing row selections: O(2^m) where m is the number of rows
• The inner loop iterates through all rows containing the current value i, which in worst case could be O(m) rows
• Each state transition involves constant time operations

Therefore, the overall time complexity is O(mx × 2^m × m), which simplifies to O(m × 2^m × mx).

Space Complexity: O(mx × 2^m)

The space usage consists of:

• The 2D DP array f with dimensions (mx + 1) × 2^m: O(mx × 2^m)
• The dictionary g storing sets of row indices for each value, which in worst case uses O(m × n) space where n is the number of columns, but this is dominated by the DP array

The dominant space consumption comes from the DP array, resulting in space complexity of O(mx × 2^m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Bitmask State Representation

A critical pitfall is misinterpreting what the bitmask j represents in the DP state. Many developers initially think j represents "rows we want to use" when it actually represents "rows that are already used/occupied."

Incorrect Understanding:

• Thinking f[i][j] means "maximum score when we can only use rows in mask j"
• This leads to incorrect state transitions

Correct Understanding:

• f[i][j] means "maximum score when considering values 1 to i, where mask j indicates which rows are already occupied"
• When j >> k & 1 is true, row k is already used, so we can place value i there
• We transition from state j ^ (1 << k) (where row k was free) to state j (where row k is now occupied)

2. Incorrect Previous State Calculation

When selecting value i from row k, developers often incorrectly calculate the previous state.

Wrong Approach:

# Incorrect: Adding the bit instead of removing it
previous_state = j | (1 << k)  # Wrong!
dp[value][row_mask] = max(dp[value][row_mask], dp[value - 1][previous_state] + value)

Correct Approach:

# Correct: XOR to toggle the bit and get the state before row k was used
previous_state = j ^ (1 << k)
dp[value][row_mask] = max(dp[value][row_mask], dp[value - 1][previous_state] + value)

3. Processing Values in Wrong Order

The algorithm requires processing values from smallest to largest (1 to max_value). Processing in random order breaks the DP recurrence relation.

Wrong:

for value in value_to_rows.keys():  # Wrong: unordered iteration
    for row_mask in range(1 << num_rows):
        # ...

Correct:

for value in range(1, max_value + 1):  # Correct: ordered from 1 to max
    for row_mask in range(1 << num_rows):
        # ...

4. Memory Optimization Trap

Some might try to optimize memory by using only two 1D arrays instead of a 2D table, but forget to handle the case where a value doesn't exist in the grid.

Problematic Optimization:

prev = [0] * (1 << num_rows)
curr = [0] * (1 << num_rows)
for value in range(1, max_value + 1):
    for row_mask in range(1 << num_rows):
        curr[row_mask] = prev[row_mask]
        # Bug: This assumes value exists in grid
        for row in value_to_rows[value]:  # Could be empty!
            # ...
    prev, curr = curr, prev

Solution: The original code handles this correctly by checking if the value exists (the loop over value_to_rows[value] simply doesn't execute if the value doesn't exist). The state correctly carries forward from dp[value-1] to dp[value] even when the value doesn't appear in the grid.