Design Twitter

Medium · Heap / Priority Queue · Explanation and code example

Heap (Optimal)

How it works

The basic heap solution looks at all tweets of all followees, which is fast enough but can be improved.

Key observation:

Each user only cares about the latest 10 tweets, because the news feed returns at most 10 items.
So for each user, instead of storing all tweets, store only their 10 most recent tweets.
This reduces:
- Memory usage
- Heap operations
- Time per query

The trick:

When a user posts a tweet, append it with a decreasing timestamp (count) and keep only the last 10 tweets.
When getting the news feed:
- If the user follows many people (>= 10), keep only the 10 followees with the newest latest tweet by using a max-heap of size 10.
- This is safe: if a followee's newest tweet is already too old, none of their older tweets can make the final 10.
- Otherwise, push the latest tweet from each followee into a min-heap and keep expanding from the same user after each pop.
In both cases, we never process more than 10 tweets per followee, and never extract more than 10 results.

This makes the method very fast even when users post a lot of tweets.

Steps

postTweet(user, tweetId)
- Insert (timestamp, tweetId) at the end of that user's list.
- If the list grows beyond 10, remove the oldest tweet.
- Decrease global timestamp so newer tweets have smaller values.
getNewsFeed(user) Steps:
- Ensure user follows themselves.
- If followees >= 10:
  - Build a max-heap that keeps only the 10 newest latest tweets from followees.
  - Move them into a min-heap for final processing.
  - After popping a tweet, push the next older tweet from that same followee.
- Else:
  - Push the newest tweet from each followee into a min-heap.
- Repeatedly pop from the heap:
  - Add the tweet to the result
  - Push the next tweet from the same followee (if exists)
  - Stop after 10 tweets
- Return the collected tweets.
follow(follower, followee)
- Add followee to follower's follow-set
unfollow(follower, followee)
- Remove the followee if present

Complexity

Time complexity: O(n) for each getNewsFeed() call and O(1) for remaining methods.
Space complexity: O(N * m + N * M + n)

Where n is the total number of followeeIds associated with the userId, m is the maximum number of tweets by any user (m can be at most 10), N is the total number of userIds and M is the maximum number of followees for any user.

Things to watch for

Forgetting to Include User's Own Tweets

When building the news feed, a user should see their own tweets in addition to tweets from people they follow. A common mistake is only iterating through followees without including the user themselves.

Using Wrong Heap Type or Direction

The heap-based solution requires careful attention to whether you need a min-heap or max-heap. Since we want the most recent tweets (highest timestamp), using a min-heap requires negating timestamps, while a max-heap extracts them directly.

Allowing Self-Follow in Follow Method

While the news feed logic may internally add the user to their own follow set, the follow() method should prevent explicit self-following to avoid duplicate entries or unexpected behavior.

Python code example

from typing import List
from collections import defaultdict
import heapq

class Twitter:

    def __init__(self):
        self.count = 0
        self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
        self.followMap = defaultdict(set)  # userId -> set of followeeId

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        if len(self.tweetMap[userId]) > 10:
            self.tweetMap[userId].pop(0)
        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        minHeap = []
        self.followMap[userId].add(userId)
        if len(self.followMap[userId]) >= 10:
            maxHeap = []
            for followeeId in self.followMap[userId]:
                if followeeId in self.tweetMap:
                    index = len(self.tweetMap[followeeId]) - 1
                    count, tweetId = self.tweetMap[followeeId][index]
                    heapq.heappush(maxHeap, [-count, tweetId, followeeId, index - 1])
                    if len(maxHeap) > 10:
                        heapq.heappop(maxHeap)
            while maxHeap:
                count, tweetId, followeeId, index = heapq.heappop(maxHeap)
                heapq.heappush(minHeap, [-count, tweetId, followeeId, index])
        else:
            for followeeId in self.followMap[userId]:
                if followeeId in self.tweetMap:
                    index = len(self.tweetMap[followeeId]) - 1
                    count, tweetId = self.tweetMap[followeeId][index]
                    heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)

C++ code example

class Twitter {
public:
    int count;
    unordered_map<int, vector<pair<int,int>>> tweetMap;
    unordered_map<int, unordered_set<int>> followMap;

    Twitter() {
        count = 0;
    }

    void postTweet(int userId, int tweetId) {
        tweetMap[userId].push_back({count, tweetId});
        if (tweetMap[userId].size() > 10) {
            tweetMap[userId].erase(tweetMap[userId].begin());
        }
        count--;
    }

    vector<int> getNewsFeed(int userId) {
        vector<int> res;
        followMap[userId].insert(userId);
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
        if (followMap[userId].size() >= 10) {
            priority_queue<vector<int>> maxHeap;
            for (auto f : followMap[userId]) {
                if (!tweetMap.count(f)) continue;
                int idx = tweetMap[f].size() - 1;
                auto &p = tweetMap[f][idx];
                maxHeap.push({-p.first, p.second, f, idx - 1});
                if (maxHeap.size() > 10) maxHeap.pop();
            }
            while (!maxHeap.empty()) {
                auto t = maxHeap.top();
                maxHeap.pop();
                minHeap.push({-t[0], t[1], t[2], t[3]});
            }
        } else {
            for (auto f : followMap[userId]) {
                if (!tweetMap.count(f)) continue;
                int idx = tweetMap[f].size() - 1;
                auto &p = tweetMap[f][idx];
                minHeap.push({p.first, p.second, f, idx - 1});
            }
        }
        while (!minHeap.empty() && res.size() < 10) {
            auto t = minHeap.top();
            minHeap.pop();
            res.push_back(t[1]);
            int idx = t[3];
            if (idx >= 0) {
                auto &p = tweetMap[t[2]][idx];
                minHeap.push({p.first, p.second, t[2], idx - 1});
            }
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        followMap[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        if (followMap[followerId].count(followeeId)) {
            followMap[followerId].erase(followeeId);
        }
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations