LeetCode Solutions Blog

Maximize Grid Happiness

Difficulty: Hard

Problem Description

You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid. The happiness of each person is calculated based on their neighbors. Return the maximum possible grid happiness.

Key Insights

Introverts start with 120 happiness and lose 30 for each neighbor.
Extroverts start with 40 happiness and gain 20 for each neighbor.
The arrangement of introverts and extroverts impacts the total happiness due to the interaction rules.
The grid can have a maximum of 6 people, allowing for a brute-force or backtracking approach.
Dynamic programming or memoization can be used to store intermediate results for efficiency.

Space and Time Complexity

Time Complexity: O(2^(mn)) - There are at most 2^(mn) configurations of people in the grid. Space Complexity: O(m*n) - Space required for the grid and memoization.

Solution

The solution employs a backtracking approach to explore all possible configurations of placing introverts and extroverts in the grid. We calculate the happiness for each configuration based on the rules provided. A recursive function is used to iterate through the grid and place either an introvert or an extrovert in each cell, while keeping track of the maximum happiness encountered. Memoization can optimize the solution by storing results of previously computed states.

Code Solutions

def get_happiness(grid, i, j, m, n):
    happiness = 0
    neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    for dx, dy in neighbors:
        x, y = i + dx, j + dy
        if 0 <= x < m and 0 <= y < n and grid[x][y] != 0:
            if grid[x][y] == 1:  # Introvert
                happiness -= 30
            else:  # Extrovert
                happiness += 20
                
    return happiness

def backtrack(grid, m, n, introvertsCount, extrovertsCount, idx):
    if idx == m * n:
        total_happiness = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:  # Introvert
                    total_happiness += 120 + get_happiness(grid, i, j, m, n)
                elif grid[i][j] == 2:  # Extrovert
                    total_happiness += 40 + get_happiness(grid, i, j, m, n)
        return total_happiness
    
    max_happiness = 0
    # Try placing an introvert
    if introvertsCount > 0:
        grid[idx // n][idx % n] = 1
        max_happiness = max(max_happiness, backtrack(grid, m, n, introvertsCount - 1, extrovertsCount, idx + 1))
    
    # Try placing an extrovert
    if extrovertsCount > 0:
        grid[idx // n][idx % n] = 2
        max_happiness = max(max_happiness, backtrack(grid, m, n, introvertsCount, extrovertsCount - 1, idx + 1))
    
    # Try placing no one
    grid[idx // n][idx % n] = 0
    max_happiness = max(max_happiness, backtrack(grid, m, n, introvertsCount, extrovertsCount, idx + 1))
    
    return max_happiness

def maximizeHappiness(m, n, introvertsCount, extrovertsCount):
    grid = [[0] * n for _ in range(m)]
    return backtrack(grid, m, n, introvertsCount, extrovertsCount, 0)