Facebook Pixel

1659. Maximize Grid Happiness

HardBit ManipulationMemoizationDynamic ProgrammingBitmask
Leetcode Link

Problem Description

You have an m x n grid and two types of people to potentially place in it: introverts and extroverts. You're given introvertsCount introverts and extrovertsCount extroverts available to place.

The key rules are:

  • You can choose to place any number of people (from 0 up to the total available) in the grid
  • Each person occupies exactly one cell
  • Not all cells need to be filled, and not all people need to be placed

Each person type has different happiness calculations:

  • Introverts: Start with 120 happiness points, but lose 30 points for each neighbor they have
  • Extroverts: Start with 40 happiness points and gain 20 points for each neighbor they have

Neighbors are defined as people in directly adjacent cells (up, down, left, right) - diagonal cells don't count as neighbors.

The grid happiness is the sum of all placed people's happiness values. Your goal is to find the maximum possible grid happiness by optimally choosing:

  1. How many people to place
  2. Which type of people to place
  3. Where to place them in the grid

For example, if you place an introvert with 2 neighbors, their happiness would be 120 - 30*2 = 60. If you place an extrovert with 2 neighbors, their happiness would be 40 + 20*2 = 80.

The problem asks you to return the maximum achievable grid happiness value.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The first observation is that the grid is small (m, n ≤ 5), which suggests we can use state compression techniques. Each cell has three possible states: empty (0), has an introvert (1), or has an extrovert (2). This naturally leads to thinking about representing each row's state as a ternary number.

Since we need to maximize happiness and the happiness of each person depends on their neighbors, we realize that:

  1. The happiness within a row depends on horizontal neighbors
  2. The happiness between rows depends on vertical neighbors

This suggests processing the grid row by row. When we place people in row i, we need to know what was placed in row i-1 to calculate the vertical neighbor interactions.

The key insight is that we can precompute several things:

  • f[state]: The base happiness for a given row state (considering only horizontal neighbors within that row)
  • g[state1][state2]: The happiness change when two row states are adjacent vertically

For example, if we have state [1, 0, 2] (introvert, empty, extrovert) in a row:

  • The introvert starts with 120 happiness
  • The extrovert starts with 40 happiness
  • They're not horizontal neighbors, so no interaction
  • Total base happiness for this row state is 160

When two rows are adjacent, we need to calculate the vertical interactions. If position j in the upper row has person type a and position j in the lower row has person type b, they affect each other's happiness according to a fixed pattern:

  • Introvert-Introvert: both lose 30, total change = -60
  • Introvert-Extrovert: introvert loses 30, extrovert gains 20, total change = -10
  • Extrovert-Extrovert: both gain 20, total change = 40

This leads us to dynamic programming with memoization. We process row by row, keeping track of:

  • Current row index i
  • Previous row's state pre
  • Remaining introverts ic
  • Remaining extroverts ec

For each row, we try all possible valid states (those that don't exceed our remaining people counts) and recursively solve for the rest of the grid, taking the maximum happiness achievable.

Learn more about Memoization, Dynamic Programming and Bitmask patterns.

Solution Approach

The solution uses ternary state compression combined with dynamic programming and memoization. Let's walk through the implementation step by step:

State Representation

Each row's state is represented as a ternary number where:

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

For a row of length n, there are 3^n possible states, stored in variable mx.

Preprocessing Phase

  1. Row State Information: For each possible row state i from 0 to 3^n - 1:

    • Convert the state to its ternary representation and store in bits[i]
    • Count introverts (ix[i]) and extroverts (ex[i]) in this state
    • Calculate base happiness f[i] considering only horizontal neighbors within the row

  2. Happiness Interaction Matrix: Define h[a][b] representing the happiness change when person type a is adjacent to person type b:

    h = [[0, 0, 0],      # empty adjacent to anything = 0
     [0, -60, -10],  # introvert adjacent to [empty, introvert, extrovert]
     [0, -10, 40]]   # extrovert adjacent to [empty, introvert, extrovert]

  3. Vertical Interaction Matrix: Calculate g[i][j] representing the total happiness change when row state i is placed above row state j:

    for each position k in the row:
    g[i][j] += h[bits[i][k]][bits[j][k]]

Dynamic Programming with Memoization

The main solving function dfs(i, pre, ic, ec) represents:

  • i: current row index
  • pre: previous row's state
  • ic: remaining introverts
  • ec: remaining extroverts

The recurrence relation is:

dfs(i, pre, ic, ec) = max over all valid cur states {
    f[cur] + g[pre][cur] + dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])
}

Where:

  • f[cur] is the base happiness of row state cur
  • g[pre][cur] is the vertical interaction happiness between consecutive rows
  • We recurse to the next row with updated counts

Base Cases

  1. If i == m (all rows processed), return 0
  2. If ic == 0 and ec == 0 (no people left to place), return 0

Optimization

The @cache decorator memoizes results to avoid recalculating the same states multiple times, which is crucial since there can be many overlapping subproblems.

Final Answer

The solution starts with dfs(0, 0, introvertsCount, extrovertsCount), meaning we start from row 0 with no previous row state and all people available to place.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with a 2×2 grid, 2 introverts, and 1 extrovert.

Step 1: State Representation For a row of length 2, we have 3² = 9 possible states:

  • State 0: [0,0] (empty, empty)
  • State 1: [0,1] (empty, introvert)
  • State 2: [0,2] (empty, extrovert)
  • State 3: [1,0] (introvert, empty)
  • State 4: [1,1] (introvert, introvert)
  • State 5: [1,2] (introvert, extrovert)
  • State 6: [2,0] (extrovert, empty)
  • State 7: [2,1] (extrovert, introvert)
  • State 8: [2,2] (extrovert, extrovert)

Step 2: Calculate Base Happiness f[state] For each row state, calculate happiness considering only horizontal neighbors:

  • f[0] = 0 (no people)
  • f[1] = 120 (one introvert, no neighbors)
  • f[2] = 40 (one extrovert, no neighbors)
  • f[3] = 120 (one introvert, no neighbors)
  • f[4] = 120 + 120 - 30 - 30 = 180 (two introverts, each loses 30)
  • f[5] = 120 + 40 - 30 + 20 = 150 (introvert loses 30, extrovert gains 20)
  • f[6] = 40 (one extrovert, no neighbors)
  • f[7] = 40 + 120 + 20 - 30 = 150 (extrovert gains 20, introvert loses 30)
  • f[8] = 40 + 40 + 20 + 20 = 120 (two extroverts, each gains 20)

Step 3: Calculate Vertical Interactions g[i][j] For example, g[4][5] (state [1,1] above state [1,2]):

  • Position 0: introvert above introvert → -60 happiness
  • Position 1: introvert above extrovert → -10 happiness
  • Total: g[4][5] = -70

Step 4: Dynamic Programming Starting with dfs(0, 0, 2, 1):

Row 0 choices:

  • State 0 (empty): happiness = 0 + dfs(1, 0, 2, 1)
  • State 1 (0,I): happiness = 120 + dfs(1, 1, 1, 1)
  • State 3 (I,0): happiness = 120 + dfs(1, 3, 1, 1)
  • State 4 (I,I): happiness = 180 + dfs(1, 4, 0, 1)
  • State 2 (0,E): happiness = 40 + dfs(1, 2, 2, 0)
  • State 6 (E,0): happiness = 40 + dfs(1, 6, 2, 0)

Let's trace state 4 (I,I) for row 0:

  • Base happiness: 180
  • Remaining: 0 introverts, 1 extrovert

Row 1 choices after row 0 = [I,I]:

  • State 0: 0 + 0 = 0
  • State 2 (0,E): 40 + g[4][2] = 40 + (-30) = 10
  • State 6 (E,0): 40 + g[4][6] = 40 + (-30) = 10

Best for row 1 is 10, so total = 180 + 10 = 190

After exploring all possibilities, the optimal placement might be:

Row 0: [I, I]  (state 4, happiness = 180)
Row 1: [0, E]  (state 2, happiness = 40 - 30 = 10)

Total grid happiness = 190

This demonstrates how the algorithm:

  1. Tries different row configurations
  2. Calculates horizontal interactions within rows
  3. Calculates vertical interactions between adjacent rows
  4. Tracks remaining people counts
  5. Memoizes results to avoid recalculation
  6. Returns the maximum achievable happiness

Solution Implementation

1class Solution:
2    def getMaxGridHappiness(
3        self, m: int, n: int, introvertsCount: int, extrovertsCount: int
4    ) -> int:
5        """
6        Calculate maximum grid happiness by placing introverts and extroverts.
7        Uses dynamic programming with state compression.
8      
9        Args:
10            m: Number of rows in the grid
11            n: Number of columns in the grid
12            introvertsCount: Number of introverts to place
13            extrovertsCount: Number of extroverts to place
14          
15        Returns:
16            Maximum happiness score achievable
17        """
18      
19        @cache
20        def dfs(row: int, prev_state: int, introverts_left: int, extroverts_left: int) -> int:
21            """
22            Dynamic programming function to calculate max happiness.
23          
24            Args:
25                row: Current row being processed
26                prev_state: State of the previous row (ternary representation)
27                introverts_left: Remaining introverts to place
28                extroverts_left: Remaining extroverts to place
29              
30            Returns:
31                Maximum happiness from current position onwards
32            """
33            # Base cases: reached end of grid or no people left to place
34            if row == m or (introverts_left == 0 and extroverts_left == 0):
35                return 0
36          
37            max_happiness = 0
38            # Try all possible states for current row
39            for curr_state in range(max_states):
40                # Check if we have enough people for this state
41                if introverts_in_state[curr_state] <= introverts_left and \
42                   extroverts_in_state[curr_state] <= extroverts_left:
43                    # Calculate happiness for current row + interaction with previous row
44                    current_happiness = base_happiness[curr_state] + interaction_happiness[prev_state][curr_state]
45                    # Recursively calculate happiness for remaining rows
46                    future_happiness = dfs(
47                        row + 1, 
48                        curr_state, 
49                        introverts_left - introverts_in_state[curr_state], 
50                        extroverts_left - extroverts_in_state[curr_state]
51                    )
52                    max_happiness = max(max_happiness, current_happiness + future_happiness)
53          
54            return max_happiness
55      
56        # Maximum possible states for a row (3^n: empty, introvert, extrovert)
57        max_states = 3 ** n
58      
59        # Precomputed values for efficiency
60        base_happiness = [0] * max_states  # Base happiness for each row state
61        interaction_happiness = [[0] * max_states for _ in range(max_states)]  # Interaction between adjacent rows
62      
63        # Happiness matrix for adjacent cells
64        # happiness_matrix[i][j] = happiness change when cell type i is adjacent to cell type j
65        # 0: empty, 1: introvert, 2: extrovert
66        happiness_matrix = [
67            [0, 0, 0],      # Empty cell adjacent to anything
68            [0, -60, -10],  # Introvert adjacent to [empty, introvert, extrovert]
69            [0, -10, 40]    # Extrovert adjacent to [empty, introvert, extrovert]
70        ]
71      
72        # Decode each state into cell configurations
73        state_cells = [[0] * n for _ in range(max_states)]
74        introverts_in_state = [0] * max_states
75        extroverts_in_state = [0] * max_states
76      
77        # Precompute state information
78        for state in range(max_states):
79            temp_state = state
80            for col in range(n):
81                # Extract cell type using ternary representation
82                temp_state, cell_type = divmod(temp_state, 3)
83                state_cells[state][col] = cell_type
84              
85                # Count people and calculate base happiness
86                if cell_type == 1:  # Introvert
87                    introverts_in_state[state] += 1
88                    base_happiness[state] += 120
89                elif cell_type == 2:  # Extrovert
90                    extroverts_in_state[state] += 1
91                    base_happiness[state] += 40
92              
93                # Add horizontal interaction happiness (within same row)
94                if col > 0:
95                    base_happiness[state] += happiness_matrix[cell_type][state_cells[state][col - 1]]
96      
97        # Precompute vertical interaction happiness between adjacent rows
98        for prev_state in range(max_states):
99            for curr_state in range(max_states):
100                for col in range(n):
101                    interaction_happiness[prev_state][curr_state] += \
102                        happiness_matrix[state_cells[prev_state][col]][state_cells[curr_state][col]]
103      
104        # Start DFS from first row with no previous state
105        return dfs(0, 0, introvertsCount, extrovertsCount)
106
1class Solution {
2    // Grid dimensions
3    private int rows;
4    private int maxStates;
5  
6    // Precomputed values for optimization
7    private int[] stateHappiness;           // Happiness value for each state (row configuration)
8    private int[][] adjacentStateBonus;     // Bonus/penalty for adjacent states (between rows)
9    private int[][] stateDigits;            // Digit representation of each state (0=empty, 1=introvert, 2=extrovert)
10    private int[] introvertsInState;        // Number of introverts in each state
11    private int[] extrovertsInState;        // Number of extroverts in each state
12  
13    // Memoization cache
14    private Integer[][][][] dp;
15  
16    // Happiness impact matrix: happinessImpact[person1][person2]
17    // 0=empty, 1=introvert, 2=extrovert
18    private final int[][] happinessImpact = {
19        {0, 0, 0},      // empty neighbor: no impact
20        {0, -60, -10},  // introvert: -60 with introvert, -10 with extrovert
21        {0, -10, 40}    // extrovert: -10 with introvert, +40 with extrovert
22    };
23
24    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
25        this.rows = m;
26        // Total possible states for a row (3^n: each cell can be empty/introvert/extrovert)
27        maxStates = (int) Math.pow(3, n);
28      
29        // Initialize arrays
30        stateHappiness = new int[maxStates];
31        adjacentStateBonus = new int[maxStates][maxStates];
32        stateDigits = new int[maxStates][n];
33        introvertsInState = new int[maxStates];
34        extrovertsInState = new int[maxStates];
35        dp = new Integer[m][maxStates][introvertsCount + 1][extrovertsCount + 1];
36      
37        // Precompute state information
38        for (int state = 0; state < maxStates; ++state) {
39            int tempState = state;
40          
41            // Decode state into individual cell values
42            for (int col = 0; col < n; ++col) {
43                int cellType = tempState % 3;  // 0=empty, 1=introvert, 2=extrovert
44                tempState /= 3;
45                stateDigits[state][col] = cellType;
46              
47                // Count people and add base happiness
48                if (cellType == 1) {
49                    introvertsInState[state]++;
50                    stateHappiness[state] += 120;  // Base happiness for introvert
51                } else if (cellType == 2) {
52                    extrovertsInState[state]++;
53                    stateHappiness[state] += 40;   // Base happiness for extrovert
54                }
55              
56                // Add horizontal neighbor impact (within the same row)
57                if (col > 0) {
58                    stateHappiness[state] += happinessImpact[cellType][stateDigits[state][col - 1]];
59                }
60            }
61        }
62      
63        // Precompute vertical neighbor impacts between adjacent rows
64        for (int prevState = 0; prevState < maxStates; ++prevState) {
65            for (int currState = 0; currState < maxStates; ++currState) {
66                for (int col = 0; col < n; ++col) {
67                    // Add impact between vertically adjacent cells
68                    adjacentStateBonus[prevState][currState] += 
69                        happinessImpact[stateDigits[prevState][col]][stateDigits[currState][col]];
70                }
71            }
72        }
73      
74        // Start DFS from first row with no previous state
75        return dfs(0, 0, introvertsCount, extrovertsCount);
76    }
77
78    /**
79     * DFS with memoization to find maximum happiness
80     * @param row Current row index
81     * @param prevState State of the previous row
82     * @param remainingIntroverts Remaining introverts to place
83     * @param remainingExtroverts Remaining extroverts to place
84     * @return Maximum happiness achievable from current state
85     */
86    private int dfs(int row, int prevState, int remainingIntroverts, int remainingExtroverts) {
87        // Base cases: reached end of grid or no more people to place
88        if (row == rows || (remainingIntroverts == 0 && remainingExtroverts == 0)) {
89            return 0;
90        }
91      
92        // Check memoization cache
93        if (dp[row][prevState][remainingIntroverts][remainingExtroverts] != null) {
94            return dp[row][prevState][remainingIntroverts][remainingExtroverts];
95        }
96      
97        int maxHappiness = 0;
98      
99        // Try all possible states for current row
100        for (int currState = 0; currState < maxStates; ++currState) {
101            // Check if we have enough people for this state
102            if (introvertsInState[currState] <= remainingIntroverts && 
103                extrovertsInState[currState] <= remainingExtroverts) {
104              
105                // Calculate happiness: base happiness + vertical neighbor bonus + recursive call
106                int happiness = stateHappiness[currState] + 
107                               adjacentStateBonus[prevState][currState] + 
108                               dfs(row + 1, currState, 
109                                   remainingIntroverts - introvertsInState[currState], 
110                                   remainingExtroverts - extrovertsInState[currState]);
111              
112                maxHappiness = Math.max(maxHappiness, happiness);
113            }
114        }
115      
116        // Store in cache and return
117        return dp[row][prevState][remainingIntroverts][remainingExtroverts] = maxHappiness;
118    }
119}
120
1class Solution {
2public:
3    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
4        // Total number of possible states for a row (3^n: empty=0, introvert=1, extrovert=2)
5        int totalStates = pow(3, n);
6      
7        // Arrays to store precomputed values
8        int baseHappiness[totalStates];                    // Base happiness for each state (without interactions between rows)
9        int interactionScore[totalStates][totalStates];    // Interaction scores between two consecutive rows
10        int stateDigits[totalStates][n];                    // Decoded digits for each state
11        int introvertCount[totalStates];                    // Number of introverts in each state
12        int extrovertCount[totalStates];                    // Number of extroverts in each state
13      
14        // DP memoization table: [row][previous_state][remaining_introverts][remaining_extroverts]
15        int dp[m][totalStates][introvertsCount + 1][extrovertsCount + 1];
16      
17        // Happiness change matrix when two people are adjacent
18        // happinessChange[person1][person2]: person1 and person2 types (0=empty, 1=introvert, 2=extrovert)
19        int happinessChange[3][3] = {
20            {0, 0, 0},      // empty next to anything
21            {0, -60, -10},  // introvert next to (empty, introvert, extrovert)
22            {0, -10, 40}    // extrovert next to (empty, introvert, extrovert)
23        };
24      
25        // Initialize arrays
26        memset(baseHappiness, 0, sizeof(baseHappiness));
27        memset(interactionScore, 0, sizeof(interactionScore));
28        memset(stateDigits, 0, sizeof(stateDigits));
29        memset(introvertCount, 0, sizeof(introvertCount));
30        memset(extrovertCount, 0, sizeof(extrovertCount));
31        memset(dp, -1, sizeof(dp));
32      
33        // Precompute values for each possible row state
34        for (int state = 0; state < totalStates; ++state) {
35            int tempState = state;
36          
37            // Decode the state into individual cell values and calculate base happiness
38            for (int col = 0; col < n; ++col) {
39                int cellType = tempState % 3;  // Get cell type (0=empty, 1=introvert, 2=extrovert)
40                tempState /= 3;
41                stateDigits[state][col] = cellType;
42              
43                // Count people and add base happiness
44                if (cellType == 1) {  // Introvert
45                    introvertCount[state]++;
46                    baseHappiness[state] += 120;
47                } else if (cellType == 2) {  // Extrovert
48                    extrovertCount[state]++;
49                    baseHappiness[state] += 40;
50                }
51              
52                // Add horizontal interaction within the same row
53                if (col > 0) {
54                    baseHappiness[state] += happinessChange[cellType][stateDigits[state][col - 1]];
55                }
56            }
57        }
58      
59        // Precompute vertical interaction scores between all pairs of row states
60        for (int state1 = 0; state1 < totalStates; ++state1) {
61            for (int state2 = 0; state2 < totalStates; ++state2) {
62                for (int col = 0; col < n; ++col) {
63                    // Add interaction score between vertically adjacent cells
64                    interactionScore[state1][state2] += happinessChange[stateDigits[state1][col]][stateDigits[state2][col]];
65                }
66            }
67        }
68      
69        // DFS with memoization to find maximum happiness
70        function<int(int, int, int, int)> dfs = [&](int row, int prevState, int remainingIntroverts, int remainingExtroverts) {
71            // Base cases: reached last row or no more people to place
72            if (row == m || (remainingIntroverts == 0 && remainingExtroverts == 0)) {
73                return 0;
74            }
75          
76            // Check memoization
77            if (dp[row][prevState][remainingIntroverts][remainingExtroverts] != -1) {
78                return dp[row][prevState][remainingIntroverts][remainingExtroverts];
79            }
80          
81            int maxHappiness = 0;
82          
83            // Try all possible states for current row
84            for (int currentState = 0; currentState < totalStates; ++currentState) {
85                // Check if we have enough people for this state
86                if (introvertCount[currentState] <= remainingIntroverts && 
87                    extrovertCount[currentState] <= remainingExtroverts) {
88                  
89                    // Calculate total happiness: base + vertical interaction + recursion for next rows
90                    int happiness = baseHappiness[currentState] + 
91                                  interactionScore[prevState][currentState] + 
92                                  dfs(row + 1, currentState, 
93                                      remainingIntroverts - introvertCount[currentState], 
94                                      remainingExtroverts - extrovertCount[currentState]);
95                  
96                    maxHappiness = max(maxHappiness, happiness);
97                }
98            }
99          
100            // Memoize and return result
101            return dp[row][prevState][remainingIntroverts][remainingExtroverts] = maxHappiness;
102        };
103      
104        // Start DFS from first row with empty previous state
105        return dfs(0, 0, introvertsCount, extrovertsCount);
106    }
107};
108
1/**
2 * Calculate maximum grid happiness by placing introverts and extroverts optimally
3 * @param m - Number of rows in the grid
4 * @param n - Number of columns in the grid
5 * @param introvertsCount - Number of introverts to place
6 * @param extrovertsCount - Number of extroverts to place
7 * @returns Maximum happiness value achievable
8 */
9function getMaxGridHappiness(
10    m: number,
11    n: number,
12    introvertsCount: number,
13    extrovertsCount: number,
14): number {
15    // Total number of possible states for a row (3^n: empty, introvert, extrovert)
16    const maxStates = 3 ** n;
17  
18    // Happiness score for each row state configuration
19    const rowHappiness: number[] = Array(maxStates).fill(0);
20  
21    // Interaction scores between two adjacent row states
22    const adjacentRowInteraction: number[][] = Array(maxStates)
23        .fill(0)
24        .map(() => Array(maxStates).fill(0));
25  
26    // Happiness change matrix: [current person type][neighbor person type]
27    // 0: empty, 1: introvert, 2: extrovert
28    const happinessMatrix: number[][] = [
29        [0, 0, 0],      // Empty cell has no interaction
30        [0, -60, -10],  // Introvert: -30 each with another introvert, -10 with extrovert
31        [0, -10, 40],   // Extrovert: -10 with introvert, +20 each with another extrovert
32    ];
33  
34    // Store the person type at each position for each state
35    const stateConfiguration: number[][] = Array(maxStates)
36        .fill(0)
37        .map(() => Array(n).fill(0));
38  
39    // Count of introverts in each state
40    const introvertCount: number[] = Array(maxStates).fill(0);
41  
42    // Count of extroverts in each state
43    const extrovertCount: number[] = Array(maxStates).fill(0);
44  
45    // Memoization table: [row][previous state][introverts left][extroverts left]
46    const memoTable: number[][][][] = Array(m)
47        .fill(0)
48        .map(() =>
49            Array(maxStates)
50                .fill(0)
51                .map(() =>
52                    Array(introvertsCount + 1)
53                        .fill(0)
54                        .map(() => Array(extrovertsCount + 1).fill(-1)),
55                ),
56        );
57  
58    // Precompute information for each possible row state
59    for (let state = 0; state < maxStates; ++state) {
60        let tempState = state;
61      
62        // Decode the state to get person types at each column
63        for (let col = 0; col < n; ++col) {
64            const personType = tempState % 3;
65            tempState = Math.floor(tempState / 3);
66            stateConfiguration[state][col] = personType;
67          
68            // Count person types and add base happiness
69            if (personType === 1) {
70                introvertCount[state] += 1;
71                rowHappiness[state] += 120; // Base happiness for introvert
72            } else if (personType === 2) {
73                extrovertCount[state] += 1;
74                rowHappiness[state] += 40;  // Base happiness for extrovert
75            }
76          
77            // Add horizontal interaction happiness within the row
78            if (col > 0) {
79                rowHappiness[state] += happinessMatrix[personType][stateConfiguration[state][col - 1]];
80            }
81        }
82    }
83  
84    // Precompute vertical interaction scores between adjacent rows
85    for (let currentState = 0; currentState < maxStates; ++currentState) {
86        for (let previousState = 0; previousState < maxStates; ++previousState) {
87            for (let col = 0; col < n; ++col) {
88                // Add interaction score between vertically adjacent cells
89                adjacentRowInteraction[currentState][previousState] += 
90                    happinessMatrix[stateConfiguration[currentState][col]][stateConfiguration[previousState][col]];
91            }
92        }
93    }
94  
95    /**
96     * Dynamic programming function to find maximum happiness
97     * @param currentRow - Current row being processed
98     * @param previousState - State of the previous row
99     * @param introvertsLeft - Remaining introverts to place
100     * @param extrovertsLeft - Remaining extroverts to place
101     * @returns Maximum happiness for the remaining grid
102     */
103    const findMaxHappiness = (
104        currentRow: number, 
105        previousState: number, 
106        introvertsLeft: number, 
107        extrovertsLeft: number
108    ): number => {
109        // Base cases: reached end of grid or no more people to place
110        if (currentRow === m || (introvertsLeft === 0 && extrovertsLeft === 0)) {
111            return 0;
112        }
113      
114        // Check memoization
115        if (memoTable[currentRow][previousState][introvertsLeft][extrovertsLeft] !== -1) {
116            return memoTable[currentRow][previousState][introvertsLeft][extrovertsLeft];
117        }
118      
119        let maxHappiness = 0;
120      
121        // Try all possible states for the current row
122        for (let currentState = 0; currentState < maxStates; ++currentState) {
123            // Check if we have enough people for this state
124            if (introvertCount[currentState] <= introvertsLeft && 
125                extrovertCount[currentState] <= extrovertsLeft) {
126              
127                // Calculate happiness for this configuration
128                const currentHappiness = rowHappiness[currentState] + 
129                                        adjacentRowInteraction[previousState][currentState];
130              
131                // Recursively calculate happiness for remaining rows
132                const remainingHappiness = findMaxHappiness(
133                    currentRow + 1, 
134                    currentState, 
135                    introvertsLeft - introvertCount[currentState], 
136                    extrovertsLeft - extrovertCount[currentState]
137                );
138              
139                maxHappiness = Math.max(maxHappiness, currentHappiness + remainingHappiness);
140            }
141        }
142      
143        // Store and return the result
144        return (memoTable[currentRow][previousState][introvertsLeft][extrovertsLeft] = maxHappiness);
145    };
146  
147    // Start DFS from first row with empty previous state (0)
148    return findMaxHappiness(0, 0, introvertsCount, extrovertsCount);
149}
150

Time and Space Complexity

Time Complexity: O(3^(2n) × m × ic × ec + 3^(2n) × n)

The time complexity consists of two main parts:

  1. Preprocessing phase: O(3^(2n) × n)

    • Computing arrays f, bits, ix, ex requires iterating through all 3^n states, and for each state, we process n positions: O(3^n × n)
    • Computing the 2D array g requires iterating through all pairs of states (3^n × 3^n) and for each pair, comparing n positions: O(3^(2n) × n)

  2. Dynamic programming phase: O(3^n × m × ic × ec)

    • The dfs function has state space of (i, pre, ic, ec) where:
      • i ranges from 0 to m-1 (m states)
      • pre can be any of the 3^n masks
      • ic ranges from 0 to introvertsCount
      • ec ranges from 0 to extrovertsCount
    • For each state, we iterate through all 3^n possible current masks
    • Total: O(3^n × m × ic × ec × 3^n) = O(3^(2n) × m × ic × ec)

The overall time complexity is dominated by the DP phase when m × ic × ec is large, giving us O(3^(2n) × m × ic × ec). When including preprocessing, it becomes O(3^(2n) × (m × ic × ec + n)).

Space Complexity: O(3^(2n) + 3^n × m × ic × ec)

The space complexity includes:

  • Arrays f, ix, ex: each of size 3^n, total O(3^n)
  • 2D array bits: 3^n × n, which is O(3^n × n)
  • 2D array g: 3^n × 3^n, which is O(3^(2n))
  • Memoization cache for dfs: stores results for all possible states (i, pre, ic, ec), which is O(m × 3^n × ic × ec)

The dominant terms are O(3^(2n)) from array g and O(3^n × m × ic × ec) from the memoization cache, resulting in total space complexity of O(3^(2n) + 3^n × m × ic × ec).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect State Encoding/Decoding

One of the most common mistakes is incorrectly converting between ternary representation and the state index. Many implementations get the order wrong or mishandle the base-3 conversion.

Pitfall Example:

# Wrong: This reverses the order of cells
for col in range(n):
    cell_type = state % 3
    state //= 3
    state_cells[state][col] = cell_type  # This fills from left to right

Solution: The correct approach stores the rightmost column in the least significant digit:

# Correct: Consistent encoding/decoding
temp_state = state
for col in range(n):
    temp_state, cell_type = divmod(temp_state, 3)
    state_cells[state][col] = cell_type

2. Double-Counting Neighbor Interactions

When calculating happiness, it's easy to accidentally count the interaction between two neighbors twice - once from each person's perspective.

Pitfall Example:

# Wrong: Double-counting horizontal neighbors
for col in range(n):
    if cell_type == 1:
        base_happiness[state] += 120
        if col > 0:  # Left neighbor
            base_happiness[state] -= 30
        if col < n-1:  # Right neighbor  
            base_happiness[state] -= 30  # This will be counted again!

Solution: Only count the interaction once, either when processing the left cell looking right, or the right cell looking left:

# Correct: Count interaction only once
if col > 0:
    base_happiness[state] += happiness_matrix[cell_type][state_cells[state][col - 1]]

3. Forgetting to Handle Empty Grid States

A subtle bug occurs when not properly handling the case where placing no one might be optimal.

Pitfall Example:

# Wrong: Forces at least one person to be placed
def dfs(row, prev_state, introverts_left, extroverts_left):
    if row == m:
        return 0
  
    max_happiness = -float('inf')  # Wrong! This prevents empty grid from being valid
    for curr_state in range(max_states):
        # ...

Solution: Initialize with 0 to allow empty configurations:

# Correct: Allow empty grid as valid option
max_happiness = 0  # Start with 0, not negative infinity

4. Memory Limit Issues with Large Grids

For larger values of n, the state space (3^n) grows exponentially, potentially causing memory issues.

Pitfall Example:

# Wrong: Creating all states even when m*n is small
max_states = 3 ** n  # Could be huge even if m is 1
state_cells = [[0] * n for _ in range(max_states)]  # Memory explosion

Solution: Add early validation and consider the actual grid size:

# Better: Check feasibility early
if n > 5:  # 3^5 = 243 states is manageable
    # Consider alternative approach or optimize memory usage
    pass

# Or limit based on actual capacity
max_people = min(m * n, introvertsCount + extrovertsCount)
if max_people == 0:
    return 0

5. Incorrect Happiness Matrix Values

The happiness changes for neighbors must account for bidirectional effects.

Pitfall Example:

# Wrong: Only considering one-directional effect
happiness_matrix = [
    [0, 0, 0],
    [0, -30, -30],  # Wrong! Should be -60 for two introverts
    [0, 20, 20]     # Wrong! Should be 40 for two extroverts
]

Solution: Each value should represent the total happiness change for both neighbors:

# Correct: Bidirectional effects
happiness_matrix = [
    [0, 0, 0],      
    [0, -60, -10],  # -30 (introvert loses) + -30 (other introvert loses) = -60
    [0, -10, 40]    # -30 (introvert loses) + 20 (extrovert gains) = -10
]
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Recommended Readings

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Bitmask Intro

Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More