Maximize Grid Happiness

Maximize Grid Happiness

What is this problem about?

This is a highly complex constraint satisfaction problem. You are given an $M \times N$ grid, and a specific number of "introverts" and "extroverts". You need to place them into the grid. Introverts gain base happiness but lose happiness for every neighbor they touch. Extroverts gain base happiness and gain extra happiness for every neighbor they touch. You want to place these people (you don't have to place all of them) to maximize the total happiness of the grid.

Why is this asked in interviews?

This is a top-tier Hard problem, typically seen in elite quant firm or senior FAANG interviews. It is the ultimate test of State-Space Search with Memoization (DP with Bitmasking). The grid is small (max $5 \times 5$), which is a massive hint that bitmasking the state of the previous row is required. It evaluates your ability to track multiple limited resources (introvert/extrovert counts) while managing 2D spatial dependencies.

Algorithmic pattern used

This utilizes Dynamic Programming with Profile Bitmasking (also known as DP on Broken Profile). You process the grid cell by cell (from left-to-right, top-to-bottom). For any cell (r, c), the happiness it brings depends only on the cell immediately to its left (r, c-1) and the cell immediately above it (r-1, c). Therefore, you only need to memorize the state of the last N cells processed. This state can be represented as a base-3 number (0 = empty, 1 = introvert, 2 = extrovert). Your recursive DFS function will pass the current index, the introverts_left, the extroverts_left, and the base3_mask of the previous N cells.

Example explanation

Imagine placing an Introvert (I) at (1, 1).

• Base happiness: +120.
• Check left neighbor (1, 0). If it's an Extrovert (E), the 'I' loses 30, and the 'E' gains 20. Net change for this border is $-30 + 20 = -10$.
• Check top neighbor (0, 1). If it's empty, no change. Total happiness for this cell placement = 110. The DP transitions try all 3 options for the current cell (Empty, I, E), calculate the local score based on the mask, update the mask by shifting out the oldest cell and shifting in the new cell, and recurse. The max score is cached in a 4D array memo[index][intro_left][extro_left][mask].

Common mistakes candidates make

The absolute most common mistake is trying to run a standard DFS/Backtracking algorithm without memoization, which instantly fails due to the $3^{25}$ state space. Another frequent error is incorrectly calculating the mutual interaction scores. If cell A touches cell B, both cells react. An introvert touching an extrovert means the introvert loses 30, but the extrovert gains 20 simultaneously.

Interview preparation tip

When dealing with the Maximize Grid Happiness coding problem or any grid problem with small dimensions ($M, N \le 6$) and neighbor dependencies, "DP with Bitmask" is the standard tool. You don't need a full 2D array for state; just an array or integer representing the immediate boundary profile. Practice converting base-3 states into integers to use as cache keys.