This is one of those problems where the clean idea matters more than the amount of code. For 933. Number of Recent Calls, the solution in this repository is mainly a data structure design solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design, sliding window.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are ping.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Write a class RecentCounter to count recent requests.
03
04It has only one method: ping(int t), where t represents some time in milliseconds.
05
06Return the number of pings that have been made from 3000 milliseconds ago until now.
07
08Any ping with time in [t - 3000, t] will count, including the current ping.
09
10It is guaranteed that every call to ping uses a strictly larger value of t than before.
11
12
13
14Example 1:
15
16Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
17Output: [null,1,2,3,3]
18
19
20Note:
21
22Each test case will have at most 10000 calls to ping.
23Each test case will call ping with strictly increasing values of t.
24Each call to ping will have 1 <= t <= 10^9.
25**/
26
27//Your runtime beats 31.89 % of cpp submissions.
28class RecentCounter {
29public:
30 queue<int> q;
31
32 RecentCounter() {
33 }
34
35 int ping(int t) {
36 q.push(t);
37 while(q.front()<t-3000){
38 q.pop();
39 }
40 return q.size();
41 }
42};
43
44/**
45 * Your RecentCounter object will be instantiated and called as such:
46 * RecentCounter* obj = new RecentCounter();
47 * int param_1 = obj->ping(t);
48 */
49
50 /**
51 Solution
52Approach 1: Queue
53Intuition
54
55We only care about the most recent calls in the last 3000 ms, so let's use a data structure that keeps only those.
56
57Algorithm
58
59Keep a queue of the most recent calls in increasing order of t. When we see a new call with time t,
60remove all calls that occurred before t - 3000.
61**/
62
63/**
64Complexity Analysis
65
66Time Complexity: O(Q), where Q is the number of queries made.
67
68Space Complexity: O(W), where W = 3000 is the size of the window we should scan for recent calls.
69In this problem, the complexity can be considered O(1).
70**/Cost