LeetCode · #355

Design Twitter Solution

Design a simplified Twitter where users can post tweets, follow/unfollow other users, and retrieve their 10 most recent tweets in their news feed.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #355

🏗️

Pattern

Design — merge k sorted feeds with heap

Implement the Twitter class with four methods: postTweet(userId, tweetId), getNewsFeed(userId) (returns most recent 10 tweets from the user and their followees), follow(followerId, followeeId), and unfollow(followerId, followeeId).

Example

 Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts tweet 5
twitter.getNewsFeed(1); // → [5]
twitter.follow(1, 2); // User 1 follows user 2
twitter.postTweet(2, 6); // User 2 posts tweet 6
twitter.getNewsFeed(1); // → [6, 5] (most recent first)
twitter.unfollow(1, 2); // User 1 unfollows user 2
twitter.getNewsFeed(1); // → [5] (user 2's tweets gone) 

Constraints

 • 1 ≤ userId, followerId, followeeId ≤ 500 • 0 ≤ tweetId ≤ 10⁴ • At most 3 × 10⁴ calls total 

Section Two · Approach 1

Brute Force — Collect & Sort

On getNewsFeed, collect all tweets from the user and their followees into one list, sort by timestamp, and return the top 10. Simple but expensive when users have many tweets.

Why it works

Sorting by timestamp guarantees recency. Taking the first 10 gives the correct feed.

Why we can do better

Problem: Collecting all tweets means iterating over potentially thousands of tweets just to pick 10. Since each user's tweets are already in chronological order, this is a merge k sorted lists problem — a min-heap of size k (where k = number of followed users) merges them in O(10 · log k) instead of sorting everything.

Java — Collect & Sort

 // Pseudocode — full brute force public List<Integer> getNewsFeed(int userId) {
List<int[]> all = new ArrayList<>();
// add all tweets from user + followees with timestamps // sort all by timestamp descending // return first 10 tweet IDs
}

Python — Collect & Sort

 def getNewsFeed(self, userId: int) -> list[int]:
    all_tweets = []
# collect tweets from user + followees with timestamps
all_tweets.sort(key=lambda t: -t[0]) # sort by time desc return [t[1] for t in all_tweets[:10]]

Metric	Value
Time (getNewsFeed)	O(T log T) — T = total tweets from user + followees
Space	O(T)

Section Three · Approach 2

Heap Merge — O(10 · log k)

Each user's tweet list is already sorted by time (newest first). To build a feed, treat each user's list as a sorted stream and merge them with a max-heap keyed by timestamp. Pop 10 times to get the 10 most recent across all followed users.

💡 Mental model: Imagine k newspaper stands, each with papers stacked newest-on-top. You want today's top 10 headlines across all stands. Instead of collecting every paper and sorting, you peek at the top paper from each stand (put them in a heap). Pick the newest headline, then reveal the next paper from that stand. After 10 picks, you have your top-10 headlines without touching most papers.

Data Structures

userTweets: HashMap<userId, List<(time, tweetId)>> — each user's tweets in chronological order.
followees: HashMap<userId, HashSet<followeeId>> — who each user follows.
Global timestamp: Counter incremented with each tweet for ordering.

Algorithm — getNewsFeed

Step 1: Collect the user's own ID + all followee IDs.
Step 2: For each person, if they have tweets, push their most recent tweet into a max-heap (keyed by timestamp).
Step 3: Pop from the heap up to 10 times. After each pop, push the next tweet from that same user (if any).
Step 4: Return the collected tweet IDs.

🎯 When to recognize this pattern:

Merging multiple sorted streams into one — this is the exact same pattern as LC 23 (Merge k Sorted Lists).
The heap holds one element per stream and always yields the global best.
It appears in Twitter feeds, calendar event merging, and multi-way external sort.

Why only 10 pops?:

The problem caps the feed at 10 tweets. We never need to merge the full lists — just pop 10 times from the heap.
This makes getNewsFeed O(10 · log k) = O(log k) regardless of how many tweets exist.

Section Four · Trace

Visual Walkthrough

Trace the example sequence:

Twitter operations — follow graph + heap feed merge

Section Five · Implementation

Code — Java & Python

Java — HashMap + Heap merge

 import java.util.*;
class Twitter {
int time = 0;
Map<Integer, List<int[]>> tweets; // userId → [(time, tweetId)] Map<Integer, Set<Integer>> following; // userId → set of followees public Twitter() {
        tweets = new HashMap<>();
        following = new HashMap<>();
    }
public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>())
              .add(new int[]{time++, tweetId});
    }
public List<Integer> getNewsFeed(int userId) {
// Max-heap: [time, tweetId, userId, index in that user's list] PriorityQueue<int[]> heap =
new PriorityQueue<>((a, b) -> b[0] - a[0]);
Set<Integer> users = new HashSet<>();
        users.add(userId);
if (following.containsKey(userId))
            users.addAll(following.get(userId));
for (int uid : users) {
List<int[]> tws = tweets.get(uid);
if (tws != null && !tws.isEmpty()) {
int idx = tws.size() - 1; // most recent int[] tw = tws.get(idx);
                heap.offer(new int[]{tw[0], tw[1], uid, idx});
            }
        }
List<Integer> feed = new ArrayList<>();
while (!heap.isEmpty() && feed.size() < 10) {
int[] top = heap.poll();
            feed.add(top[1]); // tweetId int nextIdx = top[3] - 1;
if (nextIdx >= 0) {
int[] next = tweets.get(top[2]).get(nextIdx);
                heap.offer(new int[]{next[0], next[1], top[2], nextIdx});
            }
        }
return feed;
    }
public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>())
                 .add(followeeId);
    }
public void unfollow(int followerId, int followeeId) {
Set<Integer> s = following.get(followerId);
if (s != null) s.remove(followeeId);
    }
}

Python — defaultdict + heapq merge

 from collections import defaultdict
import heapq
class Twitter:
def __init__(self):
        self.time = 0
self.tweets = defaultdict(list) # userId → [(time, tweetId)]
self.following = defaultdict(set) # userId → set of followees def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1 def getNewsFeed(self, userId: int) -> list[int]:
        heap = [] # max-heap (negate time)
users = self.following[userId] | {userId}
for uid in users:
if self.tweets[uid]:
                idx = len(self.tweets[uid]) - 1
t, tid = self.tweets[uid][idx]
                heapq.heappush(heap, (-t, tid, uid, idx))

        feed = []
while heap and len(feed) < 10:
            neg_t, tid, uid, idx = heapq.heappop(heap)
            feed.append(tid)
if idx > 0:
                t2, tid2 = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-t2, tid2, uid, idx - 1))
return feed
def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

Section Six · Analysis

Complexity Analysis

Operation	Time	Space	Notes
postTweet	O(1)	O(1)	Append to list
follow / unfollow	O(1)	O(1)	HashSet add/remove
getNewsFeed (brute)	O(T log T)	O(T)	Collect all, sort
getNewsFeed (heap) ← optimal	O(k + 10 log k)	O(k)	k = followees. Init k, pop 10 times.

Overall space:

O(U + T + F) where U = users, T = total tweets, F = total follow relationships.
Each tweet is stored once; the heap is transient (created per getNewsFeed call).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Scenario	Why It Matters
No tweets	getNewsFeed for new user	Heap is empty → return empty list.
Self-follow	follow(1, 1)	User's own tweets should already appear. follow(self) should be harmless (idempotent).
Unfollow not followed	unfollow(1, 99)	Should not throw. Use `discard` or null-check.
More than 10 tweets	User posts 20 tweets	Feed should return exactly 10 most recent.
Multiple users' tweets interleaved	Users post alternately	Heap merge correctly interleaves by timestamp.
Follow then unfollow	Feed should reflect current follow state	getNewsFeed rebuilds sources on each call — no stale data.

⚠ Common Mistake: Forgetting to include the user's own tweets in the feed. The user always sees their own tweets — add userId to the set of sources before merging. Don't require self-follow; handle it implicitly.

← Back to Heap problems

LearningTree

LC 355 · Design Twitter — Solution & Explanation | DSA Guide