Leet Code 75–933. Number of Recent Calls

This is an easy problem from Leet Code 75 with the description being:

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.

int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100); // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001); // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:
1 <= t <= 109
Each test case will call ping with strictly increasing values of t.
At most 104 calls will be made to ping.

At first hand the simplest way would be just a creation of a list to store the data and then make checks to make sure those numbers are inclusive to the range specified by the problem:

class RecentCounter {

    final List<Integer> requests = new ArrayList<>();

    public int ping(int t) {

        requests.add(t);

        final int min = t - 3000;
        final int max = t;

        return (int) requests.stream().filter(r -> r >= min && r <= max).count();
    }   
}

Runtime: 2661 ms, faster than 5.01% of Java online submissions for Number of Recent Calls.
Memory Usage: 54.4 MB, less than 19.84% of Java online submissions for Number of Recent Calls.

But looking further into the problem it states that every new ping has bigger value, meaning that the old values fades and will never be used again.

With that in mind a queue makes more sense since you can remove previous times that no longer need to be taken into account:

class RecentCounter {

    final ArrayDeque<Integer> requests = new ArrayDeque<>();

    public int ping(int t) {

        // add into requests queue
        requests.add(t);

        // define min possible amount
        final int min = t - 3000;

        // remove all ones that doesn't go into min possible
        while(requests.peek() < min) { 
            requests.poll();
        }

        return requests.size();
    }

}

Runtime: 17 ms, faster than 98.80% of Java online submiseu jsions for Number of Recent Calls.
Memory Usage: 55.5 MB, less than 6.02% of Java online submissions for Number of Recent Calls.

---

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)