Select Cells in Grid With Maximum Score

Hard
1660.

Select Cells in Grid With Maximum Score

HardArrayDynamic ProgrammingBit ManipulationMatrixBitmaskGoogle

Select Cells in Grid With Maximum Score is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.

You are given a 2D matrix grid of positive integers.

Select one or more cells so that:

  • no two selected cells lie in the same row, and
  • the values of the selected cells are pairwise distinct.

The score is the sum of the selected values. Return the maximum score you can achieve.

Example 1

Input
grid = [[1,2,3],[4,3,2],[1,1,1]]
Output
8
Explanation
Take 1 from the last row, 4 from the middle row and 3 from the first row: 1 + 4 + 3 = 8.

Example 2

Input
grid = [[8,7,6],[8,3,2]]
Output
15
Explanation
Take 7 from the first row and 8 from the second.

Example 3

Input
grid = [[7,7],[7,7]]
Output
7
Explanation
Every cell holds 7, so only one cell can be selected.

Constraints

  • 1 <= grid.length, grid[i].length <= 10
  • 1 <= grid[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxScore = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Select Cells in Grid With Maximum Score — Problem & Solution

Select Cells in Grid With Maximum Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Select Cells in Grid With Maximum Score is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.

Problem statement

You are given a 2D matrix grid of positive integers.

Select one or more cells so that:

  • no two selected cells lie in the same row, and
  • the values of the selected cells are pairwise distinct.

The score is the sum of the selected values. Return the maximum score you can achieve.

Example 1

Input: grid = [[1,2,3],[4,3,2],[1,1,1]]
Output: 8
Explanation: Take 1 from the last row, 4 from the middle row and 3 from the first row: 1 + 4 + 3 = 8.

Example 2

Input: grid = [[8,7,6],[8,3,2]]
Output: 15
Explanation: Take 7 from the first row and 8 from the second.

Example 3

Input: grid = [[7,7],[7,7]]
Output: 7
Explanation: Every cell holds 7, so only one cell can be selected.

Constraints

  • 1 <= grid.length, grid[i].length <= 10
  • 1 <= grid[i][j] <= 100

Hints for Select Cells in Grid With Maximum Score

  1. Hint 1

    There are at most 10 rows, so the set of rows already used fits in a bitmask.

  2. Hint 2

    Process the distinct values one at a time (each value is used at most once): the state is just which rows are already taken.

  3. Hint 3

    For value v, either skip it or place it in one free row that contains v: dp'[mask | 1 << r] = max(dp[mask] + v).

How to solve Select Cells in Grid With Maximum Score

Uniqueness is a constraint on values and the one-per-row rule is a constraint on rows. Iterating over values makes uniqueness automatic (each value is considered once), and with at most 10 rows the rows used so far fit in a bitmask.

Approach

  1. For every value v, record rows[v], the bitmask of rows that contain v.
  2. Let dp[mask] be the best score using exactly the rows in mask; start with dp[0] = 0 and every other mask unreachable.
  3. For each distinct value v, copy dp into ndp; for every reachable mask and every row r in rows[v] not in mask, relax ndp[mask | 1 << r] with dp[mask] + v. Then dp = ndp.
  4. Return the largest value in dp.

Why it works

Any valid selection assigns each chosen value to a distinct row that contains it. Walking the values in any fixed order and deciding for each whether (and in which free row) it is used enumerates exactly those assignments, and two selections with the same set of used rows are interchangeable for every later decision — so keeping only the best score per mask loses nothing.

Complexity

  • Time — O(V · 2^R · R)
  • Space — O(2^R)

Pitfalls

  • Update into a copy (ndp) — relaxing in place could place the same value twice.
  • Greedily taking each row's maximum fails: two rows may share their best value.

Reference solution

Python

from typing import List

def maxScore(grid: List[List[int]]) -> int:
    R = len(grid)
    rows = {}
    for r, row in enumerate(grid):
        for v in row:
            rows[v] = rows.get(v, 0) | (1 << r)
    full = 1 << R
    dp = [-1] * full
    dp[0] = 0
    for v, rm in rows.items():
        nd = dp[:]
        for mask in range(full):
            if dp[mask] < 0:
                continue
            free = rm & ~mask
            while free:
                b = free & -free
                free ^= b
                if dp[mask] + v > nd[mask | b]:
                    nd[mask | b] = dp[mask] + v
        dp = nd
    return max(dp)

Java

public static int maxScore(int[][] grid) {
    int R = grid.length;
    int[] rows = new int[101];
    for (int r = 0; r < R; r++) for (int v : grid[r]) rows[v] |= 1 << r;
    int full = 1 << R;
    int[] dp = new int[full];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int val = 1; val <= 100; val++) {
        if (rows[val] == 0) continue;
        int[] nd = dp.clone();
        for (int mask = 0; mask < full; mask++) {
            if (dp[mask] < 0) continue;
            int free = rows[val] & ~mask;
            while (free != 0) {
                int b = free & -free;
                free ^= b;
                nd[mask | b] = Math.max(nd[mask | b], dp[mask] + val);
            }
        }
        dp = nd;
    }
    int best = 0;
    for (int x : dp) best = Math.max(best, x);
    return best;
}

C++

int maxScore(vector<vector<int>>& grid) {
    int R = grid.size();
    vector<int> rows(101, 0);
    for (int r = 0; r < R; r++) for (int v : grid[r]) rows[v] |= 1 << r;
    int full = 1 << R;
    vector<int> dp(full, -1);
    dp[0] = 0;
    for (int val = 1; val <= 100; val++) {
        if (rows[val] == 0) continue;
        vector<int> nd = dp;
        for (int mask = 0; mask < full; mask++) {
            if (dp[mask] < 0) continue;
            int fr = rows[val] & ~mask;
            while (fr) {
                int b = fr & -fr;
                fr ^= b;
                nd[mask | b] = max(nd[mask | b], dp[mask] + val);
            }
        }
        dp = nd;
    }
    return *max_element(dp.begin(), dp.end());
}

JavaScript

var maxScore = function(grid) {
    var R = grid.length;
    var rows = [];
    for (var v = 0; v <= 100; v++) rows.push(0);
    for (var r = 0; r < R; r++) {
        for (var c = 0; c < grid[r].length; c++) rows[grid[r][c]] |= (1 << r);
    }
    var full = 1 << R;
    var dp = [];
    for (var m = 0; m < full; m++) dp.push(-1);
    dp[0] = 0;
    for (var val = 1; val <= 100; val++) {
        if (rows[val] === 0) continue;
        var nd = dp.slice();
        for (var mask = 0; mask < full; mask++) {
            if (dp[mask] < 0) continue;
            var free = rows[val] & ~mask;
            while (free) {
                var b = free & -free;
                free ^= b;
                if (dp[mask] + val > nd[mask | b]) nd[mask | b] = dp[mask] + val;
            }
        }
        dp = nd;
    }
    var best = 0;
    for (var k = 0; k < full; k++) if (dp[k] > best) best = dp[k];
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming