// MARK: - 380. Insert Delete GetRandom O(1)

import Foundation

class RandomizedSet {
    // Число - ключ, индекс в массиве - заначение
    var numDict: [Int:Int]
    var numList: [Int]

    init() {
        numDict = [:]
        numList = []
    }

    func insert(_ val: Int) -> Bool {
        // Значение присутствует, тогда возвращаем isIn = true, иначе false
        let isNotIn = numDict[val] == nil ? true : false

        if isNotIn {
            // Значение - это в конец нашего листа
            numDict[val] = numList.count
            numList.append(val)
        }

        return isNotIn
    }


    // работает и для массива где 1 элемент
    func remove(_ val: Int) -> Bool {
        // Нужно чтобы значение было в словаре
        let isIn = self.numDict[val] != nil ? true : false

        if isIn {
            // получим индекс по которому надо удалить из листа
            let index = numDict[val]
            // теперь нужно взять последнее значение в массиве и перетащить на этот индекс
            let lastValue = numList.last!
            numList[index!] = lastValue
            numList.popLast()
            // Меняем значение в словаре для "последнего" элемента
            numDict[lastValue] = index
            // удалим значение из словаря - обязательно только в конце!!!
            numDict[val] = nil
        }
        return isIn
    }

    func getRandom() -> Int {
        let randomIndex = Int.random(in: 0..<numList.count)
        return numList[randomIndex]
    }
}