1659. Maximize Grid Happiness
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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
@cachedecorator is used to memorize the results of previous states, which means oncedfs(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
preparameter 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). Thefor 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-10for the introvert and+20for the extrovert. -
Base Case: If
posequalsm * nor bothic(introvert count) andec(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 callingdfsand 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.
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?
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
dfsfunction begins at positionpos = 0(the top-left cell), with a base case that ifposis equal to the number of cells (m*n, which is 4 in our case) or bothicandecare 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 loopfor 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 stateprefor 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.
- If the cell is left empty,
-
As we call these options recursively, our
@cachedecorator 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 atpos = 1, then the happiness for each introvert is decreased by30. Conversely, placing an extrovert next to an introvert increases the extrovert's happiness by20and decreases the introvert's happiness by30. -
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
2x2grid will have been explored, and the maximalansvalue 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
601class 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}
531#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};
641function 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}
60Which of the following uses divide and conquer strategy?
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.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
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 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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.