Maximum Students Taking Exam

Hard
1341.

Maximum Students Taking Exam

Maximum Students Taking Exam is a hard coding problem on dynamic programming, matrix and bit manipulation, asked in Amazon and Google interviews.

A classroom is described by seats, an m x n grid given as m strings of length n: '.' is a usable seat and '#' is a broken one.

A student can see the answer sheets of students sitting directly to their left, right, upper left and upper right, but not of the students directly in front of or behind them. Seat students only in usable seats so that no student can see another student's answers.

Return the maximum number of students that can take the exam together.

Example 1

Input
seats = [".#.#.","....."]
Output
6
Explanation
Columns 0, 2 and 4 in both rows. The back row's diagonals all point at broken seats, and same-column seats do not see each other.

Example 2

Input
seats = ["..",".."]
Output
2
Explanation
Both seats of one column — any other pair is side by side or diagonal.

Example 3

Input
seats = ["#"]
Output
0

Constraints

  • seats.length == m
  • seats[i].length == n
  • 1 <= m, n <= 8
  • seats[i][j] is '.' or '#'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} seats
 * @return {number}
 */
var maxStudents = function(seats) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Students Taking Exam — Problem & Solution

Maximum Students Taking Exam solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Students Taking Exam is a hard coding problem on dynamic programming, matrix and bit manipulation, asked in Amazon and Google interviews.

Problem statement

A classroom is described by seats, an m x n grid given as m strings of length n: '.' is a usable seat and '#' is a broken one.

A student can see the answer sheets of students sitting directly to their left, right, upper left and upper right, but not of the students directly in front of or behind them. Seat students only in usable seats so that no student can see another student's answers.

Return the maximum number of students that can take the exam together.

Example 1

Input: seats = [".#.#.","....."]
Output: 6
Explanation: Columns 0, 2 and 4 in both rows. The back row's diagonals all point at broken seats, and same-column seats do not see each other.

Example 2

Input: seats = ["..",".."]
Output: 2
Explanation: Both seats of one column — any other pair is side by side or diagonal.

Example 3

Input: seats = ["#"]
Output: 0

Constraints

  • seats.length == m
  • seats[i].length == n
  • 1 <= m, n <= 8
  • seats[i][j] is '.' or '#'

Hints for Maximum Students Taking Exam

  1. Hint 1

    Process the room row by row. Which seats in one row can be filled together, and how does a row constrain the next one?

  2. Hint 2

    Encode a row's occupied seats as a bitmask. Within a row no two set bits may be adjacent; across consecutive rows, the lower row's mask may not overlap the upper row's mask shifted left or right by one.

  3. Hint 3

    Let dp[row][mask] be the most students in rows 0..row with mask occupied in row. With at most 8 columns there are few valid masks per row, so trying every pair of consecutive masks is cheap.

How to solve Maximum Students Taking Exam

Conflicts only connect a row with itself and with the row directly above, so a DP over rows whose state is the occupancy bitmask of the current row captures everything that matters.

Approach

  1. For each row compute good, the mask of usable seats.
  2. A row mask is valid if it is a subset of good and has no two adjacent bits (mask AND (mask << 1) == 0).
  3. Start from the empty row (dp = {0: 0}). For each row and each valid mask, take the best previous mask p with mask AND (p << 1) == 0 and mask AND (p >> 1) == 0, and store that value plus popcount(mask).
  4. Return the largest value after the last row.

Why it works

Every forbidden pair is either two neighbours in one row (ruled out by the adjacency test) or a student and someone in the row above at a diagonal (ruled out by the two shifted tests); pairs two or more rows apart never conflict. So an arrangement is valid exactly when each row mask is valid and each consecutive pair is compatible, and the DP maximises over all such sequences.

Complexity

  • Time — O(m · F²), F ≤ 55 valid masks per row
  • Space — O(2^n)

Pitfalls

  • Students directly in front or behind do not conflict — only the diagonals of the row above (and below, which is the same relation).
  • Check broken seats with the good mask, not just adjacency.
  • Keep only reachable previous masks to avoid scanning all 2^n × 2^n pairs.

Reference solution

Python

from typing import List

def maxStudents(seats: List[str]) -> int:
    n = len(seats[0])
    prev = {0: 0}
    for row in seats:
        good = 0
        for c in range(n):
            if row[c] == ".":
                good |= 1 << c
        cur = {}
        for mask in range(1 << n):
            if (mask & ~good) or (mask & (mask << 1)):
                continue
            best = -1
            for p, v in prev.items():
                if (mask & (p << 1)) or (mask & (p >> 1)):
                    continue
                if v > best:
                    best = v
            if best >= 0:
                cur[mask] = best + bin(mask).count("1")
        prev = cur
    return max(prev.values())

Java

public static int maxStudents(String[] seats) {
    int n = seats[0].length(), full = 1 << n;
    int[] prevMasks = new int[full], prevVals = new int[full];
    int[] curMasks = new int[full], curVals = new int[full];
    int pl = 1;
    prevMasks[0] = 0;
    prevVals[0] = 0;
    for (String row : seats) {
        int good = 0;
        for (int c = 0; c < n; c++) if (row.charAt(c) == '.') good |= 1 << c;
        int cl = 0;
        for (int mask = 0; mask < full; mask++) {
            if ((mask & ~good) != 0 || (mask & (mask << 1)) != 0) continue;
            int best = -1;
            for (int t = 0; t < pl; t++) {
                int p = prevMasks[t];
                if ((mask & (p << 1)) != 0 || (mask & (p >> 1)) != 0) continue;
                best = Math.max(best, prevVals[t]);
            }
            if (best < 0) continue;
            curMasks[cl] = mask;
            curVals[cl] = best + Integer.bitCount(mask);
            cl++;
        }
        int[] tmp = prevMasks; prevMasks = curMasks; curMasks = tmp;
        tmp = prevVals; prevVals = curVals; curVals = tmp;
        pl = cl;
    }
    int ans = 0;
    for (int t = 0; t < pl; t++) ans = Math.max(ans, prevVals[t]);
    return ans;
}

C++

int maxStudents(vector<string>& seats) {
    int n = seats[0].size(), full = 1 << n;
    vector<pair<int, int>> prev(1, make_pair(0, 0)), cur;
    for (const string& row : seats) {
        int good = 0;
        for (int c = 0; c < n; c++) if (row[c] == '.') good |= 1 << c;
        cur.clear();
        for (int mask = 0; mask < full; mask++) {
            if ((mask & ~good) || (mask & (mask << 1))) continue;
            int best = -1;
            for (auto& pv : prev) {
                if ((mask & (pv.first << 1)) || (mask & (pv.first >> 1))) continue;
                best = max(best, pv.second);
            }
            if (best < 0) continue;
            cur.push_back(make_pair(mask, best + __builtin_popcount(mask)));
        }
        swap(prev, cur);
    }
    int ans = 0;
    for (auto& pv : prev) ans = max(ans, pv.second);
    return ans;
}

JavaScript

var maxStudents = function(seats) {
    var n = seats[0].length, full = 1 << n;
    var prevMasks = [0], prevVals = [0];
    for (var r = 0; r < seats.length; r++) {
        var good = 0;
        for (var c = 0; c < n; c++) if (seats[r][c] === ".") good |= 1 << c;
        var curMasks = [], curVals = [];
        for (var mask = 0; mask < full; mask++) {
            if ((mask & ~good) || (mask & (mask << 1))) continue;
            var best = -1;
            for (var t = 0; t < prevMasks.length; t++) {
                var p = prevMasks[t];
                if ((mask & (p << 1)) || (mask & (p >> 1))) continue;
                if (prevVals[t] > best) best = prevVals[t];
            }
            if (best < 0) continue;
            var cnt = 0;
            for (var x = mask; x; x >>= 1) cnt += x & 1;
            curMasks.push(mask);
            curVals.push(best + cnt);
        }
        prevMasks = curMasks;
        prevVals = curVals;
    }
    var ans = 0;
    for (var k = 0; k < prevVals.length; k++) if (prevVals[k] > ans) ans = prevVals[k];
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Matrix and Grid Traversal