C# O(1) Leave O(n) Seat
\nVery similar to other solutions, but since no two people will ever sit in the same place at the same time, we can store our linked list nodes in a dictionary 
\nVery similar to other solutions, but since no two people will ever sit in the same place at the same time, we can store our linked list nodes in a dictionary for quick lookup to remove them. Since we store the linked list node instead of just the value, we can do a O(1) removal because the linked list does not have to find the node. \n\nIt seems like a small improvement. But it beat ~94% of others for time in C#. \n\n```\npublic class ExamRoom {\n\n    private Dictionary<int, LinkedListNode<int>> map = new Dictionary<int, LinkedListNode<int>>();//Pointers to the linked list nodes in the list below\n    private LinkedList<int> seats = new LinkedList<int>();//A sorted list of the seats taken\n    private int n;\n    \n    public ExamRoom(int n) {\n        this.n = n;\n    }\n    \n    public int Seat() {\n        \n        if(seats.Count < 1)//Handle empty edge case\n        {\n            map[0] = seats.AddFirst(0);\n            return 0;\n        }\n        \n        int first = seats.First.Value;//the max distance if we seat at 0\n        int mid = Int32.MinValue;//Computed below. The max distance for and seat in-between other seats\n        int last = n - seats.Last.Value - 1;//the max distance if we seat at n-1\n        \n        \n        LinkedListNode<int> before = null;\n        for(LinkedListNode<int> l = seats.First; l != null && l.Next != null; l = l.Next)\n        {\n            int dist = ComputeMinDist(l, l.Next);\n            if(dist > mid)\n            {\n                before = l;\n                mid = dist;\n            }\n        }\n    \n        \n        if(first >= mid && first >= last)//favor the first spot since it\'s the smallest seat number\n        {\n            map[0] = seats.AddFirst(0);\n            return 0;\n        }\n        else if(mid >= first && mid >= last)//else favor the middle spots their seat numbers are smaller than the end\n        {\n            int val = before.Value + ((before.Next.Value - before.Value) / 2);\n            map[val] = seats.AddAfter(before, val);\n            return val;\n        }\n        else//last favor the end spot \n        {\n            map[n-1] = seats.AddLast(n-1);\n            return n-1;\n        }\n    }\n    \n\n    private int ComputeMinDist(LinkedListNode<int> one, LinkedListNode<int> two)\n    {\n        int netDist = two.Value - one.Value - 1;//get the empty spaces between\n        if(netDist%2 == 0)//if it\'s even, use dist/2 because one side will be shorter\n            return (netDist/2);\n        else//if it\'s odd, add one since there will be even spacing on either side\n            return netDist/2 + 1;\n        \n    }\n    \n\n    public void Leave(int p) \n    {\n        LinkedListNode<int> target = map[p];//get the node from the map\n        seats.Remove(target);//remove it from the linked list (this is O(1) since we pass the node in instead of the value)\n        map.Remove(p);//remove the node from the map so the space is opened up again\n    }\n}\n```
[]