---
tags: data_structure_python
---

# Most Booked Hotel Room <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a hotel which has 10 floors `[0-9]` and each floor has 26 rooms `[A-Z]`. You are given a sequence of rooms, where `+` suggests room is booked, `-` room is freed. You have to find which room is booked maximum number of times.

You may assume that the list describe a correct sequence of bookings in chronological order; that is, only free rooms can be booked and only booked rooms can be freeed. All rooms are initially free. Note that this does not mean that all rooms have to be free at the end. In case, 2 rooms have been booked the same number of times, return the lexographically smaller room.

You may assume:

- N (length of input) is an integer within the range [1, 600]
- each element of array A is a string consisting of three characters: "+" or "-"; a digit "0"-"9"; and uppercase English letter "A" - "Z"
- the sequence is correct. That is every booked room was previously free and every freed room was previously booked.

**Example:**

Input: ["+1A", "+3E", "-1A", "+4F", "+1A", "-3E"]
Output: "1A"
Explanation: 1A as it has been booked 2 times.

# Solution

def most_booked_hotel_room(L):
    # n = # elt in L.
    # Time complexity: O(n). 
    # Space complexity: O(1). Hashmap cannot have more than 260 elements -> constant.

    # 1. Build hashmap.
    hashmap = {}
    # 2. Add elt of L in hashmap. hashmap[elt] = [count, book]
    for elt in L:
        if elt[1:] not in hashmap:
            hashmap[elt[1:]] = [1, 0]
        else:
            if elt[0] == '+': 
                # count += 1
                hashmap[elt[1:]][0] += 1
            else:
                # count -= 1
                hashmap[elt[1:]][0] -= 1

        if hashmap[elt[1:]][0] == 1:
            # book += 1
            hashmap[elt[1:]][1] += 1

    # 3. Find the largest 'book' in the hashmap and return its key.
    max = -float("inf")
    room = None
    for key, value in hashmap.items():
        # book.
        if value[1] > max:
            max = value[1]
            room = key
    return room