# TreeSet solution

• The idea is to use a node to record:

1. how many times a timestamp is hit and
2. how many hits in the last 300 seconds.

The nodes are organised into a binary search tree,

When adding a new node at the end, we use the last node's accumulated count minus count of all nodes in the front which fall outside of the window.

In the test cases getHits can use a timestamp which is bigger than the last hit timestamp, therefore I added the weird overload `hit(int, boolean)`.

``````public class HitCounter {

private static class CountNode {
int selfCount; //just this second
int accumulatedCount; //300 from here.

CountNode(int selfCount, int accumulatedCount) {
this.selfCount = selfCount;
this.accumulatedCount = accumulatedCount;
}

void increase() {
this.selfCount++;
this.accumulatedCount++;
}
}

private static final int PERIOD = 300;
private TreeMap<Integer, CountNode> index = new TreeMap<>();

/**
* Initialize your data structure here.
*/
public HitCounter() {
}

/**
* Record a hit.
*
* @param timestamp - The current timestamp (in seconds granularity).
*/
public void hit(int timestamp) {
hit(timestamp, true);
}

private void hit(int timestamp, boolean hit) {

Map.Entry<Integer, CountNode> last = index.lastEntry();
if (last == null) {
if (hit)
index.put(timestamp, new CountNode(1, 1));
} else {
if (last.getKey() == timestamp) {
if (hit)
last.getValue().increase();
} else {
int minKey = timestamp - PERIOD + 1; //inclusive
if (last.getKey() < minKey) {
index.clear();
if (hit)
index.put(timestamp, new CountNode(1, 1));
} else {
int totalSoFar = last.getValue().accumulatedCount;
while (index.firstKey() < minKey) {
totalSoFar -= index.pollFirstEntry().getValue().selfCount;
}
int val = hit ? 1 : 0;
index.put(timestamp, new CountNode(val, totalSoFar + val));
}
}
}
}

/**
* Return the number of hits in the past 5 minutes.
*
* @param timestamp - The current timestamp (in seconds granularity).
*/
public int getHits(int timestamp) {
hit(timestamp, false); //push timestamp forward
Map.Entry<Integer, CountNode> entry = index.floorEntry(timestamp);
if (entry == null)
return 0;
return entry.getValue().accumulatedCount;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.