855. Exam Room LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 855. Exam Room LeetCode Solution with the best time and space complexity. The solution to Exam Room 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.

Problem Statement
Complexity Analysis
Exam Room solution in C++
Exam Room solution in Java
Exam Room solution in Python
Additional Resources

Problem Statement of Exam Room

There is an exam room with n seats in a single row labeled from 0 to n – 1.
When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.
Design a class that simulates the mentioned exam room.
Implement the ExamRoom class:

ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
int seat() Returns the label of the seat at which the next student will set.
void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

Example 1:

Input
[“ExamRoom”, “seat”, “seat”, “seat”, “seat”, “leave”, “seat”]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints:

1 <= n <= 109
It is guaranteed that there is a student sitting at seat p.
At most 104 calls will be made to seat and leave.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(n)

855. Exam Room LeetCode Solution in C++

class ExamRoom {
 public:
  ExamRoom(int n) : n(n) {}

  int seat() {
    if (students.empty()) {
      students.push_back(0);
      map[0] = students.begin();
      return 0;
    }

    int prevStudent = -1;
    int maxDistToClosest = 0;
    int val = 0;              // the inserted value
    list<int>::iterator pos;  // the inserted position

    for (auto it = students.begin(); it != students.end(); ++it) {
      if (prevStudent == -1) {   // We haven't insert anything before.
        maxDistToClosest = *it;  // the distance between it and the begining
        pos = it;
      } else if ((*it - prevStudent) / 2 > maxDistToClosest) {
        maxDistToClosest = (*it - prevStudent) / 2;
        val = (*it + prevStudent) / 2;
        pos = it;
      }
      prevStudent = *it;
    }

    if (n - 1 - students.back() > maxDistToClosest) {
      pos = students.end();
      val = n - 1;
    }

    map[val] = students.insert(pos, val);
    return val;
  }

  void leave(int p) {
    students.erase(map[p]);
  }

 private:
  const int n;
  list<int> students;
  unordered_map<int, list<int>::iterator> map;  // {p: student iterator}
};
/* code provided by PROGIEZ */

855. Exam Room LeetCode Solution in Java

class Node {
  public Node prev;
  public Node next;
  public int value;

  public Node(int value) {
    this.value = value;
  }
}

class ExamRoom {
  public ExamRoom(int n) {
    this.n = n;
    join(head, tail);
  }

  public int seat() {
    if (head.next == tail) {
      Node node = new Node(0);
      join(head, node);
      join(node, tail);
      map.put(0, node);
      return 0;
    }

    int prevStudent = -1;
    int maxDistToClosest = 0;
    int val = 0;     // the inserted value
    Node pos = null; // the inserted position

    for (Node node = head; node != tail; node = node.next) {
      if (prevStudent == -1) {         // We haven't insert anything before.
        maxDistToClosest = node.value; // the distance between it and the begining
        pos = node;
      } else if ((node.value - prevStudent) / 2 > maxDistToClosest) {
        maxDistToClosest = (node.value - prevStudent) / 2;
        val = (node.value + prevStudent) / 2;
        pos = node;
      }
      prevStudent = node.value;
    }

    if (n - 1 - tail.prev.value > maxDistToClosest) {
      pos = tail;
      val = n - 1;
    }

    Node insertedNode = new Node(val);
    join(pos.prev, insertedNode);
    join(insertedNode, pos);

    map.put(val, insertedNode);
    return val;
  }

  public void leave(int p) {
    Node removedNode = map.get(p);
    join(removedNode.prev, removedNode.next);
  }

  private int n;
  private Node head = new Node(-1);
  private Node tail = new Node(-1);
  private Map<Integer, Node> map = new HashMap<>(); // {p: student iterator}

  private void join(Node node1, Node node2) {
    node1.next = node2;
    node2.prev = node1;
  }

  private void remove(Node node) {
    join(node.prev, node.next);
  }
}
// code provided by PROGIEZ

855. Exam Room LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents