Select Cells in Grid With Maximum Score - Practice Coding Problems

Select Cells in Grid With Maximum Score - Problem

You're given a 2D grid filled with positive integers, and your goal is to become a strategic treasure hunter! 🏆

Your mission: Select cells from the grid to maximize your score (sum of selected values), but there are two crucial rules:

No two cells from the same row - each row can contribute at most one treasure
All selected values must be unique - no duplicates allowed in your collection

Think of it as choosing the best representatives from each row, where each representative must have a unique value that hasn't been chosen before.

Example: In grid [[1,2,3],[4,3,2],[1,1,1]], you could select 3 from row 0 and 4 from row 1 for a score of 7, but you can't select another 3 since values must be unique!

Input & Output

example_1.py — Basic Grid

$ Input: grid = [[1,2,3],[4,3,2],[1,1,1]]

› Output: 8

💡 Note: Select 3 from row 0 (index [0,2]), 4 from row 1 (index [1,0]), and skip row 2 (all values are 1, but 1 hasn't been used yet, so we could pick 1 for a total of 3+4+1=8). Actually, the optimal is to pick 2 from row 0, 4 from row 1, and 1 from row 2 for total 2+4+1=7, or pick 3 from row 0 and 4 from row 1 for 3+4=7. Wait, let me recalculate: pick 3 from row 0, 4 from row 1, 1 from row 2 = 8 total.

example_2.py — Duplicate Values

$ Input: grid = [[7,9,8,6,2],[6,1,1,2,8]]

› Output: 24

💡 Note: From row 0, select 9 (highest unique value). From row 1, select 1 (since 6, 2, 8 are already available in row 0, pick a value not in row 0). Actually, select 9 from row 0 and 1 from row 1 gives 9+1=10. Better: select 7 from row 0 and 8 from row 1 gives 15. Even better: select 9 from row 0 and 6 from row 1 gives 15. Optimal: select 8 from row 0 and 6 from row 1, but wait - we want to maximize, so select 9 from row 0 and 8 from row 1 but 8 appears in both rows. Select 9 from row 0 and 6 from row 1 = 15.

example_3.py — Single Row

$ Input: grid = [[8,7,6]]

› Output: 8

💡 Note: With only one row, select the maximum value which is 8.

Constraints

1 ≤ grid.length, grid[i].length ≤ 10
1 ≤ grid[i][j] ≤ 100
All values in the grid are positive integers
You must select at least one cell to get a non-zero score

Visualization

Tap to expand

Understanding the Visualization

Catalog Artifacts

List all unique artifact values and create a tracking system

Hall by Hall

Process each exhibition hall (row) one by one

Smart Selection

For each hall, try selecting each artifact while tracking which values are already taken

Maximize Value

Keep track of the best possible exhibition value for each combination of selected artifacts

Key Takeaway

🎯 Key Insight: The bitmask DP approach efficiently explores all valid combinations by encoding 'which values have been used' as bits, avoiding redundant subproblem calculations and guaranteeing optimal results.

Asked in

G Google 45 f Meta 32 a Amazon 28 ⊞ Microsoft 22

The optimal solution uses Dynamic Programming with Bitmask to efficiently track which values have been selected while processing each row. This approach has time complexity O(rows × 2^unique_values × cols) and guarantees the maximum score by exploring all valid combinations without redundant calculations.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(rows × 2^unique_values × cols)	O(rows × 2^unique_values)	Use DP with bitmask to track used values and optimize overlapping subproblems
Brute Force (Try All Combinations)	O((max_cols)^rows)	O(rows)	Generate all possible selections and find the maximum valid score

Dynamic Programming with Bitmask — Algorithm Steps

Create a list of unique values from the entire grid and sort them
Use bitmask to represent which values have been selected
Use DP state: dp[row][mask] = maximum score using rows 0..row-1 with values represented by mask
For each row and each mask state, try selecting each valid cell or skip the row
Return the maximum score from all final states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty bitmask (no values used)

Process Row

For each row, create new states by selecting valid cells

Update Bitmask

Set corresponding bit when value is selected

Maximize Score

Keep only the best score for each bitmask state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VALS 100
#define MAX_STATES 1024

struct State {
    int mask;
    int score;
};

int maxScore(int** grid, int gridSize, int* gridColSize) {
    // Get unique values (simplified for C)
    int allValues[MAX_VALS];
    int valueCount = 0;
    
    // Collect all values
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            int val = grid[i][j];
            int found = 0;
            for (int k = 0; k < valueCount; k++) {
                if (allValues[k] == val) {
                    found = 1;
                    break;
                }
            }
            if (!found && valueCount < MAX_VALS) {
                allValues[valueCount++] = val;
            }
        }
    }
    
    // Simple DP implementation
    struct State dp[MAX_STATES];
    int dpSize = 1;
    dp[0].mask = 0;
    dp[0].score = 0;
    
    for (int row = 0; row < gridSize; row++) {
        struct State newDp[MAX_STATES];
        int newDpSize = 0;
        
        // Copy existing states
        for (int i = 0; i < dpSize; i++) {
            newDp[newDpSize++] = dp[i];
        }
        
        // Try adding new states
        for (int i = 0; i < dpSize; i++) {
            for (int col = 0; col < gridColSize[row]; col++) {
                int val = grid[row][col];
                int valIdx = -1;
                
                // Find value index
                for (int k = 0; k < valueCount; k++) {
                    if (allValues[k] == val) {
                        valIdx = k;
                        break;
                    }
                }
                
                if (valIdx != -1 && !(dp[i].mask & (1 << valIdx))) {
                    struct State newState;
                    newState.mask = dp[i].mask | (1 << valIdx);
                    newState.score = dp[i].score + val;
                    
                    if (newDpSize < MAX_STATES) {
                        newDp[newDpSize++] = newState;
                    }
                }
            }
        }
        
        dpSize = newDpSize;
        memcpy(dp, newDp, sizeof(struct State) * dpSize);
    }
    
    int maxResult = 0;
    for (int i = 0; i < dpSize; i++) {
        if (dp[i].score > maxResult) {
            maxResult = dp[i].score;
        }
    }
    
    return maxResult;
}

int main() {
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(rows × 2^unique_values × cols)

For each row and bitmask combination, we try each column

✓ Linear Growth

Space Complexity

O(rows × 2^unique_values)

DP table stores states for each row and bitmask combination

⚡ Linearithmic Space

52.0K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler