Problem

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. There are introvertsCount introverts and extrovertsCount 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 as follows:

  • Introverts start with 120 happiness and lose 30 happiness for each neighbor (introvert or extrovert).
  • Extroverts start with 40 happiness and gain 20 happiness for each neighbor (introvert or extrovert).

Neighbors live in the directly adjacent cells north, east, south, and west of a person’s cell.

The grid happiness is the sum of each person’s happiness. Return the maximum possible grid happiness.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
Output: 240
Explanation: Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.

Example 2

1
2
3
4
5
6
7

Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
Output: 260
Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.

Example 3

1
2

Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
Output: 240

Constraints

  • 1 <= m, n <= 5
  • 0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

Solution

Method 1 – Dynamic Programming with Bitmasking

Intuition

The problem can be solved using dynamic programming with bitmasking to represent the state of each row. By exploring all possible placements of introverts and extroverts, and keeping track of their interactions, we can maximize the grid happiness.

Approach

  1. Use a DP function that tracks the current cell, remaining introverts/extroverts, and the state of the previous row (bitmask).
  2. For each cell, try placing an introvert, extrovert, or leaving it empty.
  3. Calculate happiness changes based on neighbors (left and above).
  4. Memoize results to avoid recomputation.
  5. Return the maximum happiness achievable.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
    int m, n;
    int dp[6][6][7][7][1 << 10];
    int dfs(int r, int c, int intro, int extro, int mask, vector<int>& grid) {
        if (r == m) return 0;
        if (c == n) return dfs(r + 1, 0, intro, extro, mask, grid);
        int key = mask;
        int& ans = dp[r][c][intro][extro][mask];
        if (ans != -1) return ans;
        ans = dfs(r, c + 1, intro, extro, mask << 2 & ((1 << (2 * n)) - 1), grid);
        if (intro > 0) {
            int happy = 120;
            if (c > 0 && ((mask >> (2 * (n - 1))) & 3) == 1) happy -= 30, happy -= 30;
            if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) == 1) happy -= 30, happy -= 30;
            if (c > 0 && ((mask >> (2 * (n - 1))) & 3) == 2) happy -= 30, happy += 20;
            if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) == 2) happy -= 30, happy += 20;
            ans = max(ans, happy + dfs(r, c + 1, intro - 1, extro, (mask << 2 | 1) & ((1 << (2 * n)) - 1), grid));
        }
        if (extro > 0) {
            int happy = 40;
            if (c > 0 && ((mask >> (2 * (n - 1))) & 3) == 1) happy += 20, happy -= 30;
            if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) == 1) happy += 20, happy -= 30;
            if (c > 0 && ((mask >> (2 * (n - 1))) & 3) == 2) happy += 20, happy += 20;
            if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) == 2) happy += 20, happy += 20;
            ans = max(ans, happy + dfs(r, c + 1, intro, extro - 1, (mask << 2 | 2) & ((1 << (2 * n)) - 1), grid));
        }
        return ans;
    }
    int getMaxGridHappiness(int M, int N, int introvertsCount, int extrovertsCount) {
        m = M; n = N;
        memset(dp, -1, sizeof(dp));
        vector<int> grid(m * n);
        return dfs(0, 0, introvertsCount, extrovertsCount, 0, grid);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func getMaxGridHappiness(m, n, introvertsCount, extrovertsCount int) int {
    type key struct{r, c, intro, extro, mask int}
    memo := map[key]int{}
    var dfs func(r, c, intro, extro, mask int) int
    dfs = func(r, c, intro, extro, mask int) int {
        if r == m { return 0 }
        if c == n { return dfs(r+1, 0, intro, extro, mask) }
        k := key{r, c, intro, extro, mask}
        if v, ok := memo[k]; ok { return v }
        res := dfs(r, c+1, intro, extro, (mask<<2)&((1<<(2*n))-1))
        if intro > 0 {
            happy := 120
            if c > 0 && ((mask>>(2*(n-1)))&3) == 1 { happy -= 30; happy -= 30 }
            if r > 0 && ((mask>>(2*(n-c-1)))&3) == 1 { happy -= 30; happy -= 30 }
            if c > 0 && ((mask>>(2*(n-1)))&3) == 2 { happy -= 30; happy += 20 }
            if r > 0 && ((mask>>(2*(n-c-1)))&3) == 2 { happy -= 30; happy += 20 }
            res = max(res, happy+dfs(r, c+1, intro-1, extro, ((mask<<2)|1)&((1<<(2*n))-1)))
        }
        if extro > 0 {
            happy := 40
            if c > 0 && ((mask>>(2*(n-1)))&3) == 1 { happy += 20; happy -= 30 }
            if r > 0 && ((mask>>(2*(n-c-1)))&3) == 1 { happy += 20; happy -= 30 }
            if c > 0 && ((mask>>(2*(n-1)))&3) == 2 { happy += 20; happy += 20 }
            if r > 0 && ((mask>>(2*(n-c-1)))&3) == 2 { happy += 20; happy += 20 }
            res = max(res, happy+dfs(r, c+1, intro, extro-1, ((mask<<2)|2)&((1<<(2*n))-1)))
        }
        memo[k] = res
        return res
    }
    return dfs(0, 0, introvertsCount, extrovertsCount, 0)
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    int m, n;
    int[][][][][] dp;
    public int getMaxGridHappiness(int M, int N, int introvertsCount, int extrovertsCount) {
        m = M; n = N;
        dp = new int[m+1][n+1][introvertsCount+1][extrovertsCount+1][1 << (2*n)];
        for (int[][][][] arr1 : dp)
            for (int[][][] arr2 : arr1)
                for (int[][] arr3 : arr2)
                    for (int[] arr4 : arr3)
                        Arrays.fill(arr4, -1);
        return dfs(0, 0, introvertsCount, extrovertsCount, 0);
    }
    int dfs(int r, int c, int intro, int extro, int mask) {
        if (r == m) return 0;
        if (c == n) return dfs(r+1, 0, intro, extro, mask);
        if (dp[r][c][intro][extro][mask] != -1) return dp[r][c][intro][extro][mask];
        int res = dfs(r, c+1, intro, extro, (mask<<2)&((1<<(2*n))-1));
        if (intro > 0) {
            int happy = 120;
            if (c > 0 && ((mask>>(2*(n-1)))&3) == 1) happy -= 30;
            if (r > 0 && ((mask>>(2*(n-c-1)))&3) == 1) happy -= 30;
            if (c > 0 && ((mask>>(2*(n-1)))&3) == 2) happy -= 30;
            if (r > 0 && ((mask>>(2*(n-c-1)))&3) == 2) happy -= 30;
            res = Math.max(res, happy + dfs(r, c+1, intro-1, extro, ((mask<<2)|1)&((1<<(2*n))-1)));
        }
        if (extro > 0) {
            int happy = 40;
            if (c > 0 && ((mask>>(2*(n-1)))&3) == 1) happy += 20;
            if (r > 0 && ((mask>>(2*(n-c-1)))&3) == 1) happy += 20;
            if (c > 0 && ((mask>>(2*(n-1)))&3) == 2) happy += 20;
            if (r > 0 && ((mask>>(2*(n-c-1)))&3) == 2) happy += 20;
            res = Math.max(res, happy + dfs(r, c+1, intro, extro-1, ((mask<<2)|2)&((1<<(2*n))-1)));
        }
        return dp[r][c][intro][extro][mask] = res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun getMaxGridHappiness(m: Int, n: Int, introvertsCount: Int, extrovertsCount: Int): Int {
        val dp = HashMap<String, Int>()
        fun dfs(r: Int, c: Int, intro: Int, extro: Int, mask: Int): Int {
            if (r == m) return 0
            if (c == n) return dfs(r + 1, 0, intro, extro, mask)
            val key = "$r,$c,$intro,$extro,$mask"
            if (key in dp) return dp[key]!!
            var res = dfs(r, c + 1, intro, extro, (mask shl 2) and ((1 shl (2 * n)) - 1))
            if (intro > 0) {
                var happy = 120
                if (c > 0 && ((mask shr (2 * (n - 1))) and 3) == 1) happy -= 30
                if (r > 0 && ((mask shr (2 * (n - c - 1))) and 3) == 1) happy -= 30
                if (c > 0 && ((mask shr (2 * (n - 1))) and 3) == 2) happy -= 30
                if (r > 0 && ((mask shr (2 * (n - c - 1))) and 3) == 2) happy -= 30
                res = maxOf(res, happy + dfs(r, c + 1, intro - 1, extro, ((mask shl 2) or 1) and ((1 shl (2 * n)) - 1)))
            }
            if (extro > 0) {
                var happy = 40
                if (c > 0 && ((mask shr (2 * (n - 1))) and 3) == 1) happy += 20
                if (r > 0 && ((mask shr (2 * (n - c - 1))) and 3) == 1) happy += 20
                if (c > 0 && ((mask shr (2 * (n - 1))) and 3) == 2) happy += 20
                if (r > 0 && ((mask shr (2 * (n - c - 1))) and 3) == 2) happy += 20
                res = maxOf(res, happy + dfs(r, c + 1, intro, extro - 1, ((mask shl 2) or 2) and ((1 shl (2 * n)) - 1)))
            }
            dp[key] = res
            return res
        }
        return dfs(0, 0, introvertsCount, extrovertsCount, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
        from functools import lru_cache
        @lru_cache(None)
        def dfs(r: int, c: int, intro: int, extro: int, mask: int) -> int:
            if r == m:
                return 0
            if c == n:
                return dfs(r + 1, 0, intro, extro, mask)
            res = dfs(r, c + 1, intro, extro, (mask << 2) & ((1 << (2 * n)) - 1))
            if intro > 0:
                happy = 120
                if c > 0 and ((mask >> (2 * (n - 1))) & 3) == 1:
                    happy -= 30
                if r > 0 and ((mask >> (2 * (n - c - 1))) & 3) == 1:
                    happy -= 30
                if c > 0 and ((mask >> (2 * (n - 1))) & 3) == 2:
                    happy -= 30
                if r > 0 and ((mask >> (2 * (n - c - 1))) & 3) == 2:
                    happy -= 30
                res = max(res, happy + dfs(r, c + 1, intro - 1, extro, ((mask << 2) | 1) & ((1 << (2 * n)) - 1)))
            if extro > 0:
                happy = 40
                if c > 0 and ((mask >> (2 * (n - 1))) & 3) == 1:
                    happy += 20
                if r > 0 and ((mask >> (2 * (n - c - 1))) & 3) == 1:
                    happy += 20
                if c > 0 and ((mask >> (2 * (n - 1))) & 3) == 2:
                    happy += 20
                if r > 0 and ((mask >> (2 * (n - c - 1))) & 3) == 2:
                    happy += 20
                res = max(res, happy + dfs(r, c + 1, intro, extro - 1, ((mask << 2) | 2) & ((1 << (2 * n)) - 1)))
            return res

        return dfs(0, 0, introvertsCount, extrovertsCount, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn get_max_grid_happiness(m: i32, n: i32, introverts_count: i32, extroverts_count: i32) -> i32 {
        use std::collections::HashMap;
        fn dfs(r: i32, c: i32, intro: i32, extro: i32, mask: i32, m: i32, n: i32, memo: &mut HashMap<(i32,i32,i32,i32,i32),i32>) -> i32 {
            if r == m { return 0; }
            if c == n { return dfs(r+1, 0, intro, extro, mask, m, n, memo); }
            if let Some(&v) = memo.get(&(r,c,intro,extro,mask)) { return v; }
            let mut res = dfs(r, c+1, intro, extro, (mask<<2)&((1<<(2*n))-1), m, n, memo);
            if intro > 0 {
                let mut happy = 120;
                if c > 0 && ((mask>>(2*(n-1)))&3) == 1 { happy -= 30; }
                if r > 0 && ((mask>>(2*(n-c-1)))&3) == 1 { happy -= 30; }
                if c > 0 && ((mask>>(2*(n-1)))&3) == 2 { happy -= 30; }
                if r > 0 && ((mask>>(2*(n-c-1)))&3) == 2 { happy -= 30; }
                res = res.max(happy + dfs(r, c+1, intro-1, extro, ((mask<<2)|1)&((1<<(2*n))-1), m, n, memo));
            }
            if extro > 0 {
                let mut happy = 40;
                if c > 0 && ((mask>>(2*(n-1)))&3) == 1 { happy += 20; }
                if r > 0 && ((mask>>(2*(n-c-1)))&3) == 1 { happy += 20; }
                if c > 0 && ((mask>>(2*(n-1)))&3) == 2 { happy += 20; }
                if r > 0 && ((mask>>(2*(n-c-1)))&3) == 2 { happy += 20; }
                res = res.max(happy + dfs(r, c+1, intro, extro-1, ((mask<<2)|2)&((1<<(2*n))-1), m, n, memo));
            }
            memo.insert((r,c,intro,extro,mask), res);
            res
        }
        let mut memo = HashMap::new();
        dfs(0, 0, introverts_count, extroverts_count, 0, m, n, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    getMaxGridHappiness(m: number, n: number, introvertsCount: number, extrovertsCount: number): number {
        const memo = new Map<string, number>();
        const dfs = (r: number, c: number, intro: number, extro: number, mask: number): number => {
            if (r === m) return 0;
            if (c === n) return dfs(r + 1, 0, intro, extro, mask);
            const key = `${r},${c},${intro},${extro},${mask}`;
            if (memo.has(key)) return memo.get(key)!;
            let res = dfs(r, c + 1, intro, extro, (mask << 2) & ((1 << (2 * n)) - 1));
            if (intro > 0) {
                let happy = 120;
                if (c > 0 && ((mask >> (2 * (n - 1))) & 3) === 1) happy -= 30;
                if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) === 1) happy -= 30;
                if (c > 0 && ((mask >> (2 * (n - 1))) & 3) === 2) happy -= 30;
                if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) === 2) happy -= 30;
                res = Math.max(res, happy + dfs(r, c + 1, intro - 1, extro, ((mask << 2) | 1) & ((1 << (2 * n)) - 1)));
            }
            if (extro > 0) {
                let happy = 40;
                if (c > 0 && ((mask >> (2 * (n - 1))) & 3) === 1) happy += 20;
                if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) === 1) happy += 20;
                if (c > 0 && ((mask >> (2 * (n - 1))) & 3) === 2) happy += 20;
                if (r > 0 && ((mask >> (2 * (n - c - 1))) & 3) === 2) happy += 20;
                res = Math.max(res, happy + dfs(r, c + 1, intro, extro - 1, ((mask << 2) | 2) & ((1 << (2 * n)) - 1)));
            }
            memo.set(key, res);
            return res;
        };
        return dfs(0, 0, introvertsCount, extrovertsCount, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(m * n * introvertsCount * extrovertsCount * 3^(m*n)), since each cell can be empty, introvert, or extrovert, and we memoize states.
  • 🧺 Space complexity: O(m * n * introvertsCount * extrovertsCount * 3^(m*n)), for memoization.