We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Select Cells in Grid With Maximum Score

Number: 3563

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a 2D matrix grid of positive integers, select one or more cells such that no two selected cells come from the same row and all chosen cell values are unique. The goal is to maximize the score defined as the sum of the selected cells’ values.

Key Insights

  • Since only one cell per row can be selected, the decision for each row is independent except for the global constraint of unique cell values.
  • The grid dimensions are small (at most 10×10), which makes a brute-force DFS with memoization feasible.
  • Use recursion (row by row) while maintaining a set of already picked numbers to ensure uniqueness.
  • Each row offers a choice to either skip (not select any cell) or choose a cell whose value has not been used yet.
  • Although skipping rows is allowed, at least one cell must be selected overall. In our design, since every grid cell is positive, a total score of 0 implies no cell was chosen.

Space and Time Complexity

Time Complexity: O(2^(number of rows) * number of choices per row) in the worst case; however, due to the small grid size the practical runtime is acceptable. Space Complexity: O(m) recursion stack depth and additional space for memoization keyed on the current row index and the chosen values set (which is at most 10 elements).

Solution

We use a DFS-based recursion that iterates through the rows. For each row, we have the option to skip the row or pick exactly one cell whose value has not already been chosen in previous rows. We maintain a state (row index and a set of used values) and memoize repeated states to avoid exponential recomputation.

Algorithmic details:

  1. Start recursion from row 0 with an empty set of used numbers.
  2. For the current row, consider:
    • Skipping it and moving to the next row.
    • For each column in the row, if the cell’s value isn’t in the used set then select it, add its value to the current sum, and mark the value as used.
  3. At the end of recursion (when all rows have been processed), return the accumulated sum.
  4. Memoize each state (combination of row index and the sorted tuple of used values) to prevent redundancy.

The key trick is encoding the state using a sorted tuple (or equivalent) of used numbers to serve as a memoization key.

Code Solutions

# Python implementation using DFS with memoization

def maxScore(grid):
    from functools import lru_cache
    
    num_rows = len(grid)
    
    # Use DFS recursion through rows; state is (current_row, tuple(sorted(used_numbers)))
    @lru_cache(maxsize=None)
    def dfs(row, used):
        # If all rows processed, return 0 score
        if row == num_rows:
            return 0
        
        max_sum = 0
        used_set = set(used)
        
        # Option 1: skip the current row (allowing the possibility of picking no cell in this row)
        max_sum = max(max_sum, dfs(row + 1, used))
        
        # Option 2: try every cell in the current row
        for value in grid[row]:
            # Ensure this cell's value has not been used
            if value not in used_set:
                # Add the value to used set; sort to maintain canonical order for caching
                new_used = tuple(sorted(used_set | {value}))
                candidate = value + dfs(row + 1, new_used)
                max_sum = max(max_sum, candidate)
        return max_sum
    
    # Call DFS starting from row 0 and empty used set represented as an empty tuple
    return dfs(0, ())

# Example use-case:
grid1 = [[1,2,3],[4,3,2],[1,1,1]]
print(maxScore(grid1))  # Expected Output: 8
← Back to All Questions