rules:
- cant have anyone to the left or right of them
- cant have anyone to the top-left or top-right of them
- chair cannot be broken
- we need a way of remembering the positions of the previous row, to inform the placement of students in the current row
- the input size constraints are interesting
- m and n cant be greater than 8
- suggests the use of bit manipulation to flip student placement
proposed algorithm design:
- for each row
- check if the seat is broken or not
- if it is, flip the bit to 0 (do nothing)
- if it isnt broken continue
- check if there are any students to the left or right of them (check the left and right bits and see if they are flipped to 1)
- check the previous row and the same left and right positions for flipped bits
- populate our bitmask with 8 bits flipping them if a student can be seated there
🤔What Did I Struggle With?
- did not account for precomputing valid masks for each row
- since we know that the number of permutations for a given rows student seating is small due to the size constraints, we can precompute valid masks and store them in a vector of integers, where each integer represents a single 8-bit mask
- the above pre-computation should enable a dynamic programming solution that prevents the repetitive determination of a valid seating arrangement
💡 Explanation of Solution
1. Precompute valid configurations
- for each row, generate a bitmask representing which seats are available (1 for available, 0 for broken)
- compute all possible configurations (bitmasks) for each row
- ensure no two adjacent students are seated (no two bits can be flipped and next to eachother in the order of the bitmask)
2. Initialize the DP table
- create a 2d DP table --> dp[row][mask] where:
- row represents the current row
- mask is a bitmask representing the seating configuration for the current row
- dp[row][mask] stores the maximum number of students that can be seated up to that row, given the configuration
3. Iterate over rows
- for each row
- iterate through all valid configurations (mask) for the current row
- for each configuration
- check compatibility with all valid configurations (prevMask) of the previous row
- ensure no diagonal conflicts (no student in `mask` conflicts with the top-left or top-right position of `prevMask`)
- update the dp table
`dp[row][mask] = max(dp[row][mask], dp[row-1][prevMask] + numberOfStudentsIn(mask));`
4. Count students for each configuration
- for each bitmask (mask), count the number of 1s (students seated) using bitwise operations
5. Find the maximum students:
- after processing all rows, find the maximum value in the last row of the DP table
6. Return the result
⌛ Complexity Analysis
TC:
- m rows.
- 2^n configurations per row.
- For each configuration, check against 2^n configurations of the previous row.
m * (2n×2n)
Space Complexity:
DP table required O(m * 2^n)
💻 Implementation of Solution
class Solution {public: int maxStudents(vector<vector<char>>& seats) { int m = seats.size(); // Number of rows int n = seats[0].size(); // Number of columns // Precompute valid configurations for each row vector<int> validRows(m, 0); // Store available masks for each row for (int i = 0; i < m; ++i) { int mask = 0; for (int j = 0; j < n; ++j) { if (seats[i][j] == '.') { mask |= (1 << j); // Set bit if the seat is not broken } } validRows[i] = mask; } // DP table: dp[row][mask] represents the maximum number of students // seated up to row `row` with the current row configuration `mask` vector<vector<int>> dp(m, vector<int>(1 << n, -1)); // Initialize the first row for (int mask = 0; mask < (1 << n); ++mask) { if (isValidMask(mask, validRows[0])) { dp[0][mask] = countBits(mask); } } // Fill the DP table for (int row = 1; row < m; ++row) { for (int prevMask = 0; prevMask < (1 << n); ++prevMask) { if (dp[row - 1][prevMask] == -1) continue; // Skip invalid previous masks for (int mask = 0; mask < (1 << n); ++mask) { if (isValidMask(mask, validRows[row]) && isCompatible(mask, prevMask)) { dp[row][mask] = max(dp[row][mask], dp[row - 1][prevMask] + countBits(mask)); } } } } // Find the maximum students seated int maxStudents = 0; for (int mask = 0; mask < (1 << n); ++mask) { maxStudents = max(maxStudents, dp[m - 1][mask]); } return maxStudents; }private: // Check if a bitmask is valid for the current row bool isValidMask(int mask, int validRow) { // The mask must fit into the available positions and not have adjacent 1's return (mask & validRow) == mask && (mask & (mask >> 1)) == 0; } // Check if the current row mask is compatible with the previous row mask bool isCompatible(int mask, int prevMask) { // No diagonal conflicts (top-left and top-right) return (mask & (prevMask >> 1)) == 0 && (mask & (prevMask << 1)) == 0; } // Count the number of set bits in a mask int countBits(int mask) { int count = 0; while (mask) { count += (mask & 1); mask >>= 1; } return count; }};