---
tags: leetcode
---

# [362. Design Hit Counter](https://leetcode.com/problems/design-hit-counter/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code1

class HitCounter {
public:
    HitCounter() {

    }

    void hit(int timestamp) {
        record.push_back(timestamp);
    }

    int getHits(int timestamp) {
        if (record.empty() || timestamp < record[0] || 
            record.back() + 300 < timestamp) {
            return 0;
        }

        // Use binary search to fine the first timestamp that is 
        // greater than timestamp - 300.
        int left = 0, right = record.size() - 1, leftTime = timestamp - 300;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (record[middle] <= leftTime) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        int leftIdx = left;
        if (record[left] <= leftTime) {
            leftIdx = left + 1;
        }

        // Use binary search to find the last timestamp that is less than
        // or equal to timestamp.
        left = 0, right = record.size() - 1;
        int rightTime = timestamp;
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (timestamp < record[middle]) {
                right = middle - 1;
            } else {
                left = middle;
            }
        }

        int rightIdx = left;
        if (timestamp < record[left]) {
            rightIdx = left - 1;
        }

        return rightIdx - leftIdx + 1;
    }

private:
    vector<int> record;
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter* obj = new HitCounter();
 * obj->hit(timestamp);
 * int param_2 = obj->getHits(timestamp);
 */

## C++ Code2

struct hits {
    int timestamp;
    int cnt;
    hits(int timestamp, int cnt) : timestamp(timestamp), cnt(cnt) {}
};

class HitCounter {
public:
    HitCounter() {
    }

    void hit(int timestamp) {
        if (records.empty() || records.back().timestamp < timestamp) {
            records.push_back(hits(timestamp, 1));
            return;
        }
        ++records.back().cnt;
    }

    int getHits(int timestamp) {
        int timestamp2 = timestamp - 300;
        if (timestamp2 < 0) {
            timestamp2 = 0;
        }

        if (records.empty() || timestamp < records[0].timestamp || 
            records.back().timestamp <= timestamp2) {
            return 0;
        }

        // Find the time interval.
        // The time interval is defined as (timestamp2, timestamp]
        int leftBound, rightBound;

        // Use binary search to find the left bound.
        // The left bound must be greater than timestamp2.
        int left = 0, right = records.size() - 1;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (records[middle].timestamp <= timestamp2) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        leftBound = left;

        // Use binary search to find the right bound.
        // The right bound must be less than or equal to timestamp.
        left = 0, right = records.size() - 1;
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (timestamp < records[middle].timestamp) {
                right = middle - 1;
            } else {
                left = middle;
            }
        }
        rightBound = left;

        int hitCnt = 0;
        for (int i = leftBound; i <= rightBound; ++i) {
            hitCnt += records[i].cnt;
        }

        return hitCnt;
    }

private:
    vector<hits> records;
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter* obj = new HitCounter();
 * obj->hit(timestamp);
 * int param_2 = obj->getHits(timestamp);
 */

## Time Complexity
* `HitCounter`
$O(1)$
* `hit`
$O(1)$
* `getHits`
$O(logn)$
$n$ is the number of calls made to `hit`.
## Space Complexity
* `HitCounter`
$O(1)$
* `hit`
$O(n)$
$n$ is the number of calls made to `hit`.
* `getHits`
$O(1)$
# Miscellane
<!--
# Test Cases

["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"]
[[],[1],[2],[3],[4],[300],[300],[301]]

["HitCounter","hit","hit","hit","getHits","getHits","getHits","getHits","getHits","hit","getHits"]
[[],[2],[3],[4],[300],[301],[302],[303],[304],[501],[600]]

["HitCounter","getHits","getHits","getHits","hit","hit","getHits"]
[[],[100],[200],[300],[300],[401],[402]]

["HitCounter","hit","hit","hit","hit","hit","getHits"]
[[],[1],[2],[3],[4],[4],[301]]

-->