LeetCode #355 Medium

Design Twitter

Design posting, following, unfollowing, and a news feed containing the ten newest visible tweet IDs.

designheaphash-tablek-way-merge

02

Intuition

The direct way to build a feed is to collect every tweet written by the user and their followees, sort the whole collection by time, and take ten. That repeats a large sort even though each user's own tweets are already in chronological order and only ten results matter. Treat those per-user histories as sorted streams: place the newest tweet from each stream in a max-heap, remove the newest candidate, then expose only the previous tweet from that same user. This is the same k-way merge idea used for sorted lists, but performed from newest to oldest and stopped after ten pops.

How to spot this pattern

The output asks for only the newest few items drawn from several histories that are individually ordered. That shape is a bounded k-way merge: keep one frontier item per history in a heap and advance only the history that supplied the item you remove.

03

Approach

1

Give every posted tweet a comparable timestamp

Maintain one increasing counter and store (time, tweetId) in the posting user's list. The counter provides a total order even when several users post, while appending keeps every individual list sorted from oldest to newest. Follow relationships live in sets so duplicate follows do not create duplicate feed entries.

2

Seed the feed heap with one tweet per visible user

The user's feed includes their own tweets as well as tweets from followed accounts. For each such account with a non-empty history, push only its newest tweet into a max-heap, together with the user and index it came from. Older tweets from that account cannot beat its newest one, so pushing the entire history would add work without changing the next choice.

3

Merge backward and stop after ten tweets

Pop the newest heap entry, append its tweet ID, and if that user has an earlier tweet, push that predecessor. The heap therefore always contains the newest unconsumed tweet from every active history. Stop after ten results because anything left is older than every returned tweet and cannot affect the requested feed.

04

Solution

▶1class Twitter:
▶2    def __init__(self):
▶3        self.time = 0
▶4        self.tweets = collections.defaultdict(list)
▶5        self.following = collections.defaultdict(set)
▶6 
▶7    def postTweet(self, userId: int, tweetId: int) -> None:
▶8        self.time += 1
▶9        self.tweets[userId].append((self.time, tweetId))
▶10 
▶11    def getNewsFeed(self, userId: int) -> List[int]:
▶12        heap = []
▶13        visible_users = self.following[userId] | {userId}
▶14 
▶15        for user in visible_users:
▶16            if self.tweets[user]:
▶17                index = len(self.tweets[user]) - 1
▶18                time, tweet_id = self.tweets[user][index]
▶19                heapq.heappush(heap, (-time, tweet_id, user, index))
▶20 
▶21        feed = []
▶22        while heap and len(feed) < 10:
▶23            negative_time, tweet_id, user, index = heapq.heappop(heap)
▶24            feed.append(tweet_id)
▶25 
▶26            if index > 0:
▶27                previous_index = index - 1
▶28                time, previous_tweet = self.tweets[user][previous_index]
▶29                heapq.heappush(heap, (-time, previous_tweet, user, previous_index))
▶30 
▶31        return feed
▶32 
▶33    def follow(self, followerId: int, followeeId: int) -> None:
▶34        self.following[followerId].add(followeeId)
▶35 
▶36    def unfollow(self, followerId: int, followeeId: int) -> None:
▶37        self.following[followerId].discard(followeeId)

05

Common pitfalls

Pushing every historical tweet

✗ Wrong

for time, tweet_id in self.tweets[user]:

✓ Right

time, tweet_id = self.tweets[user][index]

Only the newest tweet from each user can be the next feed item. Adding entire histories makes a feed request grow with all stored tweets.

Forgetting the user's own posts

✗ Wrong

visible_users = self.following[userId]

✓ Right

visible_users = self.following[userId] | {userId}

A user's feed always includes their own tweets even though following themselves is not required.

Returning more than ten items

✗ Wrong

while heap:

✓ Right

while heap and len(feed) < 10:

The contract limits the feed to ten tweets; continuing the merge wastes work and returns an invalid result.

06

Edge cases

A user follows nobody and has never posted

No history contributes a heap entry, so the loop returns an empty feed.

A user follows the same account repeatedly

The followee set stores that account once, preventing duplicate copies of its tweets in the feed.

A user unfollows themselves

Their ID is added explicitly to the visible-user set during feed construction, so their own tweets remain visible as required.

07

Complexity

Time

O((F + 10) log F) per feed request

Space

O(T + R)

F is the number of visible users, T the stored tweets, and R the follow relationships.