3276. Select Cells in Grid With Maximum Score LeetCode Solution
In this guide, you will get 3276. Select Cells in Grid With Maximum Score LeetCode Solution with the best time and space complexity. The solution to Select Cells in Grid With Maximum Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Select Cells in Grid With Maximum Score
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.
3276. Select Cells in Grid With Maximum Score LeetCode Solution in C++
class Solution {
public:
int maxScore(vector<vector<int>>& grid) {
unordered_map<int, unordered_set<int>> numToIndices;
for (int index = 0; index < grid.size(); ++index)
for (const int num : grid[index])
numToIndices[num].insert(index);
vector<vector<int>> mem(numToIndices.size(), vector<int>(1 << grid.size()));
return maxScore({numToIndices.begin(), numToIndices.end()}, 0, 0, mem);
}
private:
// Returns the maximum score by selecting numbers from numToIndices[i..],
// where `mask` is the bitmask of the used row indices.
int maxScore(const vector<pair<int, unordered_set<int>>>& numToIndices, int i,
int mask, vector<vector<int>>& mem) {
if (i == numToIndices.size())
return 0;
if (mem[i][mask] != 0)
return mem[i][mask];
// Skip numToIndices[i].first.
int res = maxScore(numToIndices, i + 1, mask, mem);
for (const int index : numToIndices[i].second)
if ((mask >> index & 1) == 0)
// Take numToIndices[i].first.
res =
max(res, numToIndices[i].first +
maxScore(numToIndices, i + 1, mask | 1 << index, mem));
return mem[i][mask] = res;
}
}; /* code provided by PROGIEZ */
3276. Select Cells in Grid With Maximum Score LeetCode Solution in Java
class Solution {
public int maxScore(List<List<Integer>> grid) {
Map<Integer, Set<Integer>> numToIndices = new HashMap<>();
for (int index = 0; index < grid.size(); ++index)
for (final int num : grid.get(index)) {
numToIndices.putIfAbsent(num, new HashSet<>());
numToIndices.get(num).add(index);
}
int[][] mem = new int[numToIndices.size()][1 << grid.size()];
return maxScore(new ArrayList<>(numToIndices.entrySet()), 0, 0, mem);
}
// Returns the maximum score by selecting numbers from numToIndices[i..],
// where `mask` is the bitmask of the used row indices.
private int maxScore(List<Map.Entry<Integer, Set<Integer>>> numToIndices, int i, int mask,
int[][] mem) {
if (i == numToIndices.size())
return 0;
if (mem[i][mask] != 0)
return mem[i][mask];
// Skip numToIndices[i].getKey().
int res = maxScore(numToIndices, i + 1, mask, mem);
for (int index : numToIndices.get(i).getValue())
if ((mask >> index & 1) == 0)
// Take numToIndices[i].getKey().
res = Math.max(res, numToIndices.get(i).getKey() +
maxScore(numToIndices, i + 1, mask | (1 << index), mem));
return mem[i][mask] = res;
}
} // code provided by PROGIEZ
3276. Select Cells in Grid With Maximum Score LeetCode Solution in Python
class Solution:
def maxScore(self, grid: list[list[int]]) -> int:
numToIndices = collections.defaultdict(set)
for index, row in enumerate(grid):
for num in row:
numToIndices[num].add(index)
numToIndices = list(numToIndices.items())
@functools.lru_cache(None)
def dp(i: int, mask: int) -> int:
"""
Returns the maximum score by selecting numbers from numToIndices[i..],
where `mask` is the bitmask of the used row indices.
"""
if i == len(numToIndices):
return 0
# Skip numToIndices[i][0].
res = dp(i + 1, mask)
for index in numToIndices[i][1]:
if (mask >> index & 1) == 0:
# Take numToIndices[i][0].
res = max(res, numToIndices[i][0] + dp(i + 1, mask | 1 << index))
return res
return dp(0, 0) # code by PROGIEZ
