Maximize Grid Happiness
HardPrompt
You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. There are introvertsCount introverts and extrovertsCount extroverts.
You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid.
The happiness of each person is calculated as follows:
- Introverts start with
120happiness and lose30happiness for each neighbor (introvert or extrovert). - Extroverts start with
40happiness and gain20happiness for each neighbor (introvert or extrovert).
Neighbors live in the directly adjacent cells north, east, south, and west of a person's cell.
The grid happiness is the sum of each person's happiness. Return the maximum possible grid happiness.
Example 1:
Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
Output: 240
Explanation: Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.Example 2:
Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
Output: 260
Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.Example 3:
Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
Output: 240
Constraints:
1 <= m, n <= 50 <= introvertsCount, extrovertsCount <= min(m * n, 6)
Approaches
3 approaches with complexity analysis and trade-offs.
A straightforward but highly inefficient approach is to use simple backtracking. We can explore every possible arrangement of introverts, extroverts, and empty cells on the grid. A recursive function can be used to fill the grid cell by cell. For each cell, we try to place nothing, an introvert, or an extrovert (if available). Once the entire grid is filled, we calculate its total happiness and compare it with the maximum happiness found so far.
Algorithm
- Define a recursive function, say
backtrack(row, col, introverts_left, extroverts_left, current_grid). - The base case for the recursion is when all cells are filled (e.g.,
row == m). At this point, calculate the total happiness of thecurrent_gridand update the global maximum happiness found so far. - In the recursive step, for the current cell
(row, col), explore three possibilities:- Place an empty cell: Recurse for the next cell
(row, col+1)with the same number of introverts and extroverts left. - Place an introvert (if
introverts_left > 0): Place an introvert incurrent_grid[row][col], and recurse for the next cell withintroverts_left - 1. - Place an extrovert (if
extroverts_left > 0): Place an extrovert incurrent_grid[row][col], and recurse for the next cell withextroverts_left - 1.
- Place an empty cell: Recurse for the next cell
- After each recursive call, backtrack by resetting the cell
(row, col)to its previous state to explore other possibilities. - The initial call would be
backtrack(0, 0, introvertsCount, extrovertsCount, empty_grid).
Walkthrough
This method systematically explores all valid placements. We define a recursive function that tries to fill the grid one cell at a time, say, in row-major order. The state of our recursion would be the current cell's coordinates (row, col), the number of remaining introverts and extroverts, and the grid itself.
For each cell, we have three choices:
- Leave it empty.
- Place an introvert, if we have any left.
- Place an extrovert, if we have any left.
After making a choice, we recursively call the function for the next cell. When we have considered all cells (i.e., reached the end of the grid), we compute the total happiness for the generated configuration. This involves iterating through the grid, and for each person, calculating their happiness based on their neighbors. The maximum happiness over all configurations is our answer.
class Solution { int maxHappiness = 0; public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { int[][] grid = new int[m][n]; backtrack(0, 0, introvertsCount, extrovertsCount, grid, m, n); return maxHappiness; } private void backtrack(int r, int c, int iCount, int eCount, int[][] grid, int m, int n) { if (r == m) { maxHappiness = Math.max(maxHappiness, calculateHappiness(grid, m, n)); return; } int nextR = (c == n - 1) ? r + 1 : r; int nextC = (c == n - 1) ? 0 : c + 1; // Choice 1: Empty cell grid[r][c] = 0; backtrack(nextR, nextC, iCount, eCount, grid, m, n); // Choice 2: Place introvert if (iCount > 0) { grid[r][c] = 1; backtrack(nextR, nextC, iCount - 1, eCount, grid, m, n); } // Choice 3: Place extrovert if (eCount > 0) { grid[r][c] = 2; backtrack(nextR, nextC, iCount, eCount - 1, grid, m, n); } // Backtrack grid[r][c] = 0; } private int calculateHappiness(int[][] grid, int m, int n) { int totalHappiness = 0; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (grid[r][c] == 0) continue; int neighbors = 0; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) { neighbors++; } } if (grid[r][c] == 1) { // Introvert totalHappiness += 120 - 30 * neighbors; } else { // Extrovert totalHappiness += 40 + 20 * neighbors; } } } return totalHappiness; }}Complexity
Time
O(3^(m*n) * m * n). The recursion tree can have up to 3^(m*n) leaves, and for each complete configuration, we spend O(m*n) to calculate happiness. This is too slow for the given constraints.
Space
O(m * n) for the recursion stack depth and storing the grid.
Trade-offs
Pros
Simple to understand and implement.
Correctly explores the entire search space.
Cons
Extremely inefficient due to the large number of states explored.
Recalculates solutions for the same subproblems repeatedly, as it lacks memoization.
The time complexity is prohibitively high for the given constraints.
A better approach is to use dynamic programming. We can process the grid row by row. The state of our DP would need to include the current row index, the number of introverts and extroverts remaining, and information about the previous row to calculate happiness from vertical interactions. This information about the previous row can be encoded as a mask.
Algorithm
- The state for our DP can be
dp(row, introverts_left, extroverts_left, prev_row_mask). - This function returns the maximum happiness for the subgrid from
rowtom-1, given the number of people left to place and the configuration of the previous row (row-1). - The
prev_row_maskis a ternary number of lengthn, where each digit represents an empty cell (0), an introvert (1), or an extrovert (2). - The base case is
row == m, which means we've filled the grid, so we return 0. - In the transition, to compute
dp(row, i_left, e_left, prev_mask), we iterate through all3^npossible masks for the currentrow(current_mask). - For each
current_mask, we find the number of introverts (i_used) and extroverts (e_used) it contains. - If
i_used <= i_leftande_used <= e_left, we calculate the happiness generated by this row configuration, considering interactions within the row and with theprev_row_mask. - We then recursively call for the next row:
solve(row + 1, i_left - i_used, e_left - e_used, current_mask). - The result is the maximum value over all valid
current_maskchoices. - Memoization is used to store the results for each state to avoid recomputation.
Walkthrough
Let's define a DP state as dp(row, introverts_left, extroverts_left, prev_row_mask). This represents the maximum happiness we can obtain from filling the grid from row to m-1, given that we have introverts_left and extroverts_left people to place, and the row row-1 had a configuration represented by prev_row_mask.
The prev_row_mask is a base-3 integer of length n, where n is the number of columns. Each position in the ternary representation corresponds to a cell in the row and can be 0 (empty), 1 (introvert), or 2 (extrovert).
To compute the value for a state, we must decide the configuration for the current row. We can iterate through all 3^n possible masks for the current row. For each current_row_mask, we calculate:
- The number of introverts and extroverts it uses.
- The happiness generated within this row (horizontal interactions) and between this row and the previous one (vertical interactions, using
prev_row_mask). - We then add the result from the recursive call for the next row:
dp(row + 1, ..., current_row_mask).
The maximum value over all possible current_row_masks will be the answer for the current state. We use memoization to store and retrieve results for states (row, introverts_left, extroverts_left, prev_row_mask).
This approach is feasible but has a costly transition step. For each state, we iterate through 3^n possibilities for the current row's mask, leading to a high time complexity.
Complexity
Time
O(m * introvertsCount * extrovertsCount * 3^(2n) * n). For each of the `m * I * E * 3^n` states, the transition takes `O(3^n * n)` time because we iterate through `3^n` masks for the current row and calculate happiness in `O(n)` for each.
Space
O(m * introvertsCount * extrovertsCount * 3^n) for the memoization table. We can optimize to O(introvertsCount * extrovertsCount * 3^n) by only storing DP results for the current and next row.
Trade-offs
Pros
Significantly reduces redundant computations compared to simple backtracking by using memoization.
Systematically builds the solution row by row.
Cons
The transition is complex and slow, as it involves iterating through all possible masks for the current row.
The time complexity, while better than brute force, is still high due to the
3^(2n)factor.
The most efficient solution involves a more refined dynamic programming approach that processes the grid cell by cell. The key idea is to maintain a state that includes not just the remaining people counts but also a compact representation of the local neighborhood required for happiness calculations. This is achieved using a 'sliding mask' or 'profile DP'.
Algorithm
- To optimize, ensure
nis the smaller ofmandnby conceptually transposing the grid ifm < n. - Define a recursive function with memoization:
solve(idx, i_left, e_left, mask). idx: The current cell index, from0tom*n-1.i_left,e_left: The number of introverts and extroverts remaining.mask: A ternary number of lengthnthat stores the types of the lastncells placed. This is a sliding window over the grid cells.- The base case is
idx == m*n, returning 0. - In the recursive step for cell
idx, we have three choices:- Empty Cell: Calculate the new mask by shifting and adding a 0. Recurse:
solve(idx + 1, i_left, e_left, new_mask). - Introvert: If
i_left > 0, calculate happiness gain. This includes the base value (120) and interaction costs with the top and left neighbors. The neighbors' types are retrieved from themask. Recurse:gain + solve(idx + 1, i_left - 1, e_left, new_mask). - Extrovert: If
e_left > 0, do similarly. Base value is 40, and interactions provide gains. Recurse:gain + solve(idx + 1, i_left, e_left - 1, new_mask).
- Empty Cell: Calculate the new mask by shifting and adding a 0. Recurse:
- The
maskmakes fetching neighbor information efficient. The top neighbor (idx-n) and left neighbor (idx-1) are at fixed positions in the mask's ternary representation. - The result for the state is the maximum of the outcomes of these choices. Memoize the result.
Walkthrough
We can define a DP state as dp(idx, introverts_left, extroverts_left, mask), which represents the maximum happiness from cell idx to the end of the grid. Here, idx is the cell index from 0 to m*n-1.
The crucial part is the mask. It's a ternary (base-3) integer of length n (the number of columns) that encodes the state of the boundary between processed and unprocessed cells. Specifically, when we are at cell idx, the mask stores the types of people in the last n cells, i.e., cells idx-n, idx-n+1, ..., idx-1. This sliding window mask allows us to retrieve the types of the top neighbor (idx-n) and the left neighbor (idx-1) in constant time.
For each cell idx, we explore three choices:
- Place an empty cell (type 0): The happiness gain is 0. We recurse for
idx+1. - Place an introvert (type 1): If we have introverts left, we calculate the happiness gain. This is
120plus the interaction happiness with the top and left neighbors (whose types are derived from themask). Then we recurse foridx+1. - Place an extrovert (type 2): Similar to the introvert, but with a base happiness of
40.
When we move from idx to idx+1, the mask is updated by shifting its bits and adding the type of the person placed at idx. This maintains the sliding window property. The final answer is the result of the initial call solve(0, introvertsCount, extrovertsCount, 0).
To optimize, we can ensure n <= m by swapping them if needed, since the complexity depends exponentially on n.
class Solution { int m, n, introvertsCount, extrovertsCount; Integer[][][][] memo; int[] p3; public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { if (m < n) { // Ensure n is the smaller dimension to optimize mask size return getMaxGridHappiness(n, m, introvertsCount, extrovertsCount); } this.m = m; this.n = n; this.introvertsCount = introvertsCount; this.extrovertsCount = extrovertsCount; p3 = new int[n + 1]; p3[0] = 1; for (int i = 1; i <= n; i++) p3[i] = p3[i - 1] * 3; memo = new Integer[m * n][introvertsCount + 1][extrovertsCount + 1][p3[n]]; return solve(0, introvertsCount, extrovertsCount, 0); } private int solve(int idx, int iLeft, int eLeft, int mask) { if (idx == m * n) return 0; if (memo[idx][iLeft][eLeft][mask] != null) return memo[idx][iLeft][eLeft][mask]; int r = idx / n, c = idx % n; int upType = mask / p3[n - 1]; int leftType = (c == 0) ? 0 : (mask % 3); // Choice 1: Empty cell int newMask = (mask % p3[n - 1]) * 3; int res = solve(idx + 1, iLeft, eLeft, newMask); // Choice 2: Place introvert if (iLeft > 0) { int happinessGain = 120 + calculateInteraction(1, upType) + calculateInteraction(1, leftType); res = Math.max(res, happinessGain + solve(idx + 1, iLeft - 1, eLeft, newMask + 1)); } // Choice 3: Place extrovert if (eLeft > 0) { int happinessGain = 40 + calculateInteraction(2, upType) + calculateInteraction(2, leftType); res = Math.max(res, happinessGain + solve(idx + 1, iLeft, eLeft - 1, newMask + 2)); } return memo[idx][iLeft][eLeft][mask] = res; } private int calculateInteraction(int p1, int p2) { if (p1 == 0 || p2 == 0) return 0; int val = 0; // Interaction from p1's perspective if (p1 == 1) val -= 30; else val += 20; // Interaction from p2's perspective if (p2 == 1) val -= 30; else val += 20; return val; }}Complexity
Time
O(m * n * introvertsCount * extrovertsCount * 3^n). There are `m*n * I * E * 3^n` states, and each state transition takes constant time.
Space
O(m * n * introvertsCount * extrovertsCount * 3^n) for the memoization table.
Trade-offs
Pros
Most efficient approach for the given constraints.
The state transition is O(1), making it much faster than the row-by-row DP.
The sliding mask elegantly captures all necessary information from the past.
Cons
The state representation with a sliding mask can be complex to reason about and implement correctly.
The space complexity can still be large, though feasible for the given constraints.
Solutions
Solution
class Solution {private int m;private int mx;private int[] f;private int[][] g;private int[][] bits;private int[] ix;private int[] ex;private Integer[][][][] memo;private final int[][] h = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}};public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { this.m = m; mx = (int)Math.pow(3, n); f = new int[mx]; g = new int[mx][mx]; bits = new int[mx][n]; ix = new int[mx]; ex = new int[mx]; memo = new Integer[m][mx][introvertsCount + 1][extrovertsCount + 1]; for (int i = 0; i < mx; ++i) { int mask = i; for (int j = 0; j < n; ++j) { int x = mask % 3; mask /= 3; bits[i][j] = x; if (x == 1) { ix[i]++; f[i] += 120; } else if (x == 2) { ex[i]++; f[i] += 40; } if (j > 0) { f[i] += h[x][bits[i][j - 1]]; } } } for (int i = 0; i < mx; ++i) { for (int j = 0; j < mx; ++j) { for (int k = 0; k < n; ++k) { g[i][j] += h[bits[i][k]][bits[j][k]]; } } } return dfs(0, 0, introvertsCount, extrovertsCount); }private int dfs(int i, int pre, int ic, int ec) { if (i == m || (ic == 0 && ec == 0)) { return 0; } if (memo[i][pre][ic][ec] != null) { return memo[i][pre][ic][ec]; } int ans = 0; for (int cur = 0; cur < mx; ++cur) { if (ix[cur] <= ic && ex[cur] <= ec) { ans = Math.max(ans, f[cur] + g[pre][cur] + dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])); } } return memo[i][pre][ic][ec] = ans; }}class Solution {public: int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { int mx = pow(3, n); int f[mx]; int g[mx][mx]; int bits[mx][n]; int ix[mx]; int ex[mx]; int memo[m][mx][introvertsCount + 1][extrovertsCount + 1]; int h[3][3] = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}}; memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); memset(bits, 0, sizeof(bits)); memset(ix, 0, sizeof(ix)); memset(ex, 0, sizeof(ex)); memset(memo, -1, sizeof(memo)); for (int i = 0; i < mx; ++i) { int mask = i; for (int j = 0; j < n; ++j) { int x = mask % 3; mask /= 3; bits[i][j] = x; if (x == 1) { ix[i]++; f[i] += 120; } else if (x == 2) { ex[i]++; f[i] += 40; } if (j) { f[i] += h[x][bits[i][j - 1]]; } } } for (int i = 0; i < mx; ++i) { for (int j = 0; j < mx; ++j) { for (int k = 0; k < n; ++k) { g[i][j] += h[bits[i][k]][bits[j][k]]; } } } function<int(int, int, int, int)> dfs = [&](int i, int pre, int ic, int ec) { if (i == m || (ic == 0 && ec == 0)) { return 0; } if (memo[i][pre][ic][ec] != -1) { return memo[i][pre][ic][ec]; } int ans = 0; for (int cur = 0; cur < mx; ++cur) { if (ix[cur] <= ic && ex[cur] <= ec) { ans = max(ans, f[cur] + g[pre][cur] + dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])); } } return memo[i][pre][ic][ec] = ans; }; return dfs(0, 0, introvertsCount, extrovertsCount); }};class Solution: def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int: @ cache def dfs(i: int, pre: int, ic: int, ec: int) -> int: if i == m or (ic == 0 and ec == 0): return 0 ans = 0 for cur in range(mx): if ix[cur] <= ic and ex[cur] <= ec: a = f[cur] + g[pre][cur] b = dfs(i + 1, cur, ic - ix[cur], ec - ex[cur]) ans = max(ans, a + b) return ans mx = pow(3, n) f = [0] * mx g = [[0] * mx for _ in range(mx)] h = [[0, 0, 0], [0, - 60, - 10], [0, - 10, 40]] bits = [[0] * n for _ in range(mx)] ix = [0] * mx ex = [0] * mx for i in range(mx): mask = i for j in range(n): mask, x = divmod(mask, 3) bits[i][j] = x if x == 1: ix[i] += 1 f[i] += 120 elif x == 2: ex[i] += 1 f[i] += 40 if j: f[i] += h[x][bits[i][j - 1]] for i in range(mx): for j in range(mx): for k in range(n): g[i][j] += h[bits[i][k]][bits[j][k]] return dfs(0, 0, introvertsCount, extrovertsCount)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.