362. 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