Leetcode 1349. Maximum Students Taking Exam

Problem Explanation:

In this problem, a classroom seating arrangement is given by a m by n matrix. The goal is to find the maximum number of students that can take an exam together in this classroom while ensuring that no student is able to cheat off another student.

Empty/available seats are represented by the '.' character and broken seats are represented by the '#' character in the matrix. A student can't cheat off of someone if that student to cheat off of is either directly in front of or behind them. Because of this rule, we need to make sure that no two students sit next to each other, either on their direct left, right, upper left, or upper right.

We need to return the maximum number of students that can take the test in this room without the possibility of cheating.

Let's take an example:

Input: seats = [["#",".","#","#",".","#"],   [".","#","#","#","#","."],   ["#",".","#","#",".","#"]]

Empty seats are

• at 2nd column of 1st row,
• at 1st column of 2nd row,
• at 2nd column of 3rd row,

Place students at these locations to maximize the seating arrangement.

Output: 4

Approach:

As this is a tricky problem, a professional technique: the "Hungarian Algorithm", would be used to solve it effectively. This algorithm provides a solution for job assignments based on certain conditions, and in this case, it is being used to assign students to the most optimal seats possible for the test.

Walkthrough:

In the given solution we start by first giving all students their own seat, as we're assuming that all the unbroken seats are filled with students. This is done using the inbuilt accumulate function of C++ where we count the total number of '.' i.e available seats in every row of the seats matrix.

When the Hungarian method is called for the given seats arrangement, it assigns each seat a unique session id which is a unique number for each '.' (i.e. unbroken seat) that comes up when traversing the seats matrix row by row and column by column. If the seat has not been assigned a session id (i.e it's session id is -1), then a depth-first search (DFS) is initiated from that seat.

The DFS algorithm then keeps moving in 6 possible directions (upper left, left, lower left, upper right, right, lower right) until it finds an unvisited available seat. If no such seat is found, it backtracks to the origin seat and starts exploring in another direction. If an available seat is found, it is matched with the origin seat and the DFS ends, increasing the total count of matched seats by 1.

Finally, the algorithm returns the difference between the total number of available seats and the number of matched seats, which is the maximum possible number of students than can take the test under the given conditions.

Code:

Let's discuss the code written in C++.

1
2cpp
3class Solution {
4 public:
5  int maxStudents(vector<vector<char>>& seats) {
6    return accumulate(
7               begin(seats), end(seats), 0,
8               [&](int a, const auto& seat) {
9      return a + count(begin(seat), end(seat), '.');
10               }) -
11        hungarian(seats);
12  }

First, we get a count of all '.'(available seats) in the input. We subtract the result of the hungarian method from this count and return the result.

1
2cpp
3 private:
4  const vector<pair<int, int>> dirs{{-1, -1}, {0, -1}, {1, -1},
5                                    {-1, 1},  {0, 1},  {1, 1}};

These are the 6 possible directions in which the Depth First Search(DFS) can traverse.

1
2cpp
3  int hungarian(const vector<vector<char>>& seats) {
4    const int m = seats.size();
5    const int n = seats[0].size();
6    int count = 0;
7    vector<vector<int>> seen(m, vector<int>(n));
8    vector<vector<int>> match(m, vector<int>(n, -1));

This function initializes the hungarian algorithm. The 2D seen and match vectors have the same dimensions as the given seats grid. We keep a count variable initialized at zero to keep track of the total number of matched seats.

1
2cpp
3    for (int i = 0; i < m; ++i)
4      for (int j = 0; j < n; ++j)
5        if (seats[i][j] == '.' && match[i][j] == -1) {
6          const int sessionId = i * n + j;
7          seen[i][j] = sessionId;
8          count += dfs(seats, i, j, sessionId, seen, match);
9        }

Here we are assigning unique session ids to each unbroken(and unmatched) seat. We start the DFS traversal from that seat. If a match is found as a result of this traversal, we increase our count.

1
2cpp
3  int dfs(const vector<vector<char>>& seats, int i, int j, int sessionId,
4          vector<vector<int>>& seen, vector<vector<int>>& match) {
5    const int m = seats.size();
6    const int n = seats[0].size();

This function takes in the seat grid, the current seat position (i, j), the current sessionId, and the seen and match matrices as parameters, and carries out the DFS traversal from the (i,j) location in one of the six possible directions.

1
2cpp
3    for (const auto& [dx, dy] : dirs) {
4      const int x = i + dx;
5      const int y = j + dy;
6      if (x < 0 || x == m || y < 0 || y == n)
7        continue;
8      if (seats[x][y] != '.' || seen[x][y] == sessionId)
9        continue;
10      seen[x][y] = sessionId;
11      if (match[x][y] == -1 || dfs(seats, match[x][y] / n, match[x][y] % n,
12                                   sessionId, seen)) {
13        match[x][y] = i * n + j;
14        match[i][j] = x * n + y;
15        return 1;
16      }
17    }

This block describes the movement in a specific direction as decided by dirs[][]. Once a direction is decided, we check if the new position (determined by i + dx, j + dy) is valid and not previously travelled in the current session. If the new position is a '.' (unbroken seat) and has not been travelled yet, it is marked as visited and if it is unmatched or can be matched with some other seat by DFS traversal from its matched seat, it is matched with our (i,j) seat and 1 (indicating successful match) is returned.

1
2cpp
3    return 0;
4  }
5};

If no available seat can be found in any direction, the function returns 0 (indicating unsuccessful match).

To solve this problem in Python, Java or JavaScript we can translate the sequence of operations mentioned in above c++ solution to respective syntax of those languages. However, we need to ensure proper translation of variable declarations, function calls, loops, conditionals and return statements.### Python Solution:

Python solution can be implemented using the same Hungarian algorithm as mentioned for the C++ implementation. This solution uses list comprehension for initializing the "seen" and "match" lists.

1
2python
3class Solution:
4    def maxStudents(self, seats: List[List[str]]) -> int:
5        direction = [(-1, -1), (0, -1), (1, -1), (-1, 1), (0, 1), (1, 1)]
6        row_count, col_count = len(seats), len(seats[0])
7
8        def dfs(i, j):
9            for dx, dy in direction:
10                x, y = i + dx, j + dy
11                if 0 <= x < row_count and 0 <= y < col_count and seen[x][y] != i * col_count + j and seats[x][y] == '.':
12                    seen[x][y] = i * col_count + j
13                    if match[x][y] == -1 or dfs(*divmod(match[x][y], col_count)):
14                        match[i][j], match[x][y] = x * col_count + y, i * col_count + j
15                        return True
16            return False
17
18        match = [[-1]*col_count for _ in range(row_count)]
19        seen = [[-1]*col_count for _ in range(row_count)]
20        return sum(seats[i][j] == '.' and (match[i][j] == -1 and dfs(i, j)) for i in range(row_count) for j in range(col_count))

Java Solution:

In Java, ArrayList can be used to hold the matrix data. We just have to translate our C++ vector containers to ArrayList in Java.

1
2java
3class Solution {
4    private static final int[][] dirs = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {-1, 1}, {0, 1}, {1, 1}};
5    private List<List<Integer>> seen, match;
6    private List<List<Character>> seats;
7    private int m, n;
8
9    private boolean dfs(int i, int j) {
10        for (int[] dir : dirs) {
11            int x = i + dir[0], y = j + dir[1];
12            if (x < 0 || x == m || y < 0 || y == n) continue;
13            if (seats.get(x).get(y) != '.' || seen.get(x).get(y) == i * n + j) continue;
14            seen.get(x).set(y, i * n + j);
15            if (match.get(x).get(y) == -1 || dfs(match.get(x).get(y) / n, match.get(x).get(y) % n)) {
16                match.get(i).set(j, x * n + y);
17                match.get(x).set(y, i * n + j);
18                return true;
19            }
20        }
21        return false;
22    }
23
24    public int maxStudents(char[][] seatsChar) {
25        m = seatsChar.length;
26        n = seatsChar[0].length;
27        seats = new ArrayList<>();
28        seen = new ArrayList<>();
29        match = new ArrayList<>();
30        for (char[] row : seatsChar) {
31            List<Character> seatsRow = new ArrayList<>();
32            for (char c : row) seatsRow.add(c);
33            seats.add(seatsRow);
34            seen.add(new ArrayList<>(Collections.nCopies(n, -1)));
35            match.add(new ArrayList<>(Collections.nCopies(n, -1)));
36        }
37
38        int res = 0;
39        for (int i = 0; i < m; ++i)
40            for (int j = 0; j < n; ++j)
41                if (seats.get(i).get(j) == '.' && match.get(i).get(j) == -1)
42                    res += dfs(i, j) ? 1 : 0;
43        return res;
44    }
45}

JavaScript Solution:

1
2javascript
3function maxStudents(seats){
4  let m=seats.length,n=seats[0].length,dirs=[[-1,-1], [0,-1],[1,-1],[-1,1], [0,1],[1,1]];
5  let seen=Array(m).fill().map(_=>Array(n).fill(-1));
6  let match=Array(m).fill().map(_=>Array(n).fill(-1));
7  
8  function dfs(i,j){
9    for(let [dx,dy] of dirs){
10      let x=i+dx,y=j+dy;
11      if(x<0 || x==m || y<0 || y==n || seen[x][y] == i*n + j ||seats[x][y]=="#") continue;
12      seen[x][y] = i*n + j;
13      if(match[x][y]==-1 || dfs(...divmod(match[x][y],n))){
14        match[i][j] = x*n+y;
15        match[x][y] = i*n+j;
16        return true;
17      }
18    }
19    return false;
20  }
21  
22  let c=0;
23  for(let i=0;i<m;i++){
24    for(let j=0;j<n;j++){
25      if(seats[i][j]=='.' && match[i][j]==-1){
26        c+=dfs(i,j)?1:0;
27      }
28    }
29  }
30  return c;
31  
32  function divmod(x,y){
33    return [Math.floor(x/y), x%y];
34  }
35}

Note: In JavaScript, an equivalent of Python's 'divmod' built-in function is used to get the quotient and remainder when dividing, which is not natively supported in JavaScript.