Select Cells in Grid With Maximum Score solution and explanation
9 more videos on this problem
3276 Select Cells in Grid With Maximum Score || How to 🤔 in Interview || Unique || Memo + BitmaskingAyush Rao · 13:41 · 3K views
3276. Select Cells in Grid With Maximum Score | Weekly Leetcode 413codingMohan · 36:39 · 1K views
3276. Select Cells in Grid With Maximum Score (Leetcode Hard)Programming Live with Larry · 28:58 · 1K views
Leetcode | Weekly Contest 413 | B | C | 3275 | 3276 | 3276. Select Cells in Grid With Maximum ScorePretest Passed · 28:46 · 471 views
3276. Select Cells in Grid with Maximum Score | Weekly Contest 413 | Leetcode | Easiest SolutionCodeFod · 15:02 · 355 views
3276. Select Cells in Grid With Maximum Score || Weekly Contest 413|| Leetcode Hard LolCode · 17:49 · 352 views
Leetcode 3276 | Select Cells in Grid With Maximum Score | Weekly Contest 413Road To FAANG · 13:30 · 210 views
🔥Very Easy Solution 🔥 Select Cells in Grid With Maximum Score || Weekly Contest 413 || Recursion+DFSMohit Siwal · 25:05 · 115 views
3276. Select Cells in Grid With Maximum Score | Weekly Contest 413 | LeetcodeAmit Choraria · 18:11 · 99 views
3276. Select Cells in Grid With Maximum Score | leetcode weekly contest 413CodingHelp · 20:58 · 97 views
The 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.
Example 1:
Input: grid = [[1,2,3],[4,3,2],[1,1,1]]
Output: 8
Explanation:
We can select the cells with values 1, 3, and 4 that are colored above.
Example 2:
Input: grid = [[8,7,6],[8,3,2]]
Output: 15
Explanation:
We can select the cells with values 7 and 8 that are colored above.
Constraints:
1 <= grid.length, grid[i].length <= 101 <= grid[i][j] <= 100
Approach overview
Problem Overview: Given a grid of integers, pick cells to maximize the total score while respecting two constraints: you can select at most one cell from each row and you cannot select two cells with the same value. The challenge is coordinating row usage and value uniqueness across the entire grid.
Approach 1: Backtracking with Row Tracking (Exponential)
This method explores every valid combination of selections. First group all cells by their value so decisions are processed value by value. For each value, try selecting one of its candidate rows if that row is still unused, or skip the value entirely. Maintain a set or bitmask of used rows while recursively exploring the search space. The recursion effectively branches on choose a row or skip for each value. Time complexity is O(V * 2^R) in the worst case where V is the number of distinct values and R is the number of rows, with O(R) recursion space. This approach is straightforward but becomes slow when many rows share the same values.
Approach 2: Greedy Ordering + Bitmask Dynamic Programming (Optimal)
A more efficient strategy treats rows as a bitmask state and processes values in increasing or decreasing order. First build a mapping from each value to the rows where it appears. Then run dynamic programming where the state dp[mask] represents the best score achievable using the set of rows encoded in mask. For each value, iterate through existing masks and attempt to assign that value to any row containing it that is not already used in the mask. Update the new mask using bit operations such as mask | (1 << row). The row mask ensures the "one cell per row" constraint, while iterating values guarantees each value is used at most once. Because rows are typically ≤10, the number of states is small (2^R). Time complexity is O(V * 2^R * R) and space complexity is O(2^R). This technique heavily relies on bit manipulation to encode row usage efficiently.
Grids are naturally modeled using a matrix, but the key transformation is switching from cell-level decisions to value-level decisions combined with row bitmasks. That shift drastically reduces the search space.
Recommended for interviews: The bitmask dynamic programming approach is the expected solution. Interviewers want to see recognition that the number of rows is small enough for 2^R state compression. Explaining the brute-force backtracking first demonstrates understanding of the constraints, while transitioning to bitmask DP shows optimization skills and familiarity with state compression techniques.
Approach 1: Greedy + Sorting Approach
This method involves treating each row independently and sorting the values in descending order to get the largest possible set without duplicates across rows.
def maxScore(grid):
used = set()
total_sum = 0
for row in grid:
row.sort(reverse=True)
for value in row:
if value not in used:
total_sum += value
used.add(value)
break
return total_sum
# Example usage
print(maxScore([[1, 2, 3], [4, 3, 2], [1, 1, 1]])) # Output: 8import java.util.*;
public class Main {
public static int maxScore(int[][] grid) {
Set<Integer> used = new HashSet<>();
int sum = 0;
for (int[] row : grid) {
Arrays.sort(row);
for (int j = row.length - 1; j >= 0; j--) {
if (used.add(row[j])) {
sum += row[j];
break;
}
}
}
return sum;
}
public static void main(String[] args) {
int[][] grid = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
System.out.println(maxScore(grid)); // Output: 8
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
int maxScore(std::vector<std::vector<int>>& grid) {
std::unordered_set<int> used;
int sum = 0;
for (auto& row : grid) {
std::sort(row.begin(), row.end(), std::greater<int>());
for (int value : row) {
if (used.find(value) == used.end()) {
sum += value;
used.insert(value);
break;
}
}
}
return sum;
}
int main() {
std::vector<std::vector<int>> grid = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
std::cout << maxScore(grid) << std::endl; // Output: 8
return 0;
}function maxScore(grid) {
let used = new Set();
let sum = 0;
for (let row of grid) {
row.sort((a, b) => b - a);
for (let value of row) {
if (!used.has(value)) {
sum += value;
used.add(value);
break;
}
}
}
return sum;
}
console.log(maxScore([[1, 2, 3], [4, 3, 2], [1, 1, 1]])); // Output: 8#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int maxScore(int grid[3][3], int rows, int cols) {
int max_values[10];
int table[101] = {0};
int index = 0, sum = 0;
for (int i = 0; i < rows; ++i) {
qsort(grid[i], cols, sizeof(int), compare);
for (int j = 0; j < cols; ++j) {
if (table[grid[i][j]] == 0) {
max_values[index++] = grid[i][j];
table[grid[i][j]] = 1;
break;
}
}
}
for (int i = 0; i < index; ++i) {
sum += max_values[i];
}
return sum;
}
int main() {
int grid[3][3] = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
printf("%d\n", maxScore(grid, 3, 3)); // Output: 8
return 0;
}using System;
using System.Collections.Generic;
public class Program
{
public static int MaxScore(int[][] grid)
{
HashSet<int> used = new HashSet<int>();
int sum = 0;
foreach (var row in grid) {
Array.Sort(row, (a, b) => b.CompareTo(a));
foreach (int value in row) {
if (used.Add(value)) {
sum += value;
break;
}
}
}
return sum;
}
public static void Main()
{
int[][] grid = new int[3][] { new int[] { 1, 2, 3 }, new int[] { 4, 3, 2 }, new int[] { 1, 1, 1 }};
Console.WriteLine(MaxScore(grid)); // Output: 8
}
}In Python, a set helps verify value uniqueness efficiently. Each row is sorted in descending order, and the highest non-repeated value per row is selected to achieve the maximum score.
Time Complexity: O(n * m log m) as rows are sorted.
Space Complexity: O(m) due to the set used for duplicates detection.
Approach 2: Backtracking Approach
This approach involves exploring each row with potential cell selections using backtracking, carefully avoiding selected rows and ensuring unique values to maximize the score cumulatively.
def backtrack(grid, used, row, current_sum):
global max_score
if row == len(grid):
max_score = max(max_score, current_sum)
return
for value in grid[row]:
if value not in used:
used.add(value)
backtrack(grid, used, row + 1, current_sum + value)
used.remove(value)
def maxScore(grid):
global max_score
max_score = 0
backtrack(grid, set(), 0, 0)
return max_score
# Example usage
print(maxScore([[1, 2, 3], [4, 3, 2], [1, 1, 1]])) # Output: 8import java.util.*;
public class Main {
private int maxScore = 0;
private void backtrack(int[][] grid, Set<Integer> used, int row, int currentSum) {
if (row == grid.length) {
maxScore = Math.max(maxScore, currentSum);
return;
}
for (int value : grid[row]) {
if (used.add(value)) {
backtrack(grid, used, row + 1, currentSum + value);
used.remove(value);
}
}
}
public int getMaxScore(int[][] grid) {
maxScore = 0;
backtrack(grid, new HashSet<>(), 0, 0);
return maxScore;
}
public static void main(String[] args) {
int[][] grid = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
Main m = new Main();
System.out.println(m.getMaxScore(grid)); // Output: 8
}
}#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
int maxScore = 0;
void backtrack(vector<vector<int>>& grid, unordered_set<int>& used, int row, int currentSum) {
if (row == grid.size()) {
maxScore = max(maxScore, currentSum);
return;
}
for (int i = 0; i < grid[row].size(); ++i) {
if (used.find(grid[row][i]) == used.end()) {
used.insert(grid[row][i]);
backtrack(grid, used, row + 1, currentSum + grid[row][i]);
used.erase(grid[row][i]);
}
}
}
public:
int getMaxScore(vector<vector<int>>& grid) {
unordered_set<int> used;
maxScore = 0;
backtrack(grid, used, 0, 0);
return maxScore;
}
};
int main() {
vector<vector<int>> grid = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
Solution sol;
cout << sol.getMaxScore(grid) << endl; // Output: 8
return 0;
}let maxScore = 0;
function backtrack(grid, used, row, currentSum) {
if (row === grid.length) {
maxScore = Math.max(maxScore, currentSum);
return;
}
for (let value of grid[row]) {
if (!used.has(value)) {
used.add(value);
backtrack(grid, used, row + 1, currentSum + value);
used.delete(value);
}
}
}
function getMaxScore(grid) {
maxScore = 0;
backtrack(grid, new Set(), 0, 0);
return maxScore;
}
console.log(getMaxScore([[1, 2, 3], [4, 3, 2], [1, 1, 1]])); // Output: 8#include <stdio.h>
#include <stdbool.h>
int max = 0;
void backtrack(int grid[3][3], bool used[], int row, int sum, int rows, int cols) {
if (row == rows) {
if (sum > max) max = sum;
return;
}
for (int i = 0; i < cols; i++) {
if (!used[grid[row][i]]) {
used[grid[row][i]] = true;
backtrack(grid, used, row + 1, sum + grid[row][i], rows, cols);
used[grid[row][i]] = false;
}
}
}
int maxScore(int grid[3][3], int rows, int cols) {
bool used[101] = {0};
max = 0;
backtrack(grid, used, 0, 0, rows, cols);
return max;
}
int main() {
int grid[3][3] = {{1, 2, 3}, {4, 3, 2}, {1, 1, 1}};
printf("%d\n", maxScore(grid, 3, 3)); // Output: 8
return 0;
}using System;
using System.Collections.Generic;
public class Program
{
public static int maxScore;
public static void Backtrack(int[][] grid, HashSet<int> used, int row, int sum)
{
if (row == grid.Length)
{
maxScore = Math.Max(maxScore, sum);
return;
}
for (int i = 0; i < grid[row].Length; i++)
{
if (used.Add(grid[row][i]))
{
Backtrack(grid, used, row + 1, sum + grid[row][i]);
used.Remove(grid[row][i]);
}
}
}
public static int GetMaxScore(int[][] grid)
{
maxScore = 0;
Backtrack(grid, new HashSet<int>(), 0, 0);
return maxScore;
}
public static void Main(string[] args)
{
int[][] grid = new int[3][] { new int[] { 1, 2, 3 }, new int[] { 4, 3, 2 }, new int[] { 1, 1, 1 }};
Console.WriteLine(GetMaxScore(grid)); // Output: 8
}
}Python approach employs global variables to store maximum scores during the backtracking process, using recursive decision-making paths for each possible grid selection choice.
Time Complexity: O(n * 2n)
Space Complexity: O(n)
Approach 3: State Compression Dynamic Programming
We define f[i][j] to represent the maximum score when selecting numbers from [1,..i] and the state of the rows corresponding to the selected numbers is j. Initially, f[i][j] = 0, and the answer is f[mx][2^m - 1], where mx represents the maximum value in the matrix, and m represents the number of rows in the matrix.
First, we preprocess the matrix using a hash table g to record the set of rows corresponding to each number. Then, we can use state compression dynamic programming to solve the problem.
For the state f[i][j], we can choose not to select the number i, in which case f[i][j] = f[i-1][j]. Alternatively, we can choose the number i. In this case, we need to enumerate each row k in the set g[i] corresponding to the number i. If the k-th bit of j is 1, it means we can select the number i. Thus, f[i][j] = max(f[i][j], f[i-1][j \oplus 2^k] + i).
Finally, we return f[mx][2^m - 1].
The time complexity is O(m times 2^m times mx), and the space complexity is O(mx times 2^m). Here, m is the number of rows in the matrix, and mx is the maximum value in the matrix.
function maxScore(grid: number[][]): number {
const m = grid.length;
let mx = 0;
const g: boolean[][] = Array.from({ length: 101 }, () => Array(m + 1).fill(false));
for (let i = 0; i < m; ++i) {
for (const x of grid[i]) {
g[x][i] = true;
mx = Math.max(mx, x);
}
}
const f: number[][] = Array.from({ length: mx + 1 }, () => Array(1 << m).fill(0));
for (let i = 1; i <= mx; ++i) {
for (let j = 0; j < 1 << m; ++j) {
f[i][j] = f[i - 1][j];
for (let k = 0; k < m; ++k) {
if (g[i][k] && ((j >> k) & 1) === 1) {
f[i][j] = Math.max(f[i][j], f[i - 1][j ^ (1 << k)] + i);
}
}
}
}
return f[mx][(1 << m) - 1];
}func maxScore(grid [][]int) int {
m := len(grid)
mx := 0
g := [101][11]bool{}
for i, row := range grid {
for _, x := range row {
g[x][i] = true
mx = max(mx, x)
}
}
f := make([][]int, mx+1)
for i := range f {
f[i] = make([]int, 1<<m)
}
for i := 1; i <= mx; i++ {
for j := 0; j < 1<<m; j++ {
f[i][j] = f[i-1][j]
for k := 0; k < m; k++ {
if g[i][k] && (j>>k&1) == 1 {
f[i][j] = max(f[i][j], f[i-1][j^1<<k]+i)
}
}
}
}
return f[mx][1<<m-1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy + Sorting Approach | Time Complexity: O(n * m log m) as rows are sorted. |
| Backtracking Approach | Time Complexity: O(n * 2n) |
| State Compression Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Row Tracking | O(V * 2^R) | O(R) | Good for understanding the search space or when constraints are very small |
| Greedy Ordering + Bitmask DP | O(V * 2^R * R) | O(2^R) | Best general solution when rows ≤10 and value grouping is possible |
Frequently asked questions
Is Select Cells in Grid With Maximum Score easy or hard?
Select Cells in Grid With Maximum Score is classified as a Hard problem. The difficulty comes from recognizing that the row count is small enough for bitmask state compression and restructuring the problem from cell-level choices to value-based dynamic programming.
How to solve Select Cells in Grid With Maximum Score in O(V * 2^R)?
Compress row usage into a bitmask and iterate values sequentially. For each DP mask, attempt to place the current value into any row that contains that value and is not already used in the mask. Updating masks with bit operations avoids exploring redundant combinations and reduces the search space dramatically compared to naive recursion.
What is the best approach for Select Cells in Grid With Maximum Score?
The most efficient approach uses bitmask dynamic programming over rows. Group grid positions by value, then maintain a DP state where each bitmask represents which rows are already used. For each value, try assigning it to a row that contains it and is not set in the mask. This runs in O(V * 2^R * R) time and O(2^R) space, which works well because the number of rows is small.
Is Select Cells in Grid With Maximum Score asked at Google/Amazon/Meta?
Problems combining bitmask dynamic programming and grid selection patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require selecting elements under row or column constraints with state compression are especially common in senior-level algorithm interviews.
What data structure is used in Select Cells in Grid With Maximum Score?
The solution relies on arrays or hash maps to group rows by value, along with a bitmask to represent which rows are already used. Dynamic programming over these bitmask states is the main technique, supported by bit manipulation operations to update row usage efficiently.
What is the time complexity of Select Cells in Grid With Maximum Score?
The optimal bitmask DP solution runs in O(V * 2^R * R) time, where V is the number of distinct values and R is the number of rows. Each DP state represents a subset of rows, and transitions attempt to place the current value in available rows. Space complexity is O(2^R) for storing DP states.
Select Cells in Grid With Maximum Score Python or Java solution approach?
Both Python and Java implementations typically build a map from value to list of rows, then run bitmask dynamic programming. A DP array of size 2^rows stores the best score for each row combination, and transitions update masks using bit operations. The logic is identical across languages with minor syntax differences.