1349. Maximum Students Taking Exam LeetCode Solution
In this guide, you will get 1349. Maximum Students Taking Exam LeetCode Solution with the best time and space complexity. The solution to Maximum Students Taking Exam problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Maximum Students Taking Exam solution in C++
- Maximum Students Taking Exam solution in Java
- Maximum Students Taking Exam solution in Python
- Additional Resources
Problem Statement of Maximum Students Taking Exam
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.
Example 1:
Input: seats = [[“#”,”.”,”#”,”#”,”.”,”#”],
[“.”,”#”,”#”,”#”,”#”,”.”],
[“#”,”.”,”#”,”#”,”.”,”#”]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don’t cheat on the exam.
Example 2:
Input: seats = [[“.”,”#”],
[“#”,”#”],
[“#”,”.”],
[“#”,”#”],
[“.”,”#”]]
Output: 3
Explanation: Place all students in available seats.
Example 3:
Input: seats = [[“#”,”.”,”.”,”.”,”#”],
[“.”,”#”,”.”,”#”,”.”],
[“.”,”.”,”#”,”.”,”.”],
[“.”,”#”,”.”,”#”,”.”],
[“#”,”.”,”.”,”.”,”#”]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.
Constraints:
seats contains only characters ‘.’ and’#’.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8
Complexity Analysis
- Time Complexity: O(|V||E|) = O(m^2n^2)
- Space Complexity: O(mn)
1349. Maximum Students Taking Exam LeetCode Solution in C++
class Solution {
public:
int maxStudents(vector<vector<char>>& seats) {
return accumulate(seats.begin(), seats.end(), 0,
[&](int subtotal, const auto& seat) {
return subtotal + ranges::count(seat, '.');
}) - hungarian(seats);
}
private:
static constexpr int dirs[6][2] = {{-1, -1}, {0, -1}, {1, -1},
{-1, 1}, {0, 1}, {1, 1}};
int hungarian(const vector<vector<char>>& seats) {
const int m = seats.size();
const int n = seats[0].size();
int count = 0;
vector<vector<int>> seen(m, vector<int>(n));
vector<vector<int>> match(m, vector<int>(n, -1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (seats[i][j] == '.' && match[i][j] == -1) {
const int sessionId = i * n + j;
seen[i][j] = sessionId;
count += dfs(seats, i, j, sessionId, seen, match);
}
return count;
}
int dfs(const vector<vector<char>>& seats, int i, int j, int sessionId,
vector<vector<int>>& seen, vector<vector<int>>& match) {
const int m = seats.size();
const int n = seats[0].size();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seats[x][y] != '.' || seen[x][y] == sessionId)
continue;
seen[x][y] = sessionId;
if (match[x][y] == -1 || dfs(seats, match[x][y] / n, match[x][y] % n,
sessionId, seen, match)) {
match[x][y] = i * n + j;
match[i][j] = x * n + y;
return 1;
}
}
return 0;
}
};
/* code provided by PROGIEZ */1349. Maximum Students Taking Exam LeetCode Solution in Java
class Solution {
public int maxStudents(char[][] seats) {
int studentsCount = 0;
for (char[] seat : seats)
for (final char s : seat)
if (s == '.')
++studentsCount;
return studentsCount - hungarian(seats);
}
private static final int[][] dirs = {{-1, -1}, {0, -1}, {1, -1}, {-1, 1}, {0, 1}, {1, 1}};
private int hungarian(char[][] seats) {
final int m = seats.length;
final int n = seats[0].length;
int count = 0;
int[][] seen = new int[m][n];
int[][] match = new int[m][n];
Arrays.stream(match).forEach(A -> Arrays.fill(A, -1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (seats[i][j] == '.' && match[i][j] == -1) {
final int sessionId = i * n + j;
seen[i][j] = sessionId;
if (dfs(seats, i, j, sessionId, seen, match))
++count;
}
return count;
}
private boolean dfs(char[][] seats, int i, int j, int sessionId, int[][] seen, int[][] match) {
final int m = seats.length;
final int n = seats[0].length;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seats[x][y] != '.' || seen[x][y] == sessionId)
continue;
seen[x][y] = sessionId;
if (match[x][y] == -1 ||
dfs(seats, match[x][y] / n, match[x][y] % n, sessionId, seen, match)) {
match[x][y] = i * n + j;
match[i][j] = x * n + y;
return true;
}
}
return false;
}
}
// code provided by PROGIEZ1349. Maximum Students Taking Exam LeetCode Solution in Python
class Solution:
def maxStudents(self, seats: list[list[str]]) -> int:
m = len(seats)
n = len(seats[0])
dirs = ((-1, -1), (0, -1), (1, -1), (-1, 1), (0, 1), (1, 1))
seen = [[0] * n for _ in range(m)]
match = [[-1] * n for _ in range(m)]
def dfs(i: int, j: int, sessionId: int) -> int:
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if seats[x][y] != '.' or seen[x][y] == sessionId:
continue
seen[x][y] = sessionId
if match[x][y] == -1 or dfs(*divmod(match[x][y], n), sessionId):
match[x][y] = i * n + j
match[i][j] = x * n + y
return 1
return 0
def hungarian() -> int:
count = 0
for i in range(m):
for j in range(n):
if seats[i][j] == '.' and match[i][j] == -1:
sessionId = i * n + j
seen[i][j] = sessionId
count += dfs(i, j, sessionId)
return count
return sum(seats[i][j] == '.'
for i in range(m)
for j in range(n)) - hungarian()
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.