Problem

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

You have to select one or more cells from the matrix such that the following conditions are satisfied:

  • No two selected cells are in the same row of the matrix.
  • The values in the set of selected cells are unique.

Your score will be the sum of the values of the selected cells.

Return the maximum score you can achieve.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

Output: 8

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/29/grid1drawio.png)

We can select the cells with values 1, 3, and 4 that are colored above.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

Output: 15

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/29/grid8_8drawio.png)

We can select the cells with values 7 and 8 that are colored above.

Constraints

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

Solution

Method 1 - DP with Bitmask (Enumerate Unique Values)

Intuition

We need to select at most one cell per row, and all selected values must be unique. Since grid values are small (≤100) and grid size is small (≤10x10), we can enumerate all subsets of unique values and try to assign them to rows using DP or backtracking.

Approach

  1. Collect all unique values in the grid.
  2. For each subset of unique values, try to assign each value to a row where it appears (no two values in the same row).
  3. For each subset, if assignment is possible, sum the values and update the answer.
  4. Use bitmask DP: dp[row][mask] = max sum for first ‘row’ rows, using values in ‘mask’.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> vals;
        unordered_map<int, vector<int>> valRows;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int v = grid[i][j];
                if (valRows.count(v) == 0) vals.push_back(v);
                valRows[v].push_back(i);
            }
        int U = vals.size(), res = 0;
        for (int mask = 1; mask < (1<<U); ++mask) {
            vector<int> used(m, 0);
            int sum = 0, ok = 1;
            for (int i = 0; i < U; ++i) if (mask & (1<<i)) {
                int found = 0;
                for (int r : valRows[vals[i]]) if (!used[r]) {
                    used[r] = 1; sum += vals[i]; found = 1; break;
                }
                if (!found) { ok = 0; break; }
            }
            if (ok) res = max(res, sum);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func maxScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    valRows := map[int][]int{}
    vals := []int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            v := grid[i][j]
            if _, ok := valRows[v]; !ok { vals = append(vals, v) }
            valRows[v] = append(valRows[v], i)
        }
    }
    U, res := len(vals), 0
    for mask := 1; mask < 1<<U; mask++ {
        used := make([]bool, m)
        sum, ok := 0, true
        for i := 0; i < U; i++ {
            if mask&(1<<i) > 0 {
                found := false
                for _, r := range valRows[vals[i]] {
                    if !used[r] { used[r] = true; sum += vals[i]; found = true; break }
                }
                if !found { ok = false; break }
            }
        }
        if ok && sum > res { res = sum }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.*;
class Solution {
    public int maxScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Map<Integer, List<Integer>> valRows = new HashMap<>();
        List<Integer> vals = new ArrayList<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int v = grid[i][j];
                if (!valRows.containsKey(v)) vals.add(v);
                valRows.computeIfAbsent(v, k -> new ArrayList<>()).add(i);
            }
        int U = vals.size(), res = 0;
        for (int mask = 1; mask < (1<<U); ++mask) {
            boolean[] used = new boolean[m];
            int sum = 0; boolean ok = true;
            for (int i = 0; i < U; ++i) if ((mask & (1<<i)) > 0) {
                boolean found = false;
                for (int r : valRows.get(vals.get(i))) if (!used[r]) {
                    used[r] = true; sum += vals.get(i); found = true; break;
                }
                if (!found) { ok = false; break; }
            }
            if (ok) res = Math.max(res, sum);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    fun maxScore(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val valRows = mutableMapOf<Int, MutableList<Int>>()
        val vals = mutableListOf<Int>()
        for (i in 0 until m) for (j in 0 until n) {
            val v = grid[i][j]
            if (v !in valRows) vals.add(v)
            valRows.getOrPut(v) { mutableListOf() }.add(i)
        }
        val U = vals.size
        var res = 0
        for (mask in 1 until (1 shl U)) {
            val used = BooleanArray(m)
            var sum = 0
            var ok = true
            for (i in 0 until U) if ((mask and (1 shl i)) != 0) {
                var found = false
                for (r in valRows[vals[i]]!!) if (!used[r]) {
                    used[r] = true; sum += vals[i]; found = true; break
                }
                if (!found) { ok = false; break }
            }
            if (ok) res = maxOf(res, sum)
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def maxScore(grid):
    m, n = len(grid), len(grid[0])
    from collections import defaultdict
    val_rows = defaultdict(list)
    vals = []
    for i in range(m):
        for j in range(n):
            v = grid[i][j]
            if v not in val_rows:
                vals.append(v)
            val_rows[v].append(i)
    U, res = len(vals), 0
    for mask in range(1, 1<<U):
        used = [0]*m
        sumv, ok = 0, True
        for i in range(U):
            if mask & (1<<i):
                found = False
                for r in val_rows[vals[i]]:
                    if not used[r]:
                        used[r] = 1; sumv += vals[i]; found = True; break
                if not found:
                    ok = False; break
        if ok:
            res = max(res, sumv)
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

use std::collections::HashMap;
pub fn max_score(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut val_rows: HashMap<i32, Vec<usize>> = HashMap::new();
    let mut vals = vec![];
    for i in 0..m {
        for j in 0..n {
            let v = grid[i][j];
            if !val_rows.contains_key(&v) { vals.push(v); }
            val_rows.entry(v).or_default().push(i);
        }
    }
    let U = vals.len();
    let mut res = 0;
    for mask in 1..(1<<U) {
        let mut used = vec![false; m];
        let mut sum = 0;
        let mut ok = true;
        for i in 0..U {
            if (mask & (1<<i)) > 0 {
                let mut found = false;
                for &r in &val_rows[&vals[i]] {
                    if !used[r] { used[r] = true; sum += vals[i]; found = true; break; }
                }
                if !found { ok = false; break; }
            }
        }
        if ok && sum > res { res = sum; }
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function maxScore(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const valRows: Record<number, number[]> = {};
    const vals: number[] = [];
    for (let i = 0; i < m; ++i) for (let j = 0; j < n; ++j) {
        const v = grid[i][j];
        if (!(v in valRows)) vals.push(v);
        if (!(v in valRows)) valRows[v] = [];
        valRows[v].push(i);
    }
    const U = vals.length;
    let res = 0;
    for (let mask = 1; mask < (1<<U); ++mask) {
        const used = Array(m).fill(false);
        let sum = 0, ok = true;
        for (let i = 0; i < U; ++i) if (mask & (1<<i)) {
            let found = false;
            for (const r of valRows[vals[i]]) {
                if (!used[r]) { used[r] = true; sum += vals[i]; found = true; break; }
            }
            if (!found) { ok = false; break; }
        }
        if (ok && sum > res) res = sum;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(2^U * U * m) where U = number of unique values (≤100), m = number of rows (≤10)
  • 🧺 Space complexity: O(U + m)