Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1659. Maximize Grid Happiness - Leetcode Solution

Problem Description

The Maximize Grid Happiness problem asks you to fill an m x n grid with two types of people: introverts and extroverts. Each cell can be empty or contain one person (either introvert or extrovert). There are introvertsCount introverts and extrovertsCount extroverts available.

The goal is to place these people in the grid to maximize the total happiness. Happiness is calculated as follows:

  • Each introvert starts with 120 happiness, extrovert with 40.
  • For each neighbor (up, down, left, right):
    • If an introvert has a neighbor, their happiness decreases by 30.
    • If an extrovert has a neighbor, their happiness increases by 20.
    • Neighbors are affected too: introverts lose 30 happiness, extroverts gain 20.
Constraints:
  • You cannot place more than introvertsCount introverts or extrovertsCount extroverts.
  • Each cell can have at most one person.
  • Return the maximum total happiness achievable.

Thought Process

At first glance, this problem seems to invite brute-force: try all possible placements of introverts and extroverts in the grid, compute the happiness, and pick the best. However, the number of possibilities grows exponentially with the grid size and the number of people, making brute-force infeasible.

Instead, we look for patterns and optimizations:

  • Happiness only depends on neighbors—so the effect of a placement is local.
  • We need to avoid recalculating the same subproblems—dynamic programming (DP) is a good fit.
  • We can represent the state of each row as a number or tuple, so we can cache DP results.
The challenge is to encode the grid state efficiently and reuse overlapping subproblems.

Solution Approach

We solve the problem using dynamic programming with state compression. Here’s how:

  1. State Representation:
    • At each cell, we need to know the previous row’s state (for the cell above) and the current row’s state so far (for the cell to the left).
    • We encode a row’s state as a base-3 number: 0 = empty, 1 = introvert, 2 = extrovert. For an n-column grid, a row’s state is an n-digit base-3 number.
  2. DP Parameters:
    • pos: Current cell index (flattened from 2D to 1D).
    • mask: Encoded state of the previous row.
    • in_left: Introverts left to place.
    • ex_left: Extroverts left to place.
  3. Transitions:
    • At each cell, try placing nothing, an introvert, or an extrovert (if available).
    • Compute the happiness gained or lost by this placement, considering only the left and up neighbors (since right and down haven’t been filled yet).
    • Update the row state for the next cell, and recurse.
  4. Memoization:
    • Cache results using the tuple (pos, mask, in_left, ex_left) to avoid redundant calculations.
  5. Base Case:
    • When all cells are filled or no people are left, return 0.

This approach ensures we only compute each unique subproblem once.

Example Walkthrough

Suppose m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2. The grid is 2 rows x 3 columns.

  1. Start at cell (0, 0). Try:
    • Leave empty: move to (0, 1), people counts unchanged.
    • Place introvert: introverts left = 0, extroverts left = 2. Add 120 happiness.
    • Place extrovert: introverts left = 1, extroverts left = 1. Add 40 happiness.
  2. For each move, proceed to next cell (0, 1), considering the effect of the left neighbor (cell (0, 0)), and so on.
  3. When moving to row 1, the mask encodes the previous row’s placements, so we can compute the effect of the cell above.
  4. Continue until all cells are filled or all people are placed. At each step, memoize the result.
  5. The DP will automatically consider all valid placements and return the maximum happiness.

Time and Space Complexity

Brute-force approach: For each cell, there are up to 3 choices (empty, introvert, extrovert), so the total number of configurations is 3^(m*n). This is infeasible for even moderate grid sizes.

Optimized DP approach:

  • There are m * n positions.
  • The mask for each row can have 3^n possible values.
  • There are up to introvertsCount + 1 and extrovertsCount + 1 possible remaining people counts.

So, the total number of DP states is m * n * 3^n * (introvertsCount + 1) * (extrovertsCount + 1). For small grids and counts, this is tractable.

Time Complexity: O(m * n * 3^n * introvertsCount * extrovertsCount)
Space Complexity: O(3^n * introvertsCount * extrovertsCount) for memoization.

Summary

The Maximize Grid Happiness problem is a classic example of using dynamic programming with state compression to efficiently explore a huge solution space. By encoding the state of each row and carefully considering only local neighbor effects, we can avoid redundant calculations and find the optimal arrangement. The key insight is to recognize overlapping subproblems and use memoization, turning an exponential brute-force search into a manageable computation.

Code Implementation

from functools import lru_cache

class Solution:
    def getMaxGridHappiness(self, m, n, introvertsCount, extrovertsCount):
        N = n
        # Precompute happiness effects
        H = [0, 120, 40]  # 0: empty, 1: introvert, 2: extrovert
        neighbor = [[0, 0, 0],
                    [0, -30, 20],
                    [0, 20, 20]]

        @lru_cache(maxsize=None)
        def dp(pos, mask, in_left, ex_left):
            if pos == m * n or (in_left == 0 and ex_left == 0):
                return 0
            row, col = divmod(pos, N)
            res = dp(pos + 1, (mask * 3) % (3 ** N), in_left, ex_left)  # empty

            for t, left in ((1, in_left), (2, ex_left)):
                if left:
                    up = (mask // (3 ** (N - 1))) if col == 0 else (mask // (3 ** (N - col - 1))) % 3
                    left_cell = (mask // (3 ** (N - 1))) % 3 if col > 0 else 0
                    happy = H[t]
                    # Only need to check up and left neighbors
                    if row > 0:
                        up_cell = (mask // (3 ** (N - 1))) % 3
                        happy += neighbor[t][up_cell]
                        happy += neighbor[up_cell][t]
                    if col > 0:
                        left_cell = (mask // (3 ** (N - col))) % 3
                        happy += neighbor[t][left_cell]
                        happy += neighbor[left_cell][t]
                    new_mask = ((mask % (3 ** (N - 1))) * 3 + t)
                    res = max(res, happy + dp(pos + 1, new_mask, in_left - (t == 1), ex_left - (t == 2)))
            return res

        return dp(0, 0, introvertsCount, extrovertsCount)
      
#include <vector>
#include <unordered_map>
#include <tuple>
using namespace std;

class Solution {
public:
    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        int N = n;
        vector<int> H = {0, 120, 40};
        vector<vector<int>> neighbor = {{0, 0, 0}, {0, -30, 20}, {0, 20, 20}};
        unordered_map<long long, int> memo;

        function<int(int, int, int, int)> dp = [&](int pos, int mask, int in_left, int ex_left) {
            if (pos == m * n || (in_left == 0 && ex_left == 0)) return 0;
            long long key = (((((long long)pos * 1000 + mask) * 10 + in_left) * 10) + ex_left);
            if (memo.count(key)) return memo[key];
            int row = pos / N, col = pos % N;
            int res = dp(pos + 1, (mask * 3) % (int)pow(3, N), in_left, ex_left); // empty

            for (int t = 1; t <= 2; ++t) {
                int left = (t == 1) ? in_left : ex_left;
                if (left) {
                    int happy = H[t];
                    int up_cell = (mask / (int)pow(3, N - 1)) % 3;
                    int left_cell = (col == 0) ? 0 : (mask / (int)pow(3, N - col)) % 3;
                    if (row > 0) {
                        happy += neighbor[t][up_cell];
                        happy += neighbor[up_cell][t];
                    }
                    if (col > 0) {
                        happy += neighbor[t][left_cell];
                        happy += neighbor[left_cell][t];
                    }
                    int new_mask = ((mask % (int)pow(3, N - 1)) * 3 + t);
                    res = max(res, happy + dp(pos + 1, new_mask, in_left - (t == 1), ex_left - (t == 2)));
                }
            }
            return memo[key] = res;
        };
        return dp(0, 0, introvertsCount, extrovertsCount);
    }
};
      
import java.util.*;

class Solution {
    int m, n;
    int[] H = {0, 120, 40};
    int[][] neighbor = {{0, 0, 0}, {0, -30, 20}, {0, 20, 20}};
    Map<String, Integer> memo = new HashMap<>();

    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        this.m = m;
        this.n = n;
        return dp(0, 0, introvertsCount, extrovertsCount);
    }

    int dp(int pos, int mask, int in_left, int ex_left) {
        if (pos == m * n || (in_left == 0 && ex_left == 0)) return 0;
        String key = pos + "," + mask + "," + in_left + "," + ex_left;
        if (memo.containsKey(key)) return memo.get(key);
        int row = pos / n, col = pos % n;
        int res = dp(pos + 1, (mask * 3) % (int)Math.pow(3, n), in_left, ex_left); // empty

        for (int t = 1; t <= 2; ++t) {
            int left = (t == 1) ? in_left : ex_left;
            if (left > 0) {
                int happy = H[t];
                int up_cell = (mask / (int)Math.pow(3, n - 1)) % 3;
                int left_cell = (col == 0) ? 0 : (mask / (int)Math.pow(3, n - col)) % 3;
                if (row > 0) {
                    happy += neighbor[t][up_cell];
                    happy += neighbor[up_cell][t];
                }
                if (col > 0) {
                    happy += neighbor[t][left_cell];
                    happy += neighbor[left_cell][t];
                }
                int new_mask = ((mask % (int)Math.pow(3, n - 1)) * 3 + t);
                res = Math.max(res, happy + dp(pos + 1, new_mask, in_left - (t == 1 ? 1 : 0), ex_left - (t == 2 ? 1 : 0)));
            }
        }
        memo.put(key, res);
        return res;
    }
}
      
var getMaxGridHappiness = function(m, n, introvertsCount, extrovertsCount) {
    const N = n;
    const H = [0, 120, 40];
    const neighbor = [[0, 0, 0], [0, -30, 20], [0, 20, 20]];
    const memo = new Map();

    function dp(pos, mask, in_left, ex_left) {
        if (pos === m * n || (in_left === 0 && ex_left === 0)) return 0;
        const key = [pos, mask, in_left, ex_left].join(',');
        if (memo.has(key)) return memo.get(key);
        const row = Math.floor(pos / N), col = pos % N;
        let res = dp(pos + 1, (mask * 3) % (3 ** N), in_left, ex_left); // empty

        for (let t = 1; t <= 2; ++t) {
            let left = (t === 1) ? in_left : ex_left;
            if (left > 0) {
                let happy = H[t];
                let up_cell = Math.floor(mask / (3 ** (N - 1))) % 3;
                let left_cell = (col === 0) ? 0 : Math.floor(mask / (3 ** (N - col))) % 3;
                if (row > 0) {
                    happy += neighbor[t][up_cell];
                    happy += neighbor[up_cell][t];
                }
                if (col > 0) {
                    happy += neighbor[t][left_cell];
                    happy += neighbor[left_cell][t];
                }
                let new_mask = ((mask % (3 ** (N - 1))) * 3 + t);
                res = Math.max(res, happy + dp(pos + 1, new_mask, in_left - (t === 1 ? 1 : 0), ex_left - (t === 2 ? 1 : 0)));
            }
        }
        memo.set(key, res);
        return res;
    }
    return dp(0, 0, introvertsCount, extrovertsCount);
};