LeetCode 355 - Design Twitter

LeetCode Problem 355

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List, Design, Heap (Priority Queue)

Solution

Problem Understanding

This problem asks us to design a simplified version of a social media platform similar to Twitter. The system must support four main operations:

1. Users can post tweets.
2. Users can follow other users.
3. Users can unfollow other users.
4. Users can retrieve a personalized news feed containing the 10 most recent tweets from themselves and the users they follow.

The key challenge is efficiently maintaining tweet ordering by recency while supporting dynamic follow relationships.

Each tweet has a unique tweetId, and tweets are considered more recent based on the order they were posted. The platform does not provide timestamps directly, so we must internally track tweet ordering ourselves.

The getNewsFeed(userId) operation is the most important part of the problem. The returned feed must:

• Include tweets posted by the user themself.
• Include tweets posted by users they currently follow.
• Be ordered from most recent to least recent.
• Contain at most 10 tweets.

The constraints are relatively small:

• User IDs range from 1 to 500
• At most 3 * 10^4 operations occur

Although these limits are not enormous, a naive implementation can still become inefficient if every news feed request scans all tweets globally.

Several edge cases are important:

• A user may request a feed without following anyone.
• A user may never have posted any tweets.
• A user may follow many users with many tweets.
• Unfollowing someone not currently followed should not crash the implementation.
• Users cannot follow themselves, which simplifies some logic.
• News feeds must always contain only the 10 most recent tweets.

The core difficulty is efficiently merging multiple tweet streams while preserving chronological order.

Approaches

Brute Force Approach

The brute force solution stores every tweet globally in chronological order. When generating a news feed for a user, we scan backward through the entire tweet history and collect tweets posted either by:

• the user themself
• users they follow

We stop once we collect 10 tweets.

This approach is correct because scanning from newest to oldest guarantees correct ordering. However, it becomes inefficient as the number of tweets grows. Every getNewsFeed operation may need to inspect thousands of tweets.

If there are T total tweets, each feed query may take O(T) time.

Optimal Approach

The key observation is that tweets are naturally grouped by user. Instead of scanning all tweets globally, we can store each user's tweets separately.

When generating the news feed, we only care about:

• the user's own tweets
• tweets from followed users

Each user already has their tweets ordered chronologically. The problem therefore becomes merging several sorted tweet lists and extracting the 10 most recent tweets.

A max heap is ideal for this.

We place the newest tweet from each relevant user into a heap. Then we repeatedly extract the most recent tweet and insert the next older tweet from that same user. This is essentially the same idea as merging k sorted lists.

Because we only need the top 10 tweets, the heap never grows excessively large.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(T) per feed query	O(T)	Scans all tweets globally
Optimal	O(F log F) per feed query	O(T + F)	Uses heap to merge followed users' tweet streams

Here:

• T = total tweets
• F = number of followed users plus the user themself

Algorithm Walkthrough

Data Structures

We use two main hash maps:

1. follow_map

• Maps a user to the set of users they follow.
• Allows O(1) follow and unfollow operations.

2. tweets

• Maps a user to a list of their tweets.

• Each tweet stores:

• timestamp

• tweet ID

We also maintain a global timestamp counter that increases whenever a tweet is posted.

Feed Generation Strategy

The most important operation is merging multiple users' tweet lists efficiently.

We use a max heap where each heap entry contains:

• negative timestamp
• tweet ID
• user ID
• index of next older tweet

Python's heapq is a min heap, so we negate timestamps to simulate max heap behavior.

Step-by-Step Algorithm

1. Initialize:

• follow_map as a dictionary of sets
• tweets as a dictionary of lists
• timestamp = 0

2. When postTweet(userId, tweetId) is called:

• Append (timestamp, tweetId) to the user's tweet list
• Increment timestamp

3. When follow(followerId, followeeId) is called:

• Add followeeId to the follower's follow set

4. When unfollow(followerId, followeeId) is called:

• Remove followeeId from the follow set if present

5. When getNewsFeed(userId) is called:

6. Build a set containing:

• all followed users
• the user themself

2. For each relevant user:

• take their most recent tweet
• push it into the heap

3. While:

• heap is not empty
• fewer than 10 tweets collected

4. Pop the most recent tweet
5. Add its tweet ID to the result
6. If that user has older tweets:

• push the next older tweet into the heap

7. Return the result list

Why it works

Each user's tweet list is already ordered chronologically. The heap always contains the newest unprocessed tweet from each user stream. By repeatedly extracting the maximum timestamp tweet, we guarantee that tweets are returned globally in descending chronological order. Since we continue pushing older tweets from the same user after extraction, the heap always maintains the next best candidate. This is exactly the same correctness principle used in merging sorted lists.

Python Solution

from typing import List
from collections import defaultdict
import heapq

class Twitter:

    def __init__(self):
        self.timestamp = 0
        self.follow_map = defaultdict(set)
        self.tweets = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        max_heap = []
        result = []

        users = set(self.follow_map[userId])
        users.add(userId)

        for user in users:
            if self.tweets[user]:
                index = len(self.tweets[user]) - 1
                timestamp, tweet_id = self.tweets[user][index]

                heapq.heappush(
                    max_heap,
                    (-timestamp, tweet_id, user, index - 1)
                )

        while max_heap and len(result) < 10:
            neg_timestamp, tweet_id, user, next_index = heapq.heappop(max_heap)

            result.append(tweet_id)

            if next_index >= 0:
                timestamp, next_tweet_id = self.tweets[user][next_index]

                heapq.heappush(
                    max_heap,
                    (-timestamp, next_tweet_id, user, next_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)

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId, tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId, followeeId)
# obj.unfollow(followerId, followeeId)

The implementation begins by initializing three components:

• a timestamp counter
• a follow relationship map
• a per-user tweet storage map

Tweets are stored in chronological order inside each user's list. Every tweet receives a unique timestamp so we can compare recency efficiently.

The postTweet method appends tweets in O(1) time.

The follow and unfollow operations use sets, which provide constant-time insertion and deletion.

The most important logic is inside getNewsFeed. We first gather all relevant users, including the user themself. Then we insert each user's newest tweet into the heap.

Each heap entry remembers where the next older tweet for that user exists. Whenever we pop a tweet from the heap, we immediately insert the next older tweet from the same user if one exists.

This lazy merging strategy avoids inserting every tweet into the heap at once and keeps the algorithm efficient.

Go Solution

package main

import (
	"container/heap"
)

type Tweet struct {
	time    int
	tweetId int
}

type HeapNode struct {
	time      int
	tweetId   int
	userId    int
	nextIndex int
}

type MaxHeap []HeapNode

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i].time > h[j].time
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(HeapNode))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type Twitter struct {
	timestamp int
	followMap map[int]map[int]bool
	tweets    map[int][]Tweet
}

func Constructor() Twitter {
	return Twitter{
		timestamp: 0,
		followMap: make(map[int]map[int]bool),
		tweets:    make(map[int][]Tweet),
	}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.tweets[userId] = append(
		this.tweets[userId],
		Tweet{time: this.timestamp, tweetId: tweetId},
	)

	this.timestamp++
}

func (this *Twitter) GetNewsFeed(userId int) []int {
	result := []int{}
	h := &MaxHeap{}
	heap.Init(h)

	users := map[int]bool{}
	users[userId] = true

	if follows, exists := this.followMap[userId]; exists {
		for user := range follows {
			users[user] = true
		}
	}

	for user := range users {
		tweetList := this.tweets[user]

		if len(tweetList) > 0 {
			index := len(tweetList) - 1
			tweet := tweetList[index]

			heap.Push(h, HeapNode{
				time:      tweet.time,
				tweetId:   tweet.tweetId,
				userId:    user,
				nextIndex: index - 1,
			})
		}
	}

	for h.Len() > 0 && len(result) < 10 {
		node := heap.Pop(h).(HeapNode)

		result = append(result, node.tweetId)

		if node.nextIndex >= 0 {
			nextTweet := this.tweets[node.userId][node.nextIndex]

			heap.Push(h, HeapNode{
				time:      nextTweet.time,
				tweetId:   nextTweet.tweetId,
				userId:    node.userId,
				nextIndex: node.nextIndex - 1,
			})
		}
	}

	return result
}

func (this *Twitter) Follow(followerId int, followeeId int) {
	if _, exists := this.followMap[followerId]; !exists {
		this.followMap[followerId] = make(map[int]bool)
	}

	this.followMap[followerId][followeeId] = true
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
	if _, exists := this.followMap[followerId]; exists {
		delete(this.followMap[followerId], followeeId)
	}
}

/**
 * Your Twitter object will be instantiated and called as such:
 * obj := Constructor()
 * obj.PostTweet(userId, tweetId)
 * param_2 := obj.GetNewsFeed(userId)
 * obj.Follow(followerId, followeeId)
 * obj.Unfollow(followerId, followeeId)
 */

The Go implementation follows the same algorithmic structure as the Python version, but several implementation details differ.

Go requires an explicit heap implementation using the container/heap package. We therefore define a custom MaxHeap type and implement the required interface methods.

Instead of Python tuples, we use structs such as Tweet and HeapNode.

Go maps do not automatically initialize nested maps, so the Follow method checks whether a follower entry exists before inserting into it.

The overall algorithm and complexity remain identical to the Python implementation.

Worked Examples

Example 1

Input:

["Twitter", "postTweet", "getNewsFeed", "follow",
 "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]

Step 1

twitter = Twitter()

Initial state:

Variable	Value
timestamp	0
tweets	{}
follow_map	{}

Step 2

twitter.postTweet(1, 5)

State:

User	Tweets
1	[(0, 5)]

Timestamp becomes 1.

Step 3

twitter.getNewsFeed(1)

Relevant users:

{1}

Heap initialization:

Heap Entry	Meaning
(0, 5)	user 1 newest tweet

Feed extraction:

Extracted Tweet	Result
5	[5]

Output:

[5]

Step 4

twitter.follow(1, 2)

State:

Follower	Following
1	{2}

Step 5

twitter.postTweet(2, 6)

Tweets:

User	Tweets
1	[(0, 5)]
2	[(1, 6)]

Step 6

twitter.getNewsFeed(1)

Relevant users:

{1, 2}

Initial heap:

Timestamp	Tweet
1	6
0	5

Extraction order:

Pop	Result
6	[6]
5	[6, 5]

Output:

[6, 5]

Step 7

twitter.unfollow(1, 2)

Follow state:

Follower	Following
1	{}

Step 8

twitter.getNewsFeed(1)

Only user 1 tweets remain visible.

Output:

[5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(F log F)	Heap operations for followed users
Space	O(T + F)	Tweet storage plus heap usage

The postTweet, follow, and unfollow operations all run in approximately constant time.

The expensive operation is getNewsFeed. Suppose the user follows F users. We initialize the heap with at most one tweet per relevant user. Each heap insertion and removal costs O(log F).

Since we extract at most 10 tweets, the total work remains efficient even if users have large tweet histories.

The total tweet storage requires O(T) space where T is the number of tweets posted overall.

Test Cases

# Example from problem statement
twitter = Twitter()
twitter.postTweet(1, 5)
assert twitter.getNewsFeed(1) == [5]  # single user single tweet

twitter.follow(1, 2)
twitter.postTweet(2, 6)
assert twitter.getNewsFeed(1) == [6, 5]  # followed user tweet appears first

twitter.unfollow(1, 2)
assert twitter.getNewsFeed(1) == [5]  # unfollow removes tweets

# User with no tweets
twitter = Twitter()
assert twitter.getNewsFeed(1) == []  # empty feed

# Multiple tweets same user
twitter = Twitter()
twitter.postTweet(1, 1)
twitter.postTweet(1, 2)
twitter.postTweet(1, 3)

assert twitter.getNewsFeed(1) == [3, 2, 1]  # newest first

# More than 10 tweets
twitter = Twitter()

for i in range(15):
    twitter.postTweet(1, i)

feed = twitter.getNewsFeed(1)

assert len(feed) == 10  # feed capped at 10 tweets
assert feed == [14, 13, 12, 11, 10, 9, 8, 7, 6, 5]

# Multiple followed users
twitter = Twitter()

twitter.postTweet(1, 101)
twitter.postTweet(2, 102)
twitter.postTweet(3, 103)

twitter.follow(1, 2)
twitter.follow(1, 3)

feed = twitter.getNewsFeed(1)

assert feed == [103, 102, 101]  # merged by recency

# Unfollow non-followed user
twitter = Twitter()

twitter.unfollow(1, 2)  # should not crash

assert twitter.getNewsFeed(1) == []

# Follow after tweets already exist
twitter = Twitter()

twitter.postTweet(2, 50)
twitter.follow(1, 2)

assert twitter.getNewsFeed(1) == [50]  # old tweets become visible

# Interleaved posting
twitter = Twitter()

twitter.postTweet(1, 1)
twitter.postTweet(2, 2)

twitter.follow(1, 2)

twitter.postTweet(1, 3)
twitter.postTweet(2, 4)

assert twitter.getNewsFeed(1) == [4, 3, 2, 1]

# User follows many users with sparse tweets
twitter = Twitter()

for user in range(2, 20):
    twitter.follow(1, user)
    twitter.postTweet(user, user * 10)

feed = twitter.getNewsFeed(1)

assert len(feed) == 10  # still limited to 10
assert feed[0] == 190  # newest tweet first

Test	Why
Single tweet example	Validates basic posting and retrieval
Empty feed	Ensures no crashes with missing data
Multiple tweets same user	Confirms chronological ordering
More than 10 tweets	Verifies feed size limit
Multiple followed users	Tests heap merging logic
Unfollow non-followed user	Ensures safe deletion
Follow after tweets exist	Validates visibility of historical tweets
Interleaved posting	Confirms global recency ordering
Many followed users	Stresses heap initialization

Edge Cases

User Has No Tweets and Follows Nobody

A user may request their news feed before ever posting a tweet or following anyone. A naive implementation might assume tweet lists exist and accidentally trigger key errors or index errors.

This implementation handles the case safely because both follow_map and tweets use default empty containers. The heap simply remains empty, and the function returns an empty list.

More Than 10 Available Tweets

A user may have access to hundreds or thousands of tweets across followed users. The problem specifically requires returning only the 10 most recent tweets.

The implementation enforces this using:

while max_heap and len(result) < 10:

This guarantees the feed never exceeds the required size and avoids unnecessary heap operations.

Unfollowing a User Not Currently Followed

Calling unfollow on a user who is not currently followed could cause errors in implementations that blindly remove from sets.

The Python solution uses:

discard()

instead of remove(). Unlike remove, discard does not raise an exception if the element is absent.

Similarly, the Go implementation checks map existence before deletion.

Users With Vastly Different Tweet Counts

One followed user may have thousands of tweets while another has only one. A naive merge implementation might insert every tweet into the heap, causing unnecessary overhead.

This implementation inserts only the newest tweet from each user initially. Older tweets are added lazily only when needed. This keeps heap usage efficient regardless of tweet history size.