LeetCode 1659 - Maximize Grid Happiness

This problem asks us to place introverts and extroverts inside an m x n grid in a way that maximizes the total happiness score. Every grid cell can either remain empty, contain one introvert, or contain one extrovert.

leetcodeharddynamic-programmingbit-manipulationmemoizationbitmask

LeetCode Problem 1659

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Bit Manipulation, Memoization, Bitmask

Solution

Problem Understanding

This problem asks us to place introverts and extroverts inside an m x n grid in a way that maximizes the total happiness score. Every grid cell can either remain empty, contain one introvert, or contain one extrovert. We are allowed to leave some people unused, so we do not necessarily have to place all introverts and extroverts.

Each type of person contributes a different base happiness value and reacts differently to neighbors:

  • An introvert starts with 120 happiness and loses 30 happiness for every adjacent neighbor.
  • An extrovert starts with 40 happiness and gains 20 happiness for every adjacent neighbor.

Neighbors are only the four directly adjacent cells: up, down, left, and right.

The important detail is that the effect of a neighboring relationship impacts both people simultaneously. For example:

  • Two introverts together:

  • First introvert loses 30

  • Second introvert loses 30

  • Total change: -60

  • Introvert next to extrovert:

  • Introvert loses 30

  • Extrovert gains 20

  • Total change: -10

  • Two extroverts together:

  • Each gains 20

  • Total change: +40

The goal is to maximize the total grid happiness after considering every occupied cell and every adjacent interaction.

The constraints are very important:

  • m, n <= 5
  • introvertsCount, extrovertsCount <= 6

A grid can contain at most 25 cells, which would normally make brute force impossible because every cell has three choices:

  • Empty
  • Introvert
  • Extrovert

That would produce 3^(m*n) possibilities. For a 5 x 5 grid, this becomes 3^25, which is astronomically large.

However, the counts of introverts and extroverts are very small, at most 6 each. This strongly suggests that a dynamic programming solution with compressed state representation is intended.

Several edge cases are important:

  • A completely empty placement may be optimal when placing additional people decreases happiness.
  • Very small grids like 1 x 1 simplify neighbor handling.
  • Narrow grids such as 1 x n or m x 1 only have horizontal or vertical neighbors.
  • Cases with only introverts or only extroverts behave very differently.
  • Neighbor effects must be counted exactly once, otherwise double counting bugs appear easily.

Approaches

Brute Force

The most direct approach is to try every possible configuration of the grid.

For each cell, we choose among:

  1. Leave empty
  2. Place an introvert
  3. Place an extrovert

After generating a complete grid configuration, we compute total happiness by evaluating all neighboring relationships.

This approach is guaranteed to find the optimal answer because it exhaustively checks every valid arrangement.

Unfortunately, it is far too slow.

For a 5 x 5 grid:

3^25 ≈ 2.8 * 10^11

Even before considering pruning or happiness calculations, this search space is impossible to explore within time limits.

Optimal Approach, Dynamic Programming with State Compression

The key insight is that when processing the grid cell by cell, the happiness contribution of the current cell only depends on:

  • The left neighbor
  • The upper neighbor

Future cells do not affect already processed cells except through local adjacency.

This means we do not need the entire grid history. We only need enough information to reconstruct the previous row and the previous cell in the current row.

We represent the state of the last n cells using base-3 encoding:

  • 0 = empty
  • 1 = introvert
  • 2 = extrovert

Since n <= 5, the number of possible row states is:

3^5 = 243

which is small enough for dynamic programming.

We process the grid left to right, top to bottom. At each cell, we try:

  • Leave empty
  • Place introvert
  • Place extrovert

For each choice, we calculate the incremental happiness change caused only by the left and upper neighbors.

Memoization ensures each state is computed once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(3^(m*n)) O(m*n) Enumerates every possible grid
Optimal O(m * n * 3^n * introvertsCount * extrovertsCount * 3) O(3^n * introvertsCount * extrovertsCount) Uses DP with ternary state compression

Algorithm Walkthrough

Step 1: Represent Grid States Using Base-3 Encoding

We encode the last n processed cells as a ternary number.

For example, if n = 3:

[empty, introvert, extrovert]
= [0,1,2]
= 0 * 3^2 + 1 * 3 + 2
= 5

This compressed representation lets us store row history efficiently.

Step 2: Process Cells Sequentially

We process cells in row-major order:

(0,0) -> (0,1) -> ... -> (m-1,n-1)

At each step, we know:

  • Current cell index
  • Remaining introverts
  • Remaining extroverts
  • Encoded previous state

These values fully define the subproblem.

Step 3: Extract Neighbor Information

From the encoded state:

  • The left neighbor is the last trit
  • The upper neighbor is the first trit

This works because the state always stores the previous n processed cells.

Step 4: Try All Possible Placements

For each cell, we consider:

  1. Leave empty
  2. Place introvert
  3. Place extrovert

If we place someone, we compute:

  • Base happiness
  • Interaction with left neighbor
  • Interaction with upper neighbor

We only compute interactions with already processed neighbors so each edge is counted exactly once.

Step 5: Update the State

To move to the next cell:

  1. Remove the oldest trit
  2. Shift left in base 3
  3. Append the current cell type

Mathematically:

new_state = (old_state % (3^(n-1))) * 3 + current_type

Step 6: Use Memoization

Many states repeat during recursion.

We memoize:

(position, introverts_left, extroverts_left, state)

This transforms exponential brute force into manageable dynamic programming.

Why it works

The algorithm works because the happiness contribution of a cell only depends on adjacent cells. When processing left to right and top to bottom, the only already-determined neighbors are the left and upper cells. Therefore, the previous n cells contain all information needed to compute future decisions optimally.

The DP explores every valid placement combination while avoiding recomputation through memoization, guaranteeing the maximum possible happiness.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def getMaxGridHappiness(
        self,
        m: int,
        n: int,
        introvertsCount: int,
        extrovertsCount: int
    ) -> int:

        pow3 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow3[i] = pow3[i - 1] * 3

        # Happiness interaction table
        # 0 = empty
        # 1 = introvert
        # 2 = extrovert
        interaction = [
            [0, 0, 0],
            [0, -60, -10],
            [0, -10, 40]
        ]

        @lru_cache(None)
        def dp(
            pos: int,
            introverts_left: int,
            extroverts_left: int,
            state: int
        ) -> int:

            if pos == m * n:
                return 0

            row = pos // n
            col = pos % n

            left = state % 3
            up = state // pow3[n - 1]

            next_state_base = (state % pow3[n - 1]) * 3

            best = dp(
                pos + 1,
                introverts_left,
                extroverts_left,
                next_state_base
            )

            # Place introvert
            if introverts_left > 0:
                gain = 120

                if col > 0:
                    gain += interaction[1][left]

                if row > 0:
                    gain += interaction[1][up]

                best = max(
                    best,
                    gain + dp(
                        pos + 1,
                        introverts_left - 1,
                        extroverts_left,
                        next_state_base + 1
                    )
                )

            # Place extrovert
            if extroverts_left > 0:
                gain = 40

                if col > 0:
                    gain += interaction[2][left]

                if row > 0:
                    gain += interaction[2][up]

                best = max(
                    best,
                    gain + dp(
                        pos + 1,
                        introverts_left,
                        extroverts_left - 1,
                        next_state_base + 2
                    )
                )

            return best

        return dp(0, introvertsCount, extrovertsCount, 0)

The implementation begins by precomputing powers of 3, which are used for ternary state manipulation. Since the row width is at most 5, this remains very small.

The interaction matrix stores total happiness changes caused by neighboring pairs. For example:

interaction[1][1] = -60

because two introverts each lose 30.

The recursive dp function represents the maximum achievable happiness from the current position onward.

The encoded state stores the previous n cells. Using modulo and division operations, we extract:

  • Left neighbor
  • Upper neighbor

For every cell, we try all valid actions:

  • Skip
  • Place introvert
  • Place extrovert

When placing a person, we compute the local happiness contribution immediately.

The state transition removes the oldest cell and appends the current choice, maintaining a sliding window of the last n processed cells.

Memoization avoids recomputation of identical subproblems.

Go Solution

package main

func getMaxGridHappiness(m int, n int, introvertsCount int, extrovertsCount int) int {
	pow3 := make([]int, n+1)
	pow3[0] = 1

	for i := 1; i <= n; i++ {
		pow3[i] = pow3[i-1] * 3
	}

	interaction := [][]int{
		{0, 0, 0},
		{0, -60, -10},
		{0, -10, 40},
	}

	type State struct {
		pos              int
		introvertsLeft   int
		extrovertsLeft   int
		mask             int
	}

	memo := make(map[State]int)

	var dp func(int, int, int, int) int

	dp = func(pos int, introvertsLeft int, extrovertsLeft int, mask int) int {
		if pos == m*n {
			return 0
		}

		key := State{
			pos,
			introvertsLeft,
			extrovertsLeft,
			mask,
		}

		if val, exists := memo[key]; exists {
			return val
		}

		row := pos / n
		col := pos % n

		left := mask % 3
		up := mask / pow3[n-1]

		nextMaskBase := (mask % pow3[n-1]) * 3

		best := dp(
			pos+1,
			introvertsLeft,
			extrovertsLeft,
			nextMaskBase,
		)

		if introvertsLeft > 0 {
			gain := 120

			if col > 0 {
				gain += interaction[1][left]
			}

			if row > 0 {
				gain += interaction[1][up]
			}

			candidate := gain + dp(
				pos+1,
				introvertsLeft-1,
				extrovertsLeft,
				nextMaskBase+1,
			)

			if candidate > best {
				best = candidate
			}
		}

		if extrovertsLeft > 0 {
			gain := 40

			if col > 0 {
				gain += interaction[2][left]
			}

			if row > 0 {
				gain += interaction[2][up]
			}

			candidate := gain + dp(
				pos+1,
				introvertsLeft,
				extrovertsLeft-1,
				nextMaskBase+2,
			)

			if candidate > best {
				best = candidate
			}
		}

		memo[key] = best
		return best
	}

	return dp(0, introvertsCount, extrovertsCount, 0)
}

The Go implementation follows the same logic as the Python solution but uses a custom struct as the memoization key because Go does not provide built-in tuple hashing.

A map[State]int stores cached DP results. Since all state fields are integers, the struct is hashable and efficient.

Go integers are sufficient because the maximum happiness value remains well within 32-bit range.

Worked Examples

Example 1

Input:
m = 2
n = 3
introvertsCount = 1
extrovertsCount = 2

The algorithm starts at position 0.

Initial State

Variable Value
pos 0
introverts_left 1
extroverts_left 2
state 0

At (0,0) we try:

  • Empty
  • Introvert
  • Extrovert

Placing an introvert gives:

gain = 120

No neighbors exist.

New state becomes:

001(base3)

Next, at (0,1):

  • Left neighbor is introvert
  • Upper neighbor does not exist

Trying extrovert:

base = 40
interaction with introvert = -10
total gain = 30

The recursion continues exploring all possibilities.

Eventually, the best configuration becomes:

I . E
. . E

Happiness Calculation

Person Base Neighbor Effect Total
Introvert 120 0 120
Extrovert 40 +20 60
Extrovert 40 +20 60

Final answer:

120 + 60 + 60 = 240

Example 2

Input:
m = 3
n = 1
introvertsCount = 2
extrovertsCount = 1

Since the grid has one column, only vertical interactions matter.

Optimal placement:

I
E
I

Happiness Breakdown

Person Base Neighbor Adjustment Total
Introvert 120 -30 90
Extrovert 40 +40 80
Introvert 120 -30 90

Total:

90 + 80 + 90 = 260

Example 3

Input:
m = 2
n = 2
introvertsCount = 4
extrovertsCount = 0

All people are introverts.

Every adjacent introvert pair reduces total happiness by 60.

Optimal placement avoids overcrowding as much as possible.

Maximum achievable happiness:

240

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * 3^n * introvertsCount * extrovertsCount * 3) DP states multiplied by three placement choices
Space O(m * n * 3^n * introvertsCount * extrovertsCount) Memoization table size

The number of DP states is bounded by:

positions * introverts * extroverts * states

where:

  • positions <= 25
  • introverts <= 6
  • extroverts <= 6
  • states <= 3^5 = 243

This keeps the total state space manageable.

Test Cases

sol = Solution()

# Provided examples
assert sol.getMaxGridHappiness(2, 3, 1, 2) == 240  # example 1
assert sol.getMaxGridHappiness(3, 1, 2, 1) == 260  # example 2
assert sol.getMaxGridHappiness(2, 2, 4, 0) == 240  # example 3

# Single cell cases
assert sol.getMaxGridHappiness(1, 1, 1, 0) == 120  # one introvert
assert sol.getMaxGridHappiness(1, 1, 0, 1) == 40   # one extrovert
assert sol.getMaxGridHappiness(1, 1, 0, 0) == 0    # empty grid

# No people available
assert sol.getMaxGridHappiness(5, 5, 0, 0) == 0  # completely empty

# Only extroverts
assert sol.getMaxGridHappiness(1, 2, 0, 2) == 120  # two adjacent extroverts

# Narrow grid
assert sol.getMaxGridHappiness(1, 5, 2, 2) >= 0  # single row handling

# Tall grid
assert sol.getMaxGridHappiness(5, 1, 2, 2) >= 0  # single column handling

# Maximum counts
assert sol.getMaxGridHappiness(5, 5, 6, 6) > 0  # stress test

# Introverts should avoid adjacency
assert sol.getMaxGridHappiness(1, 2, 2, 0) == 180  # 120+120-60

# Mixed interaction
assert sol.getMaxGridHappiness(1, 2, 1, 1) == 150  # 120+40-10

Test Summary

Test Why
(2,3,1,2) Validates standard mixed placement
(3,1,2,1) Tests single-column interactions
(2,2,4,0) Tests dense introvert placement
(1,1,1,0) Smallest introvert case
(1,1,0,1) Smallest extrovert case
(1,1,0,0) Empty configuration
(5,5,0,0) No people available
(1,2,0,2) Positive extrovert interaction
(1,5,2,2) Single-row handling
(5,1,2,2) Single-column handling
(5,5,6,6) Maximum constraint stress test
(1,2,2,0) Introvert adjacency penalty
(1,2,1,1) Mixed neighbor interaction

Edge Cases

One important edge case occurs when no people are available. In this situation, the optimal answer is simply 0. A buggy implementation might still attempt transitions or compute neighbor interactions unnecessarily. This implementation handles the case naturally because the recursion can only choose the empty placement option.

Another tricky case involves very small grids such as 1 x 1. In these grids, no neighbors exist, so no interaction penalties or bonuses should be applied. The implementation correctly checks row > 0 and col > 0 before evaluating upper or left neighbors.

Single-row and single-column grids are another common source of bugs. In a 1 x n grid, there are no upper neighbors. In an m x 1 grid, there are no left neighbors. Because the algorithm explicitly guards neighbor checks with row and column conditions, it correctly handles these degenerate dimensions.

A subtle issue arises with double counting neighbor effects. If both cells independently apply interaction updates later, the total happiness becomes incorrect. This implementation avoids that by only evaluating interactions with already processed neighbors, specifically the left and upper cells. Every adjacent pair is counted exactly once.

Finally, cases with many introverts can produce situations where leaving cells empty is better than placing additional people. Since the DP always includes the option to skip a cell, the algorithm naturally discovers when partial placement yields a higher total happiness.