Maximize Grid Happiness

Number: 1778

Difficulty: Hard

Paid? No

Companies: Salesforce

Problem Description

You are given an m x n grid and a certain number of introverts and extroverts. Each placed person affects their own happiness as well as that of their neighbors, based on whether they are introverts or extroverts. The goal is to assign people to grid cells (you do not have to place everyone) such that the sum of all individual happiness values (grid happiness) is maximized. Introverts lose happiness when having neighbors, while extroverts gain happiness for each neighbor in the four cardinal directions.

Key Insights

The grid size is small (m, n ≤ 5) and the counts are limited (≤6) so an exponential-state dynamic programming (DP) with memoization is viable.
Use DFS/backtracking over the grid cell positions while keeping track of the remaining numbers of introverts and extroverts.
Only neighboring cells (up and left if processing in order) need to be considered for immediate effects, while down and right interactions can be incorporated as future contributions.
Encode state using a bitmask or array to represent the last row (or current row) configuration so that neighbor effects (especially “up” neighbors) are quickly computed.
Transition involves choosing whether to leave a cell empty, place an introvert, or place an extrovert, and update the total happiness accordingly.
Precompute the interaction effects between adjacent cells to avoid recalculating neighbor impact repeatedly.

Space and Time Complexity

Time Complexity: O(m * n * (introvertsCount+1) * (extrovertsCount+1) * state_space)
(The state_space is exponential in the number of columns due to bitmask representation, but since n ≤ 5, it is manageable.)
Space Complexity: O(m * n * (introvertsCount+1) * (extrovertsCount+1) * state_space)
(This is primarily due to the memoization cache storing various states.)

Solution

We solve the problem using Depth-First Search (DFS) with memoization (DP). The idea is to iterate over each cell in the grid and decide whether to leave it empty, place an introvert, or place an extrovert. For every placement, we update the current total happiness based on:

The base happiness of each person (120 for introverts and 40 for extroverts).
The interaction with already placed neighbors (for a left neighbor and the top neighbor which we maintain in the state).
When placing a person, we adjust the happiness of the already placed neighboring person if needed (this is calculated locally as we only add neighbor effects once).

We use an encoded state that tracks:

The current position in the grid (using a single index running from 0 to m*n - 1).
The remaining counts of introverts and extroverts.
The state (configuration) of the last row, stored as a bitmask or an array (with indicators 0, 1, 2 representing empty, introvert, or extrovert).

At each step, using DFS, we try all placement options and choose the one that leads to the maximum total happiness. The memoization cache helps to avoid reprocessing the same state, ensuring the solution runs efficiently despite the exponential nature of potential states.

Code Solutions

# Python solution using DFS with memoization

def getMaxGridHappiness(m, n, introvertsCount, extrovertsCount):
    # Define initial happiness and neighbor interaction values
    base_introvert = 120
    base_extrovert = 40
    introvert_neighbor = -30  # penalty per neighbor for introvert
    extrovert_neighbor = 20   # gain per neighbor for extrovert

    # Effects when placing a person next to another;
    # When two neighbors are adjacent, update both values.
    # For an introvert placed next to an existing neighbor:
    #    additional delta for new introvert + existing neighbor.
    # We incorporate the neighbor effect only once at the time of placement:
    # When placing a person, check the left and top neighbors (which are already placed).
    
    from functools import lru_cache
    
    # Since grid indices are processed in row-major order, we can compute row and col from pos
    def posToRC(pos):
        return pos // n, pos % n

    @lru_cache(maxsize=None)
    def dfs(pos, intro_left, extro_left, prevRow):
        # prevRow is a tuple of length n representing the previous row's configuration:
        # 0 = empty, 1 = introvert, 2 = extrovert.
        if pos == m * n:
            return 0
        i, j = posToRC(pos)
        
        # Construct current row state as a list that we maintain
        # If j == 0, then we are at the beginning of a row:
        if j == 0:
            curRow = [0] * n
        else:
            # For positions in the same row, we need to recover from the current state's row.
            # We simulate current row as starts with empty.
            curRow = [0] * n

        best = dfs(pos + 1, intro_left, extro_left, prevRow)  # Option: leave cell empty
        
        # Helper to calculate the additional happiness when placing a person at (i, j)
        def add_happiness(person):
            # person: 1 for introvert, 2 for extrovert
            happiness = base_introvert if person == 1 else base_extrovert
            # effect for neighbor connections in left and top directions:
            # left neighbor: in current row (we only process left when it has been filled)
            if j > 0:
                # For left neighbor, we need to retrieve stored placement 
                # Since we are processing cell by cell, when placing, we know left neighbor from previous decision.
                # We'll simulate a separate parameter for current row placements.
                # Here we assume that our DFS loop will add the neighbor effect when exploring this placement.
                pass   # We'll handle effect locally below.
            # top neighbor: from prevRow[j]
            if prevRow[j] != 0:
                # Compute interaction with top neighbor:
                # For current person:
                if person == 1:
                    happiness += introvert_neighbor
                else:
                    happiness += extrovert_neighbor
                # For neighbor, its happiness was counted when placed.
                # But we adjust for its effect on the new neighbor:
                # That additional neighbor will similarly add an effect.
                # In our DFS, we add the effect on the current placement only.
                # To account for double counting, we add the effect for both persons when both are placed.
                # Hence, add neighbor effect for the top neighbor's perspective:
                if prevRow[j] == 1:
                    happiness += introvert_neighbor  # introvert's reaction
                elif prevRow[j] == 2:
                    happiness += extrovert_neighbor  # extrovert's reaction
            # left neighbor: if j > 0, we need to check cell (i, j-1) 
            # For simplicity, we can compute left neighbor effect while iterating cell-by-cell,
            # but since our DFS state does not maintain current row placements,
            # we simulate the effect by inserting the placement and then exploring further.
            return happiness

        # To incorporate the left neighbor, we simulate try placement and update current row mask.
        # We combine current row's current bit which is unknown from previous recursive transitions.
        # Instead, we redefine DFS state to include the current row state as we process a row.
        # However, a common technique is to process row by row and maintain state for previous row.
        # Since the grid is small, we can use a different approach: process cell-by-cell
        # and check the left and top neighbor directly if they have been placed.
        # We simulate by storing the grid in an array indexed by pos. Because code clarity is important,
        # we re-define our DFS with an augmented grid state.
        
        # For clarity in this example, we create a grid representation as a tuple of length (m*n)
        # where each cell is 0, 1, or 2.
        # However, the standard DP solution uses bitmask techniques to encode only the previous row.
        # For brevity in this explanation solution, we use a recursive DFS with grid state.
        return best
    
    # Because the DFS state with full grid is more complicated than typical bitmask DP, and given
    # the constraints are small, we can use recursion with grid state.
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dfs_full(pos, intro_left, extro_left, grid_state):
        # grid_state is represented as a tuple of length m*n
        if pos == m * n:
            return 0
        i = pos // n
        j = pos % n
        
        # Function to compute neighbor effect for placing a person at (i, j)
        def neighbor_effect(person):
            total = 0
            # Check up
            if i > 0:
                up = grid_state[(i - 1) * n + j]
                if up:
                    if person == 1:
                        total += introvert_neighbor
                    else:
                        total += extrovert_neighbor
                    if up == 1:
                        total += introvert_neighbor
                    else:
                        total += extrovert_neighbor
            # Check left
            if j > 0:
                left = grid_state[i * n + j - 1]
                if left:
                    if person == 1:
                        total += introvert_neighbor
                    else:
                        total += extrovert_neighbor
                    if left == 1:
                        total += introvert_neighbor
                    else:
                        total += extrovert_neighbor
            return total
        
        best_ans = dfs_full(pos + 1, intro_left, extro_left, grid_state)  # leave empty
        
        # Try placing an introvert if available
        if intro_left:
            gain = base_introvert + neighbor_effect(1)
            new_state = list(grid_state)
            new_state[pos] = 1
            best_ans = max(best_ans, gain + dfs_full(pos + 1, intro_left - 1, extro_left, tuple(new_state)))
        
        # Try placing an extrovert if available
        if extro_left:
            gain = base_extrovert + neighbor_effect(2)
            new_state = list(grid_state)
            new_state[pos] = 2
            best_ans = max(best_ans, gain + dfs_full(pos + 1, intro_left, extro_left - 1, tuple(new_state)))
        
        return best_ans

    # Initialize grid_state with all zeros
    initial_grid = (0,) * (m * n)
    return dfs_full(0, introvertsCount, extrovertsCount, initial_grid)

# Example usage:
print(getMaxGridHappiness(2, 3, 1, 2))

← Back to All Questions