Maximum Students Taking Exam LeetCode solution in JavaScript

1
var maxStudents = function (seats) {
2
  if (!seats.length) return 0;
3

4
  // precalculate the seat that will be off the matrix
5
  const lastPos = 1 << seats[0].length;
6
  // encode the classroom into binary where 1 will be an available seat and 0 will be a broken seat
7
  const classroom = seats.map((row) =>
8
    row.reduce((a, c, i) => (c === "#" ? a : a | (1 << i)), 0)
9
  );
10

11
  // create a store to store the max seating for each row arrangment
12
  // each row will be off +1 of seats rows
13
  const dp = new Array(seats.length + 1).fill(null).map(() => new Map());
14
  // since no one can sit at row=-1 set the max number of no one sitting on that row as 0
15
  dp[0].set(0, 0);
16

17
  // iterate through every row in seats matrix
18
  // remember that dp's rows are +1 of seats rows
19
  for (let row = 0; row < seats.length; row++) {
20
    // start with no one sitting on the row
21
    let queue = [0];
22
    // this will count the number of students sitting on this row
23
    // we will increment this up as we add students to the row
24
    let numStudents = 0;
25

26
    while (queue.length > 0) {
27
      // this will store all the different arrangments possible when we add 1 more student from the previous
28
      const next = [];
29

30
      // iterate through all the previous arrangements
31
      // calculate the maximum number of students that can sit on current and all previous rows
32
      // try adding a student to all possible available seats meeting the rules of the game
33
      for (let arrangement of queue) {
34
        // this calculates the maximum number of students that can sit with this row arrangment
35
        // if the arrangement doesn't allow any students to sit in the previous row this will be handled
36
        // by the 0 case in the previous row
37
        // *see helper function that checks to see if the arrangement conflicts with the previous arrangment
38
        let max = 0;
39
        for (let [prevArrang, count] of dp[row]) {
40
          if (conflicts(prevArrang, arrangement)) continue;
41
          max = Math.max(max, count + numStudents);
42
        }
43
        dp[row + 1].set(arrangement, max);
44

45
        // try adding an additional student to all elements in the row checking if it conflicts
46
        // arrangement | i  => adds the student to the arrangement
47
        for (let i = 1; i < lastPos; i <<= 1) {
48
          if (canSit(classroom[row], arrangement, i))
49
            next.push(arrangement | i);
50
        }
51
      }
52

53
      queue = next;
54
      numStudents++;
55
    }
56
  }
57

58
  // return the maximum value from the last row
59
  // the last row holds the maximum number of students for each arrangment
60
  return Math.max(...dp[seats.length].values());
61
};
62

63
// this checks if the there are any students to the left or right of current arrangment
64
// curr << 1 => checks if there are any students to the left
65
// curr >> 1 => check if there are any students to the right
66
function conflicts(prev, curr) {
67
  return prev & (curr << 1) || prev & (curr >> 1);
68
}
69

70
// this checks if we can place the new student in this spot
71
// row & newStudent => checks if the classroom's row's seat is not broken
72
// arrangment & newStudent => will return truthy if there is a student sitting in that position (so we ! it because we don't want anyone sitting there)
73
// arrangement & (newStudent << 1) => will return truthy if there is a student sitting to the left of that position (so we ! it because we don't want anyone sitting there)
74
// arrangement & (newStudent >> 1) => will return truthy if there is a student sitting to the right of that position (so we ! it because we don't want anyone sitting there)
75
function canSit(row, arrangement, newStudent) {
76
  return (
77
    row & newStudent &&
78
    !(arrangement & newStudent) &&
79
    !(arrangement & (newStudent << 1)) &&
80
    !(arrangement & (newStudent >> 1))
81
  );
82
}