// MARK: - 362. Design Hit Counter

// - Заполняем массив секундами когда было нажатие
// - Бинарником находим индекс элемента и до самого конца по индексам считаем сколько там элементов

class HitCounter {

    var hits: [Int] = []

    init() {}

    func hit(_ timestamp: Int) {
        hits.append(timestamp)
    }


    // timestamp - временная отметка сейчас
    // надо найти за последние 300 сек
    func getHits(_ timestamp: Int) -> Int {
        // бинарник, например нужно найти кол-во нажатий за последние 350с, тогда 350-300 = 50
        // Нужно найти в массиве 50, узнать его индекс - это будет l и с него до конца считать

        var left = 0
        var right = hits.count - 1

        let target = timestamp - 300
        // двигаем указатели, пока границы не будут удовлетворять промежутку
        // left - должен быть настолько маленьким, насколько возможно

        // Имея число(target) нужно найти его индекс в массиве
        while left <= right {
            let mid = (left+right)/2

            // тут <= так как когда найдем, нужно это число не включать (left должен быть +1)
            // [1, 2, 3, ..., 301] - за последние 300 секунд - это 301-300 = 1
            // надо считать от 1, не включая ее - [2, 3, ..., 301]

            if hits[mid] <= target {
                left = mid + 1
            } else if hits[mid] > target {
                right = mid - 1
            }
        }

        // вычитаем так как хотим найти кол-во переходящих секунд между
        return hits.count - left
    }
}

let counter = HitCounter()
counter.hit(1)
counter.hit(2)
counter.hit(3)
counter.getHits(4)
counter.hit(300)
counter.getHits(300)
counter.getHits(301)