Scale Engineer

Select Cells in Grid With Maximum Score

Hard
#2908Time: O((n+1)^m), where `m` is the number of rows and `n` is the number of columns. For each of the `m` rows, we explore `n` options for selecting a cell plus one option for skipping the row. This leads to a recursion tree with approximately `(n+1)^m` nodes, making it infeasible for the given constraints.Space: O(m), where `m` is the number of rows. This space is used for the recursion stack. The `usedValues` set also requires space, but its size is at most `m`.
Patterns
Dynamic ProgrammingBit ManipulationBitmask
Data structures
ArrayMatrix

Prompt

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 <= 10
  • 1 <= grid[i][j] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a classic recursive backtracking technique. It explores every possible valid combination of cell selections by making a decision for each row: either to skip it or to pick one of its cells. The validity of a selection is checked by ensuring the chosen cell's value is unique among all previously selected cells.

Algorithm

  • Define a recursive function backtrack(rowIndex, currentScore, usedValues, grid).
  • The base case for the recursion is when rowIndex equals the total number of rows. At this point, update the global maximum score with currentScore.
  • In the recursive step, for the current rowIndex, explore two main branches:
    1. Skip the row: Make a recursive call for the next row: backtrack(rowIndex + 1, currentScore, usedValues, grid).
    2. Select a cell: Iterate through each column col of the current row.
      • Let value = grid[rowIndex][col].
      • If value is not present in the usedValues set, it's a valid choice.
      • Add value to usedValues.
      • Make a recursive call for the next row with the updated score and used values: backtrack(rowIndex + 1, currentScore + value, usedValues, grid).
      • After the recursive call returns, remove value from usedValues to backtrack and explore other possibilities.
  • The initial call to start the process is backtrack(0, 0, new HashSet<>(), grid).

Walkthrough

The brute-force backtracking approach systematically explores every valid combination of cells. The core of this method is a recursive function that traverses through the rows of the grid. For each row, it considers two possibilities: either skipping the row entirely or selecting one cell from it. If a cell is selected, its value must not have been chosen from any of the previous rows. This process builds a search tree where each path from the root to a leaf represents a valid selection. The score of each path is calculated, and the maximum score found across all paths is the answer.

class Solution {    int maxScore = 0;     public int selectCells(int[][] grid) {        backtrack(0, 0, new HashSet<>(), grid);        return maxScore;    }     private void backtrack(int rowIndex, int currentScore, Set<Integer> usedValues, int[][] grid) {        if (rowIndex == grid.length) {            maxScore = Math.max(maxScore, currentScore);            return;        }         // Option 1: Skip the current row        backtrack(rowIndex + 1, currentScore, usedValues, grid);         // Option 2: Pick one cell from the current row        for (int col = 0; col < grid[rowIndex].length; col++) {            int value = grid[rowIndex][col];            if (!usedValues.contains(value)) {                usedValues.add(value);                backtrack(rowIndex + 1, currentScore + value, usedValues, grid);                usedValues.remove(value); // backtrack            }        }    }}

Complexity

Time

O((n+1)^m), where `m` is the number of rows and `n` is the number of columns. For each of the `m` rows, we explore `n` options for selecting a cell plus one option for skipping the row. This leads to a recursion tree with approximately `(n+1)^m` nodes, making it infeasible for the given constraints.

Space

O(m), where `m` is the number of rows. This space is used for the recursion stack. The `usedValues` set also requires space, but its size is at most `m`.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Correctly explores the entire search space to guarantee the right answer if given enough time.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {public  int maxScore(List<List<Integer>> grid) {    int m = grid.size();    int mx = 0;    boolean[][] g = new boolean[101][m + 1];    for (int i = 0; i < m; ++i) {      for (int x : grid.get(i)) {        g[x][i] = true;        mx = Math.max(mx, x);      }    }    int[][] f = new int[mx + 1][1 << m];    for (int i = 1; i <= mx; ++i) {      for (int j = 0; j < 1 << m; ++j) {        f[i][j] = f[i - 1][j];        for (int 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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem