Leetcode 355 - Design Twitter
Understanding the Problem
The goal is to design a simplified version of Twitter that supports:
- Posting tweets
- Following and unfollowing users
- Retrieving the 10 most recent tweets from a user's news feed
A user's news feed should contain:
- Their own tweets
- Tweets from users they follow
- Tweets ordered from newest to oldest
The main challenge is efficiently retrieving the latest 10 tweets.
A straightforward solution would be:
- Collect all tweets from the user and everyone they follow.
- Sort them by timestamp.
- Return the latest 10 tweets.
However, this approach does unnecessary work because we only need 10 tweets.
The key observation is:
Tweets from each user are already sorted by time, so instead of looking at every tweet, we can merge multiple sorted tweet lists using a heap.
This is the same idea as k-way merge.
Data Structure Design
1. Tweet Map
Stores all tweets posted by each user.
Example:
Tweets are stored in chronological order.
2. Follow Map
Stores the users that each user follows.
Example:
3. Timestamp Counter
A global counter gives every tweet a unique timestamp.
This allows tweets from different users to be compared chronologically.
Optimal Approach Intuition
The key observation:
Each user's tweets are already sorted by time.
Example:
The news feed is simply the merge of these sorted lists.
Instead of putting every tweet into a heap, we only maintain the newest available tweet from each user.
Why Not Add All Tweets?
Suppose:
A brute force approach processes:
to return:
Most of the work is unnecessary.
The heap only limits the number of tweets stored, but it does not reduce the number of tweets examined.
How the Optimal Approach Works
Step 1: Add the Latest Tweet From Each User
Suppose:
Instead of adding all tweets:
we only add:
The heap contains the best current candidate from each user.
Step 2: Remove the Newest Tweet
The heap gives:
because it is the newest tweet.
Add it to the feed:
Now we reveal the next tweet from User B:
and add it to the heap.
Heap:
Step 3: Repeat Until We Have 10 Tweets
Repeat:
- Remove the newest tweet from the heap.
- Add it to the result.
- Add the next older tweet from the same user.
Stop after collecting 10 tweets.
Why This Works
If a user's newest tweet has not been selected, none of their older tweets can be selected.
Example:
If A100 is still in the heap:
- A99 cannot be newer than A100.
- A98 cannot be newer than A99.
Therefore, there is no reason to consider A99 or A98 yet.
We process tweets lazily and only reveal older tweets when needed.
Solution Implementation
from collections import defaultdict
import heapq
from typing import List
class Twitter:
def __init__(self):
self.tweet_map = defaultdict(list)
self.follow_map = defaultdict(set)
self.time = 0
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweet_map[userId].append((self.time, tweetId))
self.time += 1
def getNewsFeed(self, userId: int) -> List[int]:
result = []
heap = []
# User should see their own tweets
self.follow_map[userId].add(userId)
# Add newest tweet from every followee
for user in self.follow_map[userId]:
if self.tweet_map[user]:
index = len(self.tweet_map[user]) - 1
time, tweetId = self.tweet_map[user][index]
heapq.heappush(
heap,
(-time, tweetId, user, index - 1)
)
# Extract newest 10 tweets
while heap and len(result) < 10:
time, tweetId, user, index = heapq.heappop(heap)
result.append(tweetId)
# Add next older tweet from the same user
if index >= 0:
actual_time, next_tweet = self.tweet_map[user][index]
heapq.heappush(
heap,
(-actual_time, next_tweet, user, index - 1)
)
return result
def follow(self, followerId: int, followeeId: int) -> None:
self.follow_map[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.follow_map[followerId].discard(followeeId)
Complexity Analysis
Let:
F= number of users followedT= total number of tweets stored
Time Complexity
Initial Heap Creation
We insert one tweet from each followee:
Retrieving 10 Tweets
Each heap operation:
For 10 tweets:
Overall:
Since 10 is constant:
Time Complexity: O(F log F)
Space Complexity
Tweet Storage
Stores all tweets:
Follow Relationships
Stores follow connections:
Heap
Stores one candidate tweet per followee:
Overall:
Space Complexity: O(T + F)
Key Takeaways
- A heap does not automatically make a solution efficient.
- The important question is: how many elements enter the heap?
- Keeping heap size at 10 only limits memory usage.
- It does not reduce the number of tweets processed.
- When multiple sources are already sorted, think about k-way merge.
- Store only the best current candidate from each source.
- Reveal the next candidate only when needed.
- This pattern appears in:
- Merge K Sorted Lists
- Merge K Sorted Arrays
- Top K problems
Common Mistakes
Mistake 1: Adding Every Tweet Into the Heap
Problem:
- Too many heap operations.
- Processes tweets that may never appear in the feed.
Fix:
- Add only the newest tweet from each user.
- Add older tweets only after selecting a newer tweet from that user.
Mistake 2: Confusing Heap Size With Efficiency
Example:
This only controls memory usage.
It does not reduce the number of tweets processed.
The important question is:
How many tweets are inserted into the heap?
Mistake 3: Timestamp and Heap Ordering Mismatch
Python provides a min heap.
If timestamps increase:
the oldest tweet has priority.
To get newest tweets first, store negative timestamps:
Now the smallest value represents the newest tweet.