Maximum students taking exam

Array Dynamic Programming Bit Manipulation Matrix Bitmask

53.4% acceptance

Feb 25, 2026

895

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character. Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible. Students must be placed in seats in good condition.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_students(seats: Vec<Vec<char>>) -> i32 {
    let m = seats.len();
    let n = seats[0].len();

    // Build valid masks per row (available seats)
    let mut valid = vec![0u32; m];
    for i in 0..m {
      for j in 0..n {
        if seats[i][j] == '.' {
          valid[i] |= 1 << j;
        }
      }
    }

    const INF: i32 = -1;
    // dp[mask] = max students placing given mask in current row
    let mut dp = vec![INF; 1 << n];
    dp[0] = 0;

    for i in 0..m {
      let mut ndp = vec![INF; 1 << n];
      // Enumerate all masks for this row
      let v = valid[i];
      let mut mask = v;
      loop {
        if mask & v == mask {
          // No two students sit adjacently
          if mask & (mask >> 1) == 0 {
            let cnt = mask.count_ones() as i32;
            // Check prev row
            for prev_mask in 0u32..(1 << n) {
              if dp[prev_mask as usize] == INF { continue; }
              // Students in prev row: no diagonal conflict
              // mask must not have students at upper-left or upper-right of prev students
              // Students in current row can't see prev row upper-left/upper-right
              if mask & (prev_mask >> 1) == 0 && mask & (prev_mask << 1) == 0 {
                let new_cnt = dp[prev_mask as usize] + cnt;
                if new_cnt > ndp[mask as usize] {
                  ndp[mask as usize] = new_cnt;
                }
              }
            }
          }
        }
        if mask == 0 { break; }
        mask = (mask - 1) & v;
      }
      // Also handle mask = 0 explicitly
      for prev_mask in 0u32..(1 << n) {
        if dp[prev_mask as usize] == INF { continue; }
        if dp[prev_mask as usize] > ndp[0] {
          ndp[0] = dp[prev_mask as usize];
        }
      }
      dp = ndp;
    }
    *dp.iter().filter(|&&x| x != INF).max().unwrap_or(&0)
  }
}