1349. Maximum Students Taking Exam


Problem Description

The problem presents a scenario akin to seating arrangements in a classroom represented by a matrix, with a clear goal: to maximize the number of students that can be seated for an exam without having the possibility of cheating from one another. Seats are either in good condition (represented by a '.') or broken (represented by '#'). A student seated can potentially cheat from students to their left, right, upper left, and upper right, but not from those directly in front or behind them. The objective is to determine the arrangement that allows the maximum number of students to sit for the exam under the given constraints. Seats in poor condition cannot be occupied.

Intuition

The intuition behind the solution is to approach the problem using backtracking and bit manipulation. Here is how we arrive at the solution:

  1. Treat each row of seats as a binary number, where a seat in good condition (.) corresponds to a bit of 1 and a broken seat (#) corresponds to a bit of 0. This allows us to compactly store the state of each row.

  2. Utilize dynamic programming to remember solutions to subproblems and hence avoid recalculating them. This is achieved here by using the cache decorator which memoizes the results of the dfs function.

  3. Implement a depth-first search (DFS) to iterate over all possible seatings of students in a row that satisfy the non-cheating constraints, and then recursively explore valid arrangements for subsequent rows.

  4. Apply bit manipulation within DFS to efficiently:

    • Check if a student can sit in a particular seat by comparing the seat's bitmask with the student's mask.
    • Ensure that students aren't cheating by ensuring that no two adjacent bits in the mask are set (since this would mean two students seated next to each other).
  5. Each state within the DFS is defined by the current row's seating arrangement and the index of the row. With each call, we calculate the maximum number of students that can be seated from this row onwards.

  6. The DFS continues until all rows are evaluated, computing the optimal number of students that can be seated without the possibility of cheating.

By combining these strategies, the solution efficiently explores all possible seating arrangements, abiding by the constraints, and identifies the one that accommodates the maximum number of students.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The solution is composed of several key components: representing the seating arrangement as binary masks, leveraging recursive depth-first search with memoization, and bit manipulation. Here's how these concepts are incorporated into the implementation:

  1. Binary Masks: Each row of the seating arrangement is represented as a binary mask using the f function. A seat in good condition is denoted by a "." and corresponds to a 1 in the binary mask, and a broken seat is denoted by "#" and corresponds to a 0. This allows us to efficiently process the entire row as a single integer where each bit represents a seat.

  2. Dynamic Programming via Memoization: The dfs function is decorated with the @cache decorator, enabling memoization. This optimization technique stores the results of expensive function calls and returns the cached result when the same inputs occur again, thus avoiding the recomputation of results for overlapping subproblems.

  3. Depth-First Search (DFS): The dfs function is designed to find the optimal seating arrangement by exploring every possible arrangement for a row (using masks), ensuring that no adjacent students are seated next to each other (no consecutive bits are set in the mask), and that no student can cheat by seeing the test answers of the student in the upper left or upper right (handled by bit shifting and masking).

    • The DFS continues this process row by row, passing the valid seating arrangement of the next row as a continuation of the current seating arrangement.

    • When the DFS explores the last row (i == len(ss) - 1), it directly updates the maximum answer (ans) with the count of seated students (cnt).

    • For rows that are not the last, the DFS recursively calls itself with the next row's seating arrangement, considering the students already placed in the current row.

  4. Bit Manipulation: The inner loop of dfs uses bit operations to quickly enumerate over all seat combinations (mask), utilising mask.bit_count() to count the number of students (bits set to 1). The if (seat | mask) != seat or (mask & (mask << 1)) condition ensures that students only sit in good seats and not adjacent to each other.

    • The mask is further adjusted to ensure that no student can cheat by looking diagonally at another student's paper; this is accomplished by applying bitwise AND and shifting operations (nxt &= ~(mask << 1) and nxt &= ~(mask >> 1)).
  5. Recursive Call Optimization: To reduce the complexity, before making a recursive call, we apply another set of bitwise operations to determine the seats available for the next row (next), considering the current placements.

By integrating these techniques, the solution effectively searches through all combinatorial possibilities and takes into account all constraints to find the arrangement with the maximum number of students that can be seated without the possibility of cheating. This approach ensures that every seat configuration is considered and the best one is chosen.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following classroom seating arrangement represented as a matrix:

1.##
2.#.

In our example, there are two rows and three columns with a total of four good seats ('.') and two broken seats ('#').

  1. Binary Masks: We convert each row into a binary mask. A seat in good condition (.) is a 1, and a broken seat (#) is a 0. The binary masks for each row in our example are as follows:

    • First row (.##): 100 (binary) or 4 (decimal)
    • Second row (.#.): 101 (binary) or 5 (decimal)
  2. Dynamic Programming via Memoization: The @cache decorator will store the results of the dfs function as we compute the arrangements row by row, avoiding recalculations.

  3. Depth-First Search (DFS): We start by considering the seating arrangement of the first row. We iterate over all possible masks (combinations of students seated) and use a depth-first search to explore each arrangement.

    • For the first row (100), we try seating a student in the first seat. The valid mask for this would be 100 since the two other seats are broken. We count 1 student seated.

    • We then explore the second row. No students can be seated directly below the first row's student, so students could only potentially be seated in the third seat. However, for this example, we'll say that one isn't available due to another constraint such as cheating diagonally.

    • The maximum count for this setup is 1.

    • Since this is a simple example, there's only one valid seating in the first row given the constraints, so we don't have further combinations to try for it.

  4. Bit Manipulation: As we create the mask for the rows, we ensure that no two students are seated next to each other using the conditions described.

  5. Recursive Call Optimization: At each step of the DFS, the available seats for the next row are calculated using bitwise operations considering the current row's placements. In our example, if a student is placed in the first seat on the first row, the only possible seat for the second row would be the third seat.

Using these techniques, we have determined that the maximum number of students which can be seated without the possibility of cheating is 1 for our small example matrix. This example aimed to simplify the approach for illustrative purposes. A real implementation would involve more complex and varied combinations of row arrangements and additional logic to enforce the constraints more rigorously, considering all rows and columns of a larger matrix.

Solution Implementation

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def maxStudents(self, seats: List[List[str]]) -> int:
6        # Function to convert the seating arrangement (seat) into a bitmask representation.
7        # '.' represents an available seat and will be converted to '1' in the bitmask.
8        # 'x' represents a taken or unavailable seat and will be converted to '0' in the bitmask.
9        def get_seat_mask(seat: List[str]) -> int:
10            mask = 0
11            for i, c in enumerate(seat):
12                if c == '.':
13                    mask |= 1 << i
14            return mask
15
16        # Recursive function with memoization to find the maximum number of students.
17        # It uses depth-first search (DFS) with the current seat arrangement (as a bitmask)
18        # and the row index 'i' as arguments.
19        @lru_cache(maxsize=None)
20        def dfs(current_seat_mask: int, i: int) -> int:
21            ans = 0
22            for mask in range(1 << n):
23                # Skip if the mask has a student in an unavailable seat or two students sitting next to each other.
24                if (current_seat_mask | mask) != current_seat_mask or (mask & (mask << 1)):
25                    continue
26              
27                # Count the number of students (bits set to 1) in the mask.
28                cnt = bin(mask).count('1')
29                # If it's the last row, return the count as is.
30                if i == len(available_seat_masks) - 1:
31                    ans = max(ans, cnt)
32                else:
33                    # Calculate the mask for the next row where students can be placed.
34                    # Students in the next row cannot be directly behind or diagonally behind a student in the current row.
35                    next_seat_mask = available_seat_masks[i + 1]
36                    next_seat_mask &= ~(mask << 1)
37                    next_seat_mask &= ~(mask >> 1)
38                    # Maximize the count including the next row's students.
39                    ans = max(ans, cnt + dfs(next_seat_mask, i + 1))
40            return ans
41
42        # Get the number of columns in the classroom.
43        n = len(seats[0])
44        # Convert the classroom seating arrangement into a list of bitmasks.
45        available_seat_masks = [get_seat_mask(row) for row in seats]
46        # Start the recursive DFS with the first row's bitmask.
47        return dfs(available_seat_masks[0], 0)
48
49# Example usage:
50sol = Solution()
51print(sol.maxStudents([['.', '.'], ['.', 'x'], ['.', '.'], ['x', '.']]))  # Output will be the maximum number of students
52
1class Solution {
2    private Integer[][] memo; // memoization table to store results for subproblems
3    private int numSeats; // number of seats in a row
4    private int[] validSeats; // array representing the valid seats in each row using bitmasks
5
6    // Main method to calculate the maximum number of students that can sit in the provided seats
7    public int maxStudents(char[][] seats) {
8        int rows = seats.length; // number of rows
9        numSeats = seats[0].length; // number of seats in a row
10        validSeats = new int[rows]; // create an array to represent the valid seats using bitmasks
11        memo = new Integer[1 << numSeats][rows]; // initialize the memoization table
12        // Preprocess the seats and store the valid positions using bit manipulation
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < numSeats; ++j) {
15                if (seats[i][j] == '.') {
16                    validSeats[i] |= 1 << j; // use a bitmask to represent a valid seat position
17                }
18            }
19        }
20        // Start the depth-first search from the first row
21        return dfs(validSeats[0], 0);
22    }
23
24    // DFS method to find the optimal sitting arrangement
25    private int dfs(int seatRow, int rowIndex) {
26        // If we have already computed this subproblem, return its result
27        if (memo[seatRow][rowIndex] != null) {
28            return memo[seatRow][rowIndex];
29        }
30        int maxStudentsCount = 0; // initialize the current count of students to 0
31        // Iterate over all possible seat combinations for the current row
32        for (int mask = 0; mask < 1 << numSeats; ++mask) {
33            // Check if the mask is a subset of available seats and has no adjacent students
34            if ((seatRow | mask) != seatRow || (mask & (mask << 1)) != 0) {
35                continue; // skip this combination if it's not valid
36            }
37            int seatCount = Integer.bitCount(mask); // count the number of students seated
38            // If we are at the last row, update the maxStudents if needed
39            if (rowIndex == validSeats.length - 1) {
40                maxStudentsCount = Math.max(maxStudentsCount, seatCount);
41            } else {
42                // Prepare the available seats for the next row
43                int nextRow = validSeats[rowIndex + 1];
44                nextRow &= ~(mask << 1); // remove seats left-diagonal to a seated student
45                nextRow &= ~(mask >> 1); // remove seats right-diagonal to a seated student
46                // Recursively call dfs for the next row and accumulate the result
47                maxStudentsCount = Math.max(maxStudentsCount, seatCount + dfs(nextRow, rowIndex + 1));
48            }
49        }
50        // Memoize and return the result for the current state
51        return memo[seatRow][rowIndex] = maxStudentsCount;
52    }
53}
54
1class Solution {
2public:
3    int maxStudents(vector<vector<char>>& seats) {
4        int rows = seats.size(); // The number of rows in the classroom
5        int cols = seats[0].size(); // The number of seats in a row
6      
7        // Represents the seats in each row with a binary number ('.'=1 for a valid seat and '0'=0 for a broken seat).
8        vector<int> validSeats(rows, 0);
9        for (int i = 0; i < rows; ++i) {
10            for (int j = 0; j < cols; ++j) {
11                if (seats[i][j] == '.') {
12                    validSeats[i] |= 1 << j; // Sets the j-th bit if the seat is valid
13                }
14            }
15        }
16      
17        // f[mask][row] is the maximum number of students for the 'row' with 'mask' denoting which seats are taken in this row.
18        vector<vector<int>> cache(1 << cols, vector<int>(rows, -1));
19      
20        // Helper function to use depth-first search to find the maximum number of students.
21        function<int(int, int)> dfs = [&](int seatMask, int row) -> int {
22            // If the result is already computed, return it from the cache.
23            if (cache[seatMask][row] != -1) {
24                return cache[seatMask][row];
25            }
26            int maxStudents = 0; // Maximum students that can sit starting from this row.
27            // Try every possible combination of students sitting in this row.
28            for (int mask = 0; mask < (1 << cols); ++mask) {
29                // Check if 'mask' can fit into 'seatMask' and that no adjacent students are sitting.
30                if ((seatMask | mask) != seatMask || (mask & (mask << 1)) != 0) {
31                    continue;
32                }
33              
34                // Count of students that can sit in this current configuration.
35                int count = __builtin_popcount(mask);
36                if (row == rows - 1) {
37                    // If it's the last row, just take the count.
38                    maxStudents = max(maxStudents, count);
39                } else {
40                    // Calculate valid seats for the next row considering the current row.
41                    int nextValidSeats = validSeats[row + 1];
42                    // Invalidate seats to the left and right diagonally of an occupied seat.
43                    nextValidSeats &= ~(mask >> 1);
44                    nextValidSeats &= ~(mask << 1);
45                    // Update the maxStudents with the result of the next rows.
46                    maxStudents = max(maxStudents, count + dfs(nextValidSeats, row + 1));
47                }
48            }
49            // Cache and return the maximum number of students for this configuration.
50            return cache[seatMask][row] = maxStudents;
51        };
52      
53        // Start the DFS process with the first row and its validSeats representation.
54        return dfs(validSeats[0], 0);
55    }
56};
57
1// Define the dimensions of the classroom seating arrangement
2let rows: number;
3let cols: number;
4
5// Define and initialize the array for valid seat configurations for each row
6let validSeats: number[];
7
8// Store maximum number of students based on (mask, row) configuration
9let cache: number[][];
10
11// Function to count the number of set bits (popcount equivalent)
12function countBits(mask: number): number {
13    let count = 0;
14    while(mask > 0) {
15        count += mask & 1;
16        mask >>= 1;
17    }
18    return count;
19}
20
21// Define depth-first search function for finding the maximum number of students
22let dfs: (seatMask: number, row: number) => number;
23
24// Given a 2D array of seats, calculate the maximum students that can be seated
25function maxStudents(seats: char[][]): number {
26    rows = seats.length; // The number of rows in the classroom
27    cols = seats[0].length; // The number of seats in a row
28  
29    // Represents the valid and broken seats in binary for each row
30    validSeats = new Array(rows).fill(0);
31    for (let i = 0; i < rows; ++i) {
32        for (let j = 0; j < cols; ++j) {
33            if (seats[i][j] === '.') {
34                validSeats[i] |= 1 << j; // Sets the j-th bit if the seat is valid
35            }
36        }
37    }
38  
39    // Initialize cache with -1 to indicate uncalculated states
40    cache = Array.from({length: 1 << cols}, () => Array(rows).fill(-1));
41  
42    // Declare and define the DFS function for maximum students
43    dfs = (seatMask: number, row: number): number => {
44        if (cache[seatMask][row] !== -1) {
45            // Return cached value if already computed
46            return cache[seatMask][row];
47        }
48        let maxStudents = 0; // Initialize maximum students for this configuration
49
50        // Try all possible combinations of students in the current row
51        for (let mask = 0; mask < (1 << cols); ++mask) {
52            // Ensure that mask fits the seatMask and check for no adjacent students
53            if ((seatMask | mask) !== seatMask || (mask & (mask << 1)) !== 0) {
54                continue;
55            }
56          
57            // Count students in the current seating configuration
58            let count = countBits(mask);
59            if (row === rows - 1) {
60                maxStudents = Math.max(maxStudents, count);
61            } else {
62                // Prepare next row's valid seats considering current seating
63                let nextValidSeats = validSeats[row + 1];
64                // Invalidate seats left and right diagonally from occupied seats
65                nextValidSeats &= ~(mask >> 1);
66                nextValidSeats &= ~(mask << 1);
67                // Calculate maximum students including subsequent rows
68                maxStudents = Math.max(maxStudents, count + dfs(nextValidSeats, row + 1));
69            }
70        }
71      
72        // Cache the result for current state and return
73        return cache[seatMask][row] = maxStudents;
74    };
75  
76    // Start the DFS from the first row with its corresponding valid seats
77    return dfs(validSeats[0], 0);
78}
79

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed by examining the two main parts: the construction of valid masks for each row of seats (f(seat: List[str])) and the depth-first search with memoization for finding the maximum number of students (dfs(seat: int, i: int)).

  1. The f function has a time complexity of O(m) where m is the length of a row, because it iterates through each seat to create a bitmask representation of available seats.

  2. The dfs function involves iterating over all possible seat configurations for each row (represented as bitmasks) and combining these with the possibilities of the following row. For each row, there are 2^n possible seating arrangements where n is the number of seats in a row. There are also constraints that eliminate some possibilities due to students not being able to sit next to each other.

The dfs function is called recursively for each row, with constraints reducing the number of possibilities. The memoization cache efficiently stores results for different configurations, meaning each unique configuration of a row is computed only once. If k is the number of rows:

  • Without memoization, the upper bound time complexity would be O((2^n)^k) which simplifies to O(2^(n*k)).
  • With memoization, the time complexity is greatly reduced because you only compute each unique configuration of a row once and there are k*2^n unique configurations (since each row can have 2^n configurations and there are k rows). Thus, the time complexity is O(k * 2^n).

Combine these, and the overall time complexity becomes O(m*k + k * 2^n).

Space Complexity

The space complexity is determined by the space required to store the memoization cache and the recursive call stack of the DFS function.

  • The memoization cache stores a value for each unique configuration of a row, of which there are at most k*2^n, so the cache space complexity is O(k * 2^n).
  • The maximum depth of the recursive call stack is k (the number of rows), so the space required for the call stack is O(k).

The overall space complexity is therefore dominated by the memoization cache: O(k * 2^n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄