# Maximize Grid Happiness
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-grid-happiness)
Canonical: https://scaleengineer.com/dsa/problems/maximize-grid-happiness
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
---
## Problem
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 `120` happiness and **lose** `30` happiness for each neighbor (introvert or extrovert).
* Extroverts **start** with `40` happiness and **gain** `20` happiness 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:**

![](https://assets.glich.co/dsa/maximize-grid-happiness/image0.png) 

**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 <= 5`
* `0 <= introvertsCount, extrovertsCount <= min(m * n, 6)`

# Approaches
## Brute-Force Backtracking
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.
**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.
**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.
### Explanation
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:
1.  Leave it empty.
2.  Place an introvert, if we have any left.
3.  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.

```java
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;
    }
}
```
### 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 the `current_grid` and update the global maximum happiness found so far.
- In the recursive step, for the current cell `(row, col)`, explore three possibilities:
  1. Place an empty cell: Recurse for the next cell `(row, col+1)` with the same number of introverts and extroverts left.
  2. Place an introvert (if `introverts_left > 0`): Place an introvert in `current_grid[row][col]`, and recurse for the next cell with `introverts_left - 1`.
  3. Place an extrovert (if `extroverts_left > 0`): Place an extrovert in `current_grid[row][col]`, and recurse for the next cell with `extroverts_left - 1`.
- 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)`.

## Dynamic Programming (Row by Row)
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.
**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.
**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.
### Explanation
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:
1.  The number of introverts and extroverts it uses.
2.  The happiness generated within this row (horizontal interactions) and between this row and the previous one (vertical interactions, using `prev_row_mask`).
3.  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_mask`s 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.
### 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 `row` to `m-1`, given the number of people left to place and the configuration of the previous row (`row-1`).
- The `prev_row_mask` is a ternary number of length `n`, 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 all `3^n` possible masks for the current `row` (`current_mask`).
- For each `current_mask`, we find the number of introverts (`i_used`) and extroverts (`e_used`) it contains.
- If `i_used <= i_left` and `e_used <= e_left`, we calculate the happiness generated by this row configuration, considering interactions within the row and with the `prev_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_mask` choices.
- Memoization is used to store the results for each state to avoid recomputation.

## Dynamic Programming with Sliding Mask (Cell by Cell)
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'.
**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.
**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.
### Explanation
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:
1.  **Place an empty cell (type 0):** The happiness gain is 0. We recurse for `idx+1`.
2.  **Place an introvert (type 1):** If we have introverts left, we calculate the happiness gain. This is `120` plus the interaction happiness with the top and left neighbors (whose types are derived from the `mask`). Then we recurse for `idx+1`.
3.  **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`.

```java
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;
    }
}
```
### Algorithm
- To optimize, ensure `n` is the smaller of `m` and `n` by conceptually transposing the grid if `m < n`.
- Define a recursive function with memoization: `solve(idx, i_left, e_left, mask)`.
- `idx`: The current cell index, from `0` to `m*n-1`.
- `i_left`, `e_left`: The number of introverts and extroverts remaining.
- `mask`: A ternary number of length `n` that stores the types of the last `n` cells 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:
  1. **Empty Cell**: Calculate the new mask by shifting and adding a 0. Recurse: `solve(idx + 1, i_left, e_left, new_mask)`.
  2. **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 the `mask`. Recurse: `gain + solve(idx + 1, i_left - 1, e_left, new_mask)`.
  3. **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)`.
- The `mask` makes 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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);
  }
};

```

### Python

```python
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)

```