Abstract / Summary

A program tracks phone call times and reports how many happened in the last three seconds.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 76% (300k+ submissions).

Typical patterns to solve this problem:

• Data Stream
• Design
• Queue

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided RecentCounter class implements a simple sliding-window counter for timestamped events. It stores each incoming timestamp in a list called history and, upon each call to ping, removes any timestamps that fall outside a 3000-millisecond window ending at the current timestamp t. The method then returns the number of timestamps that remain, which represents the number of recent pings within the defined interval.

Initialization

The constructor creates an empty list that will hold the timestamps in the order they are received.

def __init__(self):
    self.history = []

Because timestamps are appended in chronological order, the list naturally remains sorted, which simplifies later removal of outdated entries.

Adding a New Timestamp

When ping is invoked, the first operation appends the new timestamp t to the end of history.

self.history.append(t)

Appending to a Python list is an amortized O(1) operation, ensuring that the addition of each new event does not become a bottleneck even when many pings are processed.

Removing Out-of-Range Timestamps

The core logic of the sliding window is expressed by a while loop that checks the oldest timestamp in the list. As long as the oldest entry is less than t - 3000, it is removed from the front of the list.

while self.history[0] < t - 3000:
    del self.history[0]

Because timestamps are stored in chronological order, the oldest element is always at index 0. The loop continues until the first element satisfies the window condition, guaranteeing that all remaining timestamps lie within the inclusive range [t-3000, t].

Edge Cases Handled

The loop implicitly handles the situation where the list contains only the newly added timestamp. In that case, self.history[0] equals t, which is never less than t - 3000, so the loop body is skipped and the list remains unchanged. This covers the edge case of the very first ping as well as the case where all previous timestamps have already expired.

Another edge case occurs when multiple timestamps become obsolete at once. Because the loop repeatedly checks the first element after each deletion, it efficiently discards a contiguous block of outdated entries without requiring additional passes over the list.

Returning the Count

After the outdated timestamps have been removed, the method returns the length of the list, which directly corresponds to the number of pings in the last 3000 milliseconds.

return len(self.history)

Since the list now contains only timestamps within the desired window, the length operation provides the correct count in constant time.

Performance Optimizations

The implementation leverages the fact that timestamps arrive in non-decreasing order. By storing them in a simple list and always deleting from the front, the code avoids the overhead of more complex data structures such as balanced trees or deques. Although deleting the first element of a Python list requires shifting the remaining elements, this cost is amortized across the entire sequence of pings because each timestamp is removed exactly once during its lifetime. Consequently, the total work performed over n pings is proportional to n, providing an efficient overall runtime.

The use of append for insertion and len for counting ensures that the most frequent operations are O(1). The while-loop performs deletions only when necessary, and each deletion reduces the size of the list, preventing unnecessary iterations in future calls. This design results in a tight, low-overhead implementation suitable for high-frequency ping streams.

Imagine a special toy box that keeps track of the little balls you toss inside. When the box is first made, it starts off completely empty so it is ready for your game.

Every time you toss a ball into the box, you give it a secret number that tells the box exactly when that ball arrived. The box puts that number into a growing line inside.

After dropping a ball in, the box checks all the numbers in its line to see if any of them are getting too old. If a ball arrived more than three thousand ticks of the clock ago, it is way too old to be useful anymore. The box finds these old balls at the front of the line and tosses them out one by one until only the fresh, new balls are left inside.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	JS	C#		Go		Rust	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim								C
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	fsq	C++
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	qiyuangong			Java
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
qiyuangong	Java
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality