Facebook Pixel

3276. Select Cells in Grid With Maximum Score

HardBit ManipulationArrayDynamic ProgrammingBitmaskMatrix
Leetcode Link

Problem Description

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

Your task is to select one or more cells from the matrix in such a way 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 is the sum of the values of the selected cells. Your goal is to return the maximum score you can achieve based on these conditions.

Intuition

The problem requires us to select some cells under specific constraints and to maximize the sum of their values. The key constraints are that no two cells are selected from the same row and that the values selected are unique. This suggests a complex arrangement of selections considering both rows and unique values.

The solution utilizes a state compression dynamic programming approach, which enables handling of row selection constraints through binary representation. The core idea is to maintain a state that captures the current selection for each row using a bitmask. Each number in the grid has its set of associated rows.

The dynamic programming state f[i][j] represents the maximum score achievable by considering numbers up to i and the current row selection state j, where j is a bitmask representing which rows have been used. The DP transition involves choices to either include the current cell or not, ensuring valid row selection through bitwise operations.

By exploring all possibilities through this structured approach, we can effectively maximize the sum of selected values, adhering to both the uniqueness and distinct-row requirements.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The solution employs state compression dynamic programming to address the constraints of unique values and distinct rows.

Data Structures and Initialization

  1. Hash Table g: We use a hash table g to record which rows contain each number in the grid. This helps in quickly identifying potential selection states for each number.

  2. DP Table f: Define a 2D list f where f[i][j] represents the maximum score possible by selecting numbers up to i with the current row selection state represented by j. Here, j is a bitmask indicating which rows are currently selected. The dimensions of f are based on the maximum value from the grid and the number of rows.

Dynamic Programming Transition

  • Skip the Current Number: For each number i, consider not selecting it:

    f[i][j] = f[i - 1][j]

  • Include the Current Number: For each row k associated with the number i (from g[i]), check if the row is not yet selected (j >> k & 1). If it's selectable, update the DP state to reflect selecting this number and row:

    f[i][j] = max(f[i][j], f[i - 1][j ^ (1 << k)] + i)

Final Answer

The maximum score obtainable by this approach is stored in f[mx][2^m - 1], where mx is the maximum number in the grid and m is the count of rows. This reflects selecting numbers where all rows have potentially contributed to the configuration.

This algorithm efficiently explores all valid pathways using state compression to manage selection with respect to both row and value constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the following small 2D matrix grid:

[
  [5, 1, 3],
  [2, 4, 6]
]

The goal is to select cells from this grid such that no two selected cells are from the same row, and all selected values are unique, aiming to maximize the score, which is the sum of the values of the selected cells.

Step-by-step Process

  1. Data Structures Initialization:

    • Hash Table g: This hash table keeps track of which rows contain each number. For our grid:

      • Number 5 -> Row 0
      • Number 1 -> Row 0
      • Number 3 -> Row 0
      • Number 2 -> Row 1
      • Number 4 -> Row 1
      • Number 6 -> Row 1

    • DP Table f: Consider f[i][j], where i is the number being considered, and j is a bitmask representing which rows have been selected. Initialize f such that f[i][j] = 0.

  2. Transition through Dynamic Programming:

    • Iterate over the numbers in the grid, handling each number i as follows:

      • Skip the Current Number: If you decide not to pick the number i:

        f[i][j] = f[i - 1][j]

      • Include the Current Number: Determine possible rows for the number i using g[i]. For each row k:

        • Check if the current bitmask j does not already have row k included (j >> k & 1 is 0).
        • Update f considering picking the number i and selecting row k: 
          f[i][j] = max(f[i][j], f[i - 1][j ^ (1 << k)] + i)

  3. Compute the Final Max Score:

    • The final score is stored in f[mx][2^m - 1], where mx is the maximum value in the grid, and m is the number of rows. In this example, this would tell us the maximum sum possible with the constraint that every row contributes uniquely.

  4. Example Calculation:

    • For this grid, an optimal selection is: pick 5 from row 0 and 6 from row 1. The sum is 5 + 6 = 11. No two values are selected from the same row, and all values are unique.

This walkthrough demonstrates how to systematically evaluate potential selections in the matrix to return the maximum score adhering to the constraints.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def maxScore(self, grid: List[List[int]]) -> int:
6        # Create a dictionary to map each number to the set of row indices where it appears
7        number_to_rows = defaultdict(set)
8        max_value = 0
9      
10        # Fill the dictionary and find the maximum value in the grid
11        for i, row in enumerate(grid):
12            for num in row:
13                number_to_rows[num].add(i)
14                max_value = max(max_value, num)
15              
16        num_rows = len(grid)
17      
18        # Initialize the DP table with dimensions (max_value + 1) x (1 << num_rows)
19        dp = [[0] * (1 << num_rows) for _ in range(max_value + 1)]
20      
21        # Iterate over each possible value from 1 to max_value
22        for value in range(1, max_value + 1):
23            # Iterate over each possible combination of rows (using bitmask)
24            for combination in range(1 << num_rows):
25                # Initialize dp with the previous value's max score for the same combination
26                dp[value][combination] = dp[value - 1][combination]
27              
28                # Check each row index where the current value appears
29                for row_index in number_to_rows[value]:
30                    # If the row is included in the current combination
31                    if combination >> row_index & 1:
32                        # Update the dp table with the maximum score
33                        dp[value][combination] = max(
34                            dp[value][combination], 
35                            dp[value - 1][combination ^ (1 << row_index)] + value
36                        )
37      
38        # The maximum score will be stored at the last value for the full combination of rows
39        return dp[-1][-1]
40
1import java.util.List;
2
3class Solution {
4    public int maxScore(List<List<Integer>> grid) {
5        int m = grid.size();   // Number of rows in the grid
6        int maxValue = 0;      // Variable to store the maximum value found in the grid
7      
8        // Boolean matrix to keep track of possible values in each row
9        boolean[][] isAvailable = new boolean[101][m + 1];
10      
11        // Fill the boolean matrix with the presence of each value in the grid
12        for (int i = 0; i < m; ++i) {
13            for (int value : grid.get(i)) {
14                isAvailable[value][i] = true;  // Mark the value as available in row 'i'
15                maxValue = Math.max(maxValue, value);  // Update the maximum value
16            }
17        }
18      
19        // Initialize a DP table to track the maximum scores
20        int[][] dp = new int[maxValue + 1][1 << m];
21      
22        // Iterate over all possible values
23        for (int i = 1; i <= maxValue; ++i) {
24            // Check all combinations of rows using a bitmask
25            for (int mask = 0; mask < (1 << m); ++mask) {
26                dp[i][mask] = dp[i - 1][mask];  // Initialize with the value from the previous row
27              
28                // Check each row in the combination
29                for (int k = 0; k < m; ++k) {
30                    if (isAvailable[i][k] && ((mask >> k) & 1) == 1) {
31                        // Compute maximum score by selecting or not selecting a value in row 'k'
32                        dp[i][mask] = Math.max(dp[i][mask], dp[i - 1][mask ^ (1 << k)] + i);
33                    }
34                }
35            }
36        }
37      
38        // Return the maximum score achievable with all rows selected
39        return dp[maxValue][(1 << m) - 1];
40    }
41}
42
1#include <vector>
2#include <algorithm>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    int maxScore(vector<vector<int>>& grid) {
9        int m = grid.size();  // Number of rows in the grid
10        int maxValue = 0;     // To store the maximum value found in the grid
11
12        // A 2D boolean array to keep track of the presence of any number x in the grid's row
13        bool presence[101][11]{}; 
14
15        // Populate the presence array and find the maximum value in the grid
16        for (int i = 0; i < m; ++i) {
17            for (int value : grid[i]) {
18                presence[value][i] = true; // Mark the presence of value in row i
19                maxValue = max(maxValue, value); // Update the maximum value if current value is greater
20            }
21        }
22
23        // DP table to store the maximum score we can achieve using the numbers <= i and subset of rows
24        int dp[maxValue + 1][1 << m];
25        memset(dp, 0, sizeof(dp)); // Initialize the DP table with 0
26
27        // Iterate over all possible numbers from 1 to maxValue
28        for (int i = 1; i <= maxValue; ++i) {
29            // Iterate over all subsets of rows
30            for (int subset = 0; subset < (1 << m); ++subset) {
31                dp[i][subset] = dp[i - 1][subset]; // Start with the previous subset configuration without using current value
32
33                // Check if current number 'i' is present in any row 'k' and subset includes row 'k'
34                for (int k = 0; k < m; ++k) {
35                    if (presence[i][k] && (subset >> k & 1) == 1) {
36                        // Update dp to maximum score by including 'i' from row 'k'
37                        dp[i][subset] = max(dp[i][subset], dp[i - 1][subset ^ (1 << k)] + i);
38                    }
39                }
40            }
41        }
42
43        // Return the maximum score possible using all rows
44        return dp[maxValue][(1 << m) - 1];
45    }
46};
47
1// The function calculates the maximum score from a grid of numbers.
2function maxScore(grid: number[][]): number {
3    const m = grid.length; // Get the number of rows in the grid
4    let maxValue = 0; // Initialize a variable to track the maximum value in the grid
5    // Create a 2D boolean array to track which numbers exist in each row
6    const hasValue: boolean[][] = Array.from({ length: 101 }, () => Array(m).fill(false));
7
8    // Populate the boolean array and determine the maximum number in the grid
9    for (let i = 0; i < m; ++i) {
10        for (const number of grid[i]) {
11            hasValue[number][i] = true;
12            maxValue = Math.max(maxValue, number);
13        }
14    }
15
16    // Create a 2D array for dynamic programming to store the maximum score
17    const dp: number[][] = Array.from({ length: maxValue + 1 }, () => Array(1 << m).fill(0));
18
19    // Iterate over each possible value up to the maximum value in the grid
20    for (let value = 1; value <= maxValue; ++value) {
21      
22        // Iterate over all possible states of selected rows represented by bitmasks
23        for (let mask = 0; mask < 1 << m; ++mask) {
24            dp[value][mask] = dp[value - 1][mask]; // Carry forward the previous value
25
26            // Check each row to see if it contributes to the score
27            for (let row = 0; row < m; ++row) {
28                // Check if the current value exists in the row and the row is selected in the mask
29                if (hasValue[value][row] && ((mask >> row) & 1) === 1) {
30                    // Update the DP table with the maximum score possible
31                    dp[value][mask] = Math.max(dp[value][mask], dp[value - 1][mask ^ (1 << row)] + value);
32                }
33            }
34        }
35    }
36
37    // Return the maximum score possible by selecting all rows (2^m - 1 represents all rows selected)
38    return dp[maxValue][(1 << m) - 1];
39}
40

Time and Space Complexity

The time complexity of the code is O(m * 2^m * mx), where m is the number of rows in the matrix and mx is the maximum value in the matrix. This is due to the nested loops: the first over the unique values up to mx, the second over all subsets of rows (which has 2^m iterations), and the third iterating over specific rows.

The space complexity is O(mx * 2^m), caused by the 2D list f which has a size corresponding to mx values and subsets of rows represented by 2^m.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Bitmask Introduction

Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More