Maximize grid happiness

Dynamic Programming Bit Manipulation Memoization Bitmask

40.9% acceptance

Feb 25, 2026

342

You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid with introverts and extroverts to place. Introverts start with 120 happiness and lose 30 for each neighbor. Extroverts start with 40 happiness and gain 20 for each neighbor. Return the maximum possible grid happiness.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn get_max_grid_happiness(
    m: i32, n: i32, introverts_count: i32, extroverts_count: i32,
  ) -> i32 {
    let (m, n) = (m as usize, n as usize);
    let (max_i, max_e) = (introverts_count as usize, extroverts_count as usize);
    let pow3n = 3usize.pow(n as u32);

    // interaction happiness between two adjacent people
    let interact = |a: usize, b: usize| -> i32 {
      match (a, b) {
        (0, _) | (_, 0) => 0,
        (1, 1) => -60,
        (2, 2) => 40,
        _ => -10, // (1,2) or (2,1)
      }
    };

    // Decode row state s -> cell values (0=empty,1=intro,2=extro) for n cells
    let decode = |s: usize| -> Vec<usize> {
      let mut row = vec![0usize; n];
      let mut tmp = s;
      for i in 0..n {
        row[i] = tmp % 3;
        tmp /= 3;
      }
      row
    };

    // Precompute per-row-state: (intro_count, extro_count, solo_happy, horiz_interact)
    let mut ri_count = vec![0usize; pow3n]; // intro count
    let mut re_count = vec![0usize; pow3n]; // extro count
    let mut r_solo = vec![0i32; pow3n];
    let mut r_horiz = vec![0i32; pow3n];

    for s in 0..pow3n {
      let row = decode(s);
      let mut ic = 0;
      let mut ec = 0;
      let mut solo = 0;
      let mut horiz = 0;
      for i in 0..n {
        match row[i] {
          1 => { ic += 1; solo += 120; }
          2 => { ec += 1; solo += 40; }
          _ => {}
        }
        if i + 1 < n {
          horiz += interact(row[i], row[i + 1]);
        }
      }
      ri_count[s] = ic;
      re_count[s] = ec;
      r_solo[s] = solo;
      r_horiz[s] = horiz;
    }

    // Precompute vertical interaction between prev_row and cur_row
    let mut r_vert = vec![vec![0i32; pow3n]; pow3n];
    for ps in 0..pow3n {
      let prev = decode(ps);
      for cs in 0..pow3n {
        let cur = decode(cs);
        let mut v = 0;
        for i in 0..n {
          v += interact(prev[i], cur[i]);
        }
        r_vert[ps][cs] = v;
      }
    }

    const NEG_INF: i32 = i32::MIN / 2;
    // dp[ic][ec][prev_row_state] = max happiness so far
    let mut dp = vec![vec![vec![NEG_INF; pow3n]; max_e + 1]; max_i + 1];
    // Before processing row 0: prev = empty row (state 0), 0 people used
    dp[0][0][0] = 0;

    let mut ans = 0;

    for _row in 0..m {
      let mut new_dp = vec![vec![vec![NEG_INF; pow3n]; max_e + 1]; max_i + 1];
      for ic in 0..=max_i {
        for ec in 0..=max_e {
          for ps in 0..pow3n {
            let cur_val = dp[ic][ec][ps];
            if cur_val == NEG_INF {
              continue;
            }
            for cs in 0..pow3n {
              let ni = ic + ri_count[cs];
              let ne = ec + re_count[cs];
              if ni > max_i || ne > max_e {
                continue;
              }
              let delta = r_solo[cs] + r_horiz[cs] + r_vert[ps][cs];
              let new_val = cur_val + delta;
              if new_dp[ni][ne][cs] < new_val {
                new_dp[ni][ne][cs] = new_val;
              }
            }
          }
        }
      }
      dp = new_dp;
    }

    for ic in 0..=max_i {
      for ec in 0..=max_e {
        for s in 0..pow3n {
          if dp[ic][ec][s] != NEG_INF {
            ans = ans.max(dp[ic][ec][s]);
          }
        }
      }
    }
    ans
  }
}