1659. Maximize Grid Happiness

HardBit ManipulationMemoizationDynamic ProgrammingBitmask

Problem Description

In this problem, you are given a grid of size m x n where you can place a certain number of introverts and extroverts, given by introvertsCount and extrovertsCount, respectively. Each type of person has a starting happiness value (120 for introverts, 40 for extroverts) that can increase or decrease based on the number of adjacent neighbors. For each introvert neighbor, an introvert loses 30 happiness while an extrovert gains 20. The goal is to maximize the total happiness of all individuals on the grid. The problem asks to determine this maximum possible grid happiness.

Not every person needs to be placed on the grid, and the positions where the individuals are placed will significantly affect the overall grid happiness. The total grid happiness is the sum of the happiness of all people positioned on the grid. Note, neighbors are considered only in the four orthogonal directions (up, down, left, and right), not diagonally.

Intuition

To solve this problem, we employ dynamic programming and depth-first search (DFS). We will use DFS to explore every possible combination of positions on the grid and dynamic programming to store the results of subproblems to avoid recalculating the same scenarios.

The key ideas behind the solution are:

Encode the state of the last row of the grid to use as a reference for calculating the happiness of the people placed on the current row.
Consider three possible states for each cell on the grid: empty (0), has an introvert (1), or has an extrovert (2).
Evaluate the impact of placing an introvert or extrovert in the current cell based on the neighbors' states, adjusting the happiness accordingly.
Recursively compute the maximum happiness for the remaining grid configuration after placing a person or leaving the cell empty.

The solution deeply cycles through the grid, attempting to place an introvert or extrovert in each cell (or leaving it empty), calculates the happiness gained or lost by the adjacent individuals, and uses memoization (@cache decorator) to remember the results of previous computations to improve efficiency.

The state of the grid is efficiently tracked by storing an integer representation (pre) where each digit represents the state of a cell in the last row of the grid, which helps to determine the happiness of a placed individual based on their neighbors. By always considering the best possible outcome at each step and leveraging memoization, the algorithm ensures that the final result will be the maximum possible grid happiness.

Learn more about Memoization, Dynamic Programming and Bitmask patterns.

Solution Approach

The implementation of the solution employs several key programming concepts and algorithms, including dynamic programming, depth-first search, and state compression. Here’s a breakdown of the approach:

Dynamic Programming & Cache: To avoid recalculating subproblems, the solution makes use of dynamic programming. The @cache decorator is used to memorize the results of previous states, which means once dfs (our depth-first search function) computes the maximum happiness for a certain state, it stores the result. If the same state is encountered again, the cached result is returned instead of recomputing.
Depth-First Search (DFS): The core of the solution is the recursive function dfs, which stands for depth-first search. DFS is a common way to traverse all possible combinations in the state space. It explores the grid cell by cell, making decisions at each step to either place an introvert, extrovert, or leave the cell empty.
State Compression: The pre parameter is a compact representation of the last row of the grid’s state. It is an integer that is effectively a base-3 number where each digit represents a cell's state in the previous row (0 for empty, 1 for introvert, 2 for extrovert). This encoding allows for efficient transitions and checking of neighbor states.
Transition: The recursive function attempts to transition from one cell to the next by incrementing pos, and for the current cell, it tries three different actions (leaving it empty, placing an introvert, placing an extrovert). The for i in range(3) loop represents these three actions.
Happiness Calculation: Happiness is calculated using the array h, which stores the happiness adjustments when two types of people become neighbors. For instance, h[1][2] means an introvert is next to an extrovert, so the happiness change is -10 for the introvert and +20 for the extrovert.
Base Case: If pos equals m * n or both ic (introvert count) and ec (extrovert count) are zero, the function returns 0 as there are no more cells or no more people to place.
Maximum Happiness: At each step, the solution updates ans, which accumulates the maximum possible happiness. It does this by recursively calling dfs and passing the new state, then combining the result with the happiness contribution of placing the person in the current cell. This evaluation involves comparing the value obtained by including the current cell in various states (empty, with introvert, with extrovert) and taking the maximum.

By carefully combining these elements, the solution is able to efficiently explore a large state space and calculate the optimal arrangement for maximum grid happiness.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a smaller and simplified example. Suppose we have a 2x2 grid, 1 introvert count (ic = 1), and 1 extrovert count (ec = 1). Our goal is to place the introvert and extrovert in a way that maximizes the total happiness of the grid.

Our dfs function begins at position pos = 0 (the top-left cell), with a base case that if pos is equal to the number of cells (m*n, which is 4 in our case) or both ic and ec are zero, it returns 0 since there are no more cells or people to place.
At pos = 0, there are three options: leave it empty, place an introvert, or place an extrovert. We start with the loop for i in range(3) to consider all three possibilities.
- If the cell is left empty, dfs(1, 1, 1, 0) is called for the next position with the same number of people to place and the empty state pre for the current row.
- If an introvert is placed, dfs(1, 0, 1, 1) is called with one fewer introvert and the state of the current row updated to reflect an introvert in the first cell.
- If an extrovert is placed, dfs(1, 1, 0, 2) is called with one fewer extrovert and the current row state updated to reflect an extrovert in the first cell.
As we call these options recursively, our @cache decorator ensures that if the same state of the grid is ever encountered again, the calculated result is simply returned from the cache rather than recomputed.
The happiness impact of placing a person is evaluated. If an introvert is placed at pos = 0, and later another introvert is placed adjacent to it at pos = 1, then the happiness for each introvert is decreased by 30. Conversely, placing an extrovert next to an introvert increases the extrovert's happiness by 20 and decreases the introvert's happiness by 30.
As we recurse through the grid, each time we place a person or leave a cell empty, we calculate the new maximum happiness ans, inclusive of the current cell's contribution.
Eventually, all possibilities for the 2x2 grid will have been explored, and the maximal ans value reflects the optimal placement of the introvert and extrovert for maximum grid happiness.

Through this process, the dfs function along with dynamic programming, state compression, and careful calculation of happiness contributions, determines the optimal grid placement for the given number of introverts and extroverts to maximize the total happiness of the grid.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def getMaxGridHappiness(
5        self, rows: int, cols: int, introverts_count: int, extroverts_count: int
6    ) -> int:
7        # Constants to represent the types of people
8        EMPTY, INTROVERT, EXTROVERT = 0, 1, 2
9
10        # Happiness impact table
11        happiness_impact = [
12            [0, 0, 0],
13            [0, -60, -10],
14            [0, -10, 40]
15        ]
16
17        # Cache computed states to avoid recomputation (memoization)
18        @lru_cache(maxsize=None)
19        def dfs(position: int, previous_row_state: int, remaining_introverts: int, remaining_extroverts: int) -> int:
20            # Base case when all cells are filled or no people remaining
21            if position == rows * cols or (remaining_introverts == 0 and remaining_extroverts == 0):
22                return 0
23
24            # No one placed in the current cell
25            max_happiness = 0
26
27            # Determine the value 'up' (neighbor above) from the previous row state
28            up_neighbor = previous_row_state // pow(3, cols - 1)
29
30            # Determine the value of 'left' (neighbor to the left), which is 0 if at the row start
31            left_neighbor = 0 if position % cols == 0 else previous_row_state % 3
32
33            # Try all three possibilities: empty, with an introvert, or with an extrovert
34            for person in [EMPTY, INTROVERT, EXTROVERT]:
35                if (person == INTROVERT and remaining_introverts == 0) or \
36                   (person == EXTROVERT and remaining_extroverts == 0):
37                    continue  # Skip if not enough people of a type
38                new_state = ((previous_row_state % pow(3, cols - 1)) * 3) + person
39                additive_happiness = happiness_impact[up_neighbor][person] + happiness_impact[left_neighbor][person]
40                resultant_happiness = dfs(position + 1, new_state, remaining_introverts - (person == INTROVERT), remaining_extroverts - (person == EXTROVERT))
41
42                base_happiness = 0
43                if person == INTROVERT:
44                    base_happiness = 120
45                elif person == EXTROVERT:
46                    base_happiness = 40
47
48                # Calculate total happiness
49                total_happiness = additive_happiness + resultant_happiness + base_happiness
50                max_happiness = max(max_happiness, total_happiness)
51
52            return max_happiness
53
54        return dfs(0, 0, introverts_count, extroverts_count)
55
56# Example usage:
57# solution = Solution()
58# happiness = solution.getMaxGridHappiness(3, 3, 2, 1)
59# print(happiness)  # Output the maximum grid happiness
60

1class Solution {
2    private int rows; // Number of rows in the grid
3    private int cols; // Number of columns in the grid
4    private int base; // The base used for representing the ternary state
5    private final int[][] happinessChange = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}}; // Happiness change table
6    private Integer[][][][] memoization; // Memoization array for storing intermediate results
7
8    // Returns the maximum grid happiness for the given configuration
9    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
10        this.rows = m;
11        this.cols = n;
12        base = (int) Math.pow(3, n - 1);
13        memoization = new Integer[m * n][base * 3][introvertsCount + 1][extrovertsCount + 1];
14        return dfs(0, 0, introvertsCount, extrovertsCount);
15    }
16
17    // Depth-first search to find the maximum happiness
18    private int dfs(int position, int previous, int introverts, int extroverts) {
19        // If we filled the entire grid or have no more people left, stop the recursion
20        if (position == rows * cols || (introverts == 0 && extroverts == 0)) {
21            return 0;
22        }
23        // Return memoized result if available
24        if (memoization[position][previous][introverts][extroverts] != null) {
25            return memoization[position][previous][introverts][extroverts];
26        }
27      
28        int maxHappiness = 0; // To store the max happiness at the current state
29        int above = previous / base; // The state of the cell above
30        int left = position % cols == 0 ? 0 : previous % 3; // The state of the cell to the left
31      
32        // Try placing each type of person (0: none, 1: introvert, 2: extrovert)
33        for (int i = 0; i < 3; ++i) {
34            // Skip if no people of the type are left
35            if ((i == 1 && introverts == 0) || (i == 2 && extroverts == 0)) {
36                continue;
37            }
38            // Calculate the new previous state after placing the person
39            int current = previous % base * 3 + i;
40            // Gain/loss of happiness by placing at current vs adjacent positions
41            int happinessGain = happinessChange[above][i] + happinessChange[left][i];
42            // Recursively call dfs for the next cell
43            int nextHappiness = dfs(position + 1, current, introverts - (i == 1 ? 1 : 0), extroverts - (i == 2 ? 1 : 0));
44            // Base happiness for introvert/extrovert
45            int baseHappiness = i == 1 ? 120 : (i == 2 ? 40 : 0);
46            // Calculate the total happiness and update maxHappiness
47            maxHappiness = Math.max(maxHappiness, happinessGain + nextHappiness + baseHappiness);
48        }
49        // Memoize and return the computed happiness
50        return memoization[position][previous][introverts][extroverts] = maxHappiness;
51    }
52}
53

1#include <vector>
2#include <cstring>
3#include <cmath>
4#include <functional>
5using namespace std;
6
7class Solution {
8public:
9    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
10        // Happiness scores for combinations of introverts(I), extroverts(E), and empty(Emp) cells.
11        // h[state1][state2] represents the additional happiness when state1 is adjacent to state2.
12        int happinessScores[3][3] = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}};
13      
14        // Power calculation to track the state of the grid.
15        int powerOf3 = pow(3, n - 1);
16      
17        // Memoization array to store results for states to avoid recomputation.
18        // Indexes: position in grid, previous state, remaining introverts count, remaining extroverts count.
19        int memo[m * n][powerOf3 * 3][introvertsCount + 1][extrovertsCount + 1];
20        memset(memo, -1, sizeof(memo)); // Initialize all memo values to -1.
21      
22        // Define a lambda function for depth-first search to find the solution.
23        // Parameters: current position, previous state, remaining introverts count, and remaining extroverts count.
24        function<int(int, int, int, int)> dfs = [&](int position, int previousState, int ic, int ec) {
25            // Base case: If we've filled the entire grid or have no more people to place.
26            if (position == m * n || (ic == 0 && ec == 0)) {
27                return 0;
28            }
29            // If the result for the current state is already computed, return it.
30            if (memo[position][previousState][ic][ec] != -1) {
31                return memo[position][previousState][ic][ec];
32            }
33          
34            int maxHappiness = 0;
35            // Get the states of the cell above and to the left of the current position.
36            int up = previousState / powerOf3; // State above.
37            int left = position % n == 0 ? 0 : previousState % 3; // State to the left (or 0 if at the edge).
38          
39            // Iterate through the possible states for the current position: 0 (empty), 1 (introvert), 2 (extrovert).
40            for (int i = 0; i < 3; ++i) {
41                // If we don't have enough people of the current type, skip this iteration.
42                if ((i == 1 && ic == 0) || (i == 2 && ec == 0)) {
43                    continue;
44                }
45                // Calculate new state for the next iteration.
46                int currentState = previousState % powerOf3 * 3 + i;
47                // Calculate additional happiness from neighbors.
48                int neighborHappiness = happinessScores[up][i] + happinessScores[left][i];
49                // Recur to find the happiness for the rest of the grid.
50                int restHappiness = dfs(position + 1, currentState, ic - (i == 1), ec - (i == 2));
51                // Calculate inherent happiness for the current state: 120 for introverts, 40 for extroverts, 0 for empty.
52                int currentHappiness = i == 1 ? 120 : (i == 2 ? 40 : 0);
53                // Maximize happiness.
54                maxHappiness = max(maxHappiness, neighborHappiness + restHappiness + currentHappiness);
55            }
56            // Store the computed max happiness for the current state in memo array.
57            return memo[position][previousState][ic][ec] = maxHappiness;
58        };
59      
60        // Begin the DFS traversal from position 0 (start of the grid) with all counts of introverts and extroverts. 
61        return dfs(0, 0, introvertsCount, extrovertsCount);
62    }
63};
64

1function getMaxGridHappiness(m: number, n: number, introvertsCount: number, extrovertsCount: number): number {
2    // Constants for maintaining happiness values.
3    const offset = 3 ** (n - 1);
4    const happinessValues: number[][] = [
5        [0, 0, 0],
6        [0, -60, -10],
7        [0, -10, 40],
8    ];
9  
10    // Memoization table for dynamic programming.
11    const memo: number[][][][] = Array(m * n)
12        .fill(0)
13        .map(() =>
14            Array(offset * 3)
15                .fill(0)
16                .map(() =>
17                    Array(introvertsCount + 1)
18                        .fill(0)
19                        .map(() => Array(extrovertsCount + 1).fill(-1)),
20                ),
21        );
22  
23    // Depth-First Search (recursive helper method) with memoization.
24    const depthFirstSearch = (position: number, previousState: number, introverts: number, extroverts: number): number => {
25        // Base cases.
26        if (position === m * n || (introverts === 0 && extroverts === 0)) {
27            return 0;
28        }
29        // Use memoized results if available.
30        if (memo[position][previousState][introverts][extroverts] !== -1) {
31            return memo[position][previousState][introverts][extroverts];
32        }
33      
34        let maxHappiness = 0;
35        const upper = Math.floor(previousState / offset);
36        const left = position % n == 0 ? 0 : previousState % 3;
37        // Iterate over three states: 0-empty, 1-introvert, and 2-extrovert.
38        for (let state = 0; state < 3; ++state) {
39            // Skip state if there are no remaining people of that type.
40            if ((state === 1 && introverts === 0) || (state === 2 && extroverts === 0)) {
41                continue;
42            }
43            const currentState = (previousState % offset) * 3 + state;
44            const upperLeftHappiness = happinessValues[upper][state] + happinessValues[left][state];
45            const remainingIntroverts = state === 1 ? introverts - 1 : introverts;
46            const remainingExtroverts = state === 2 ? extroverts - 1 : extroverts;
47            const happinessFromNext = depthFirstSearch(position + 1, currentState, remainingIntroverts, remainingExtroverts);
48            const stateHappiness = state === 1 ? 120 : state === 2 ? 40 : 0;
49            maxHappiness = Math.max(maxHappiness, upperLeftHappiness + happinessFromNext + stateHappiness);
50        }
51      
52        // Update and return the memoization table value.
53        memo[position][previousState][introverts][extroverts] = maxHappiness;
54        return maxHappiness;
55    };
56  
57    // Start the DFS from the initial state.
58    return depthFirstSearch(0, 0, introvertsCount, extrovertsCount);
59}
60

Time and Space Complexity

The given Python code uses dynamic programming with memoization to solve the problem of maximizing grid happiness. The time and space complexity of the code are derived primarily from the number of states that need to be memorized and the depth of recursion.

Time Complexity:

The time complexity of the algorithm is determined by the number of possible states which is a function of the grid dimensions (m and n), the number of introverts (ic), and the number of extroverts (ec). Each cell of the grid has three states: empty (0), occupied by an introvert (1), or occupied by an extrovert (2). Therefore, for each cell, there are 3 potential states.

Since we have n columns, the immediate previous state of a row can be represented using 3^n. For each position, we can either place an introvert, an extrovert, or leave it empty. That leads to 3 possible actions except for the cases where there are no more introverts or extroverts to place.

Consequently, the total number of states to consider is O(m*n*3^n*ic*ec). For each state, we check up to 3 possible placements (excluding the cases where we cannot place anything due to the lack of people), so the overall time complexity becomes O(3 * m * n * 3^n * ic * ec), which simplifies to O(m * n * 3^(n+1) * ic * ec).

Space Complexity:

The space complexity mainly comes from the cache used for memoization. The dfs function is memoized and stores results for each state defined by the position (pos), the previous state configuration (pre), the number of remaining introverts (ic), and the number of remaining extroverts (ec). Each unique combination of these values represents a state in the cache.

The cache will store results for every position in the grid (m * n), all configurations of the previous row (3^n), and all possible counts of introverts and extroverts (ic * ec). Therefore, the space complexity is O(m * n * 3^n * ic * ec) due to the memoization cache.

It should be noted that the dfs function itself has a limited call stack depth, since it only recurses to a depth of m * n, which doesn't significantly contribute to the space complexity in comparison to the memoization cache.

To conclude, the overall time complexity of the code is O(m * n * 3^(n+1) * ic * ec) and the space complexity is O(m * n * 3^n * ic * ec).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know