Maximize Grid Happiness - Practice Coding Problems

Maximize Grid Happiness - Problem

Imagine you're a city planner tasked with arranging residents in an m x n residential grid to maximize overall community happiness! 🏘️

You have two personality types to work with:

Introverts: Start with 120 happiness but lose 30 points for each neighbor
Extroverts: Start with 40 happiness but gain 20 points for each neighbor

Given introvertsCount introverts and extrovertsCount extroverts, you need to strategically place them (or leave some out) to achieve the maximum possible grid happiness.

Neighbors are those living in directly adjacent cells (north, south, east, west). The total happiness is the sum of all residents' individual happiness scores.

Input & Output

example_1.py — Basic Grid

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

› Output: 240

💡 Note: Place 1 introvert and 2 extroverts optimally. Extroverts gain happiness from neighbors while introvert should be isolated.

example_2.py — Small Grid

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

› Output: 260

💡 Note: In a 3×1 grid, place extrovert in middle (gains from 2 neighbors) and introverts on ends (each loses from 1 neighbor).

example_3.py — Edge Case

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

› Output: 240

💡 Note: With only introverts available, place them to minimize neighbor interactions (diagonal arrangement gives 60×4 = 240).

Constraints

1 ≤ m, n ≤ 5
0 ≤ introvertsCount ≤ min(6, m × n)
0 ≤ extrovertsCount ≤ min(6, m × n)
Grid size is small enough for DP with bitmask approach

Visualization

Tap to expand

Understanding the Visualization

Understanding the Problem

Introverts lose happiness from neighbors (-30 each), extroverts gain happiness (+20 each). Goal: maximize total happiness.

Brute Force Insight

Trying all 3^(m×n) combinations is too slow - we need to identify overlapping subproblems.

Key Observation

Happiness only depends on direct neighbors. We can solve row by row, remembering previous row state.

DP State Design

State: (current_row, previous_row_configuration, introverts_left, extroverts_left)

Optimal Solution

Generate all 3^n row states, use DP with memoization to build solution incrementally.

Key Takeaway

🎯 Key Insight: By processing the grid row by row and using memoization to cache subproblem results, we transform an intractable exponential problem into an efficient dynamic programming solution that leverages the local nature of neighbor interactions.

Asked in

G Google 15 f Meta 12 a Amazon 8 ⊞ Microsoft 6

The optimal solution uses Dynamic Programming with Bitmask to represent row states. Process the grid row by row, tracking previous row state and remaining people counts. Use memoization to avoid recomputing identical subproblems, achieving O(m × 3²ⁿ × introvertsCount × extrovertsCount) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask (Optimal)	O(m × 3^(2n) × introvertsCount × extrovertsCount)	O(3^(2n) × introvertsCount × extrovertsCount)	Use DP with row-wise state compression to avoid recomputing subproblems

Dynamic Programming with Bitmask (Optimal) — Algorithm Steps

Generate all possible states for a single row (3^n combinations)
Use DP where state is (row, prev_row_state, introverts_left, extroverts_left)
For each cell in current row, consider previous row neighbors for happiness calculation
Memoize results to avoid recomputation of identical subproblems
Return maximum happiness across all final states

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Row States

Pre-compute all possible arrangements for a single row (3^n combinations)

Row-by-Row DP

Process grid row by row, considering previous row for neighbor calculations

State Tracking

Track current row, previous row state, and remaining people counts

Memoization

Cache results to avoid recomputing identical subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 243  // 3^5
#define MAX_KEY_LEN 50

typedef struct {
    char key[MAX_KEY_LEN];
    int value;
} MemoEntry;

static int allStates[MAX_STATES][6];
static int numStates = 0;
static MemoEntry memo[10000];
static int memoSize = 0;

void generateStatesHelper(int state[], int pos, int cols) {
    if (pos == cols) {
        for (int i = 0; i < cols; i++) {
            allStates[numStates][i] = state[i];
        }
        numStates++;
        return;
    }
    
    for (int personType = 0; personType <= 2; personType++) {
        state[pos] = personType;
        generateStatesHelper(state, pos + 1, cols);
    }
}

void generateStates(int cols) {
    int state[6] = {0};
    numStates = 0;
    generateStatesHelper(state, 0, cols);
}

int findMemo(const char* key) {
    for (int i = 0; i < memoSize; i++) {
        if (strcmp(memo[i].key, key) == 0) {
            return memo[i].value;
        }
    }
    return -1;
}

void addMemo(const char* key, int value) {
    strcpy(memo[memoSize].key, key);
    memo[memoSize].value = value;
    memoSize++;
}

void countPeople(int state[], int n, int* introverts, int* extroverts) {
    *introverts = *extroverts = 0;
    for (int i = 0; i < n; i++) {
        if (state[i] == 1) (*introverts)++;
        else if (state[i] == 2) (*extroverts)++;
    }
}

int calculateRowHappiness(int currRow[], int prevRow[], int n) {
    int happiness = 0;
    for (int j = 0; j < n; j++) {
        if (currRow[j] == 0) continue;
        
        int neighbors = 0;
        if (j > 0 && currRow[j-1] != 0) neighbors++;
        if (j < n-1 && currRow[j+1] != 0) neighbors++;
        if (prevRow && prevRow[j] != 0) neighbors++;
        
        if (currRow[j] == 1) {
            happiness += 120 - 30 * neighbors;
        } else {
            happiness += 40 + 20 * neighbors;
        }
    }
    return happiness;
}

int dp(int row, int prevStateIdx, int introvertsLeft, int extrovertsLeft, int m, int n) {
    char key[MAX_KEY_LEN];
    sprintf(key, "%d,%d,%d,%d", row, prevStateIdx, introvertsLeft, extrovertsLeft);
    
    int memoResult = findMemo(key);
    if (memoResult != -1) return memoResult;
    
    if (row == m) return 0;
    
    int maxHappiness = 0;
    int* prevState = prevStateIdx >= 0 ? allStates[prevStateIdx] : NULL;
    
    for (int currStateIdx = 0; currStateIdx < numStates; currStateIdx++) {
        int reqIntroverts, reqExtroverts;
        countPeople(allStates[currStateIdx], n, &reqIntroverts, &reqExtroverts);
        
        if (reqIntroverts > introvertsLeft || reqExtroverts > extrovertsLeft) continue;
        
        int currHappiness = calculateRowHappiness(allStates[currStateIdx], prevState, n);
        int futureHappiness = dp(row + 1, currStateIdx, 
                               introvertsLeft - reqIntroverts, 
                               extrovertsLeft - reqExtroverts, m, n);
        
        int total = currHappiness + futureHappiness;
        if (total > maxHappiness) maxHappiness = total;
    }
    
    addMemo(key, maxHappiness);
    return maxHappiness;
}

int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
    memoSize = 0;
    generateStates(n);
    return dp(0, -1, introvertsCount, extrovertsCount, m, n);
}

Time & Space Complexity

Time Complexity

⏱️

O(m × 3^(2n) × introvertsCount × extrovertsCount)

For each of m rows, we have 3^n current states × 3^n previous states, and we track counts of remaining people

✓ Linear Growth

Space Complexity

O(3^(2n) × introvertsCount × extrovertsCount)

Memoization table stores results for all state combinations

⚡ Linearithmic Space

27.6K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler