Problem editorial

Design Twitter

MediumHeap (Priority Queue) PatternsDesignHeap (Priority Queue)Hash Table

Editorial

Core insight

Design Twitter · Heap (Priority Queue) Patterns

Core Insight for Design Twitter

The brute force method sorts all eligible tweets, even though the feed needs only the 10 newest. The key improvement is to merge the tweet lists incrementally.

For every eligible source:

The source's tweets are stored in posting order.
Its last tweet is currently the newest tweet available from that source.
The newest tweet among all sources must be the maximum timestamp among those source-ending tweets.

A max-heap can identify that tweet efficiently. Once it is removed, only one new candidate is revealed: the immediately older tweet from the same source. No other source changes state.

The central K-way Merge invariant is:

At every iteration, the heap contains the newest not-yet-selected tweet from each source that still has remaining tweets.

Because each source's list is chronological, the next tweet from a source can only be its previous list element. Therefore, selecting the maximum heap entry and inserting that source's previous tweet preserves the invariant.

The algorithm does not need to merge complete lists. It stops after extracting 10 tweets or when all eligible tweets have been exhausted.

Visual Description: Conceptually, each eligible user contributes a vertical sequence of tweets indexed from newest at the bottom to oldest at the top. The heap initially contains the bottom element of every nonempty sequence. Each extraction removes one visible element and moves that sequence's pointer one position toward older tweets. The heap boundary therefore moves independently through each source while always exposing the globally newest available tweet.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 355: Design Twitter Solution & Explanation

Problem Overview

TL;DR: Store each user's tweets in chronological order, then use a max-heap to perform a K-way merge of the current user's and followed users' tweet streams, extracting only the 10 newest tweets.

In LeetCode 355: Design Twitter, the Twitter class must support posting tweets, following and unfollowing users, and retrieving a user's news feed. A news feed contains at most the 10 most recent tweets from the user and all currently followed users.

Each user's tweets form a chronological sequence. The main challenge is combining several such sequences efficiently while preserving global reverse-chronological order. This makes the LeetCode 355 Solution a direct application of the K-way Merge subpattern.

Because the number of operations can reach 100,000, an approach that repeatedly scans and sorts every eligible tweet is too expensive. The optimal solution for interviews maintains chronological tweet streams and merges only the portions needed for the feed.

Brute Force Approach for Design Twitter

A straightforward approach is:

Store every tweet with its posting timestamp.
For getNewsFeed(userId):
- Collect tweets posted by userId.
- Collect tweets posted by every user followed by userId.
- Sort all collected tweets by timestamp in descending order.
- Return the first 10 tweet IDs.

Naive Pseudocode

text

postTweet(userId, tweetId):
    append (timestamp, tweetId) to the user's tweet list
    increment timestamp

follow(followerId, followeeId):
    add followeeId to followerId's follow set

unfollow(followerId, followeeId):
    remove followeeId from followerId's follow set if present

getNewsFeed(userId):
    candidates = empty list

    add all tweets from userId to candidates

    for each followed user:
        add all of that user's tweets to candidates

    sort candidates by timestamp descending

    return the first 10 tweet IDs

Let:

F be the number of eligible sources: the user plus followed users.
T be the total number of tweets posted by those sources.

For one feed request, collecting tweets takes O(T) time and sorting takes O(T log T) time. Therefore:

text

getNewsFeed: O(T log T)

This can fail because a user may follow many accounts, and those accounts may collectively have a very large number of tweets. Even though the result contains only 10 tweets, the brute force method processes and sorts every eligible tweet. Across up to 100,000 operations, this can lead to Time Limit Exceeded.

Algorithm Strategy: Heap (Priority Queue) Patterns

Maintain a monotonically increasing global timestamp.
Store each user's tweets in a list in posting order.
Store follow relationships in a set for each follower.
For getNewsFeed(userId):
- Build the set of eligible sources by combining userId with all users followed by userId.
- Insert the newest tweet from every nonempty source into a max-heap.
- Repeatedly remove the newest heap entry.
- Add its tweet ID to the result.
- If that source has an older tweet, insert that tweet into the heap.
- Stop after 10 results or when the heap becomes empty.
Use set insertion and removal for idempotent follow and safe unfollow operations.

The heap boundary enforces that only the newest unselected tweet from each source is active. This is the constraint that makes the merge efficient.

Execution Flow

Posting a tweet
- Increment the global timestamp.
- Append (timestamp, tweetId) to the posting user's tweet list.
- Since tweets are appended, each user's list remains chronologically sorted.
Following
- Insert the followee into the follower's set.
- Repeating the same follow has no additional effect.
Unfollowing
- Remove the followee from the follower's set if the relationship exists.
- Removing a nonexistent relationship is a no-op.
Starting a feed request
- Include the requesting user as a source.
- Include every currently followed user as a source.
- For each source with tweets, point to its last tweet and push that entry into the max-heap.
Selecting feed entries
- The heap top is the newest currently available tweet across all sources.
- Remove it and append its ID to the feed.
- Move that source's index one position backward.
- If an older tweet exists in that source, push it into the heap.
Stopping
- Stop after 10 tweets because no feed can contain more than 10 results.
- If the heap becomes empty first, return all available eligible tweets.

Proof of Correctness

We prove that getNewsFeed returns the eligible tweets in descending posting order.

Heap Invariant

Before every extraction, the heap contains the newest not-yet-selected tweet from every eligible source that still has unselected tweets.

Initialization: For each nonempty source, the algorithm inserts its newest tweet. Therefore, the invariant holds before the first extraction.
Maintenance: Suppose the heap invariant holds before an extraction. The heap top is the newest available tweet among all sources, so it is safe to append it to the feed. After removing it, only that same source can expose a new candidate: its immediately older tweet. The algorithm inserts that tweet if it exists. All other sources remain unchanged. Thus, the invariant holds for the next iteration.

Correct Ordering

Because the heap contains the newest remaining tweet from every source, its maximum entry is the newest unselected eligible tweet overall. Each extracted tweet is therefore no older than the previous extracted tweet.

Completeness of the First 10 Results

Every source advances one position only after its current newest remaining tweet is selected. Consequently, no tweet can be skipped before a newer tweet from the same source is selected. Repeating this process produces the globally newest eligible tweets in order. Stopping after 10 extractions returns exactly the required feed.

Therefore, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

Each problem has multiple ordered sources and uses a heap to track the next candidate from every source. The heap repeatedly selects the globally smallest or largest candidate, then advances only the source that produced it. In Design Twitter, the sources are users' tweet lists, and the merge is performed in descending timestamp order.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 355

cpp

1class Twitter {
2    struct Tweet {
3        long long time;
4        int id;
5    };
6
7    struct HeapEntry {
8        long long time;
9        int id;
10        int user;
11        int index;
12    };
13
14    struct Compare {
15        bool operator()(const HeapEntry& a, const HeapEntry& b) const {
16            return a.time < b.time;
17        }
18    };
19
20    long long currentTime = 0;
21    unordered_map<int, vector<Tweet>> tweets;
22    unordered_map<int, unordered_set<int>> following;
23
24public:
25    Twitter() {
26    }
27
28    void postTweet(int userId, int tweetId) {
29        tweets[userId].push_back({++currentTime, tweetId});
30    }
31
32    vector<int> getNewsFeed(int userId) {
33        priority_queue<HeapEntry, vector<HeapEntry>, Compare> heap;
34
35        auto addLatestTweet = [&](int user) {
36            auto it = tweets.find(user);
37            if (it == tweets.end() || it->second.empty()) {
38                return;
39            }
40
41            int index = static_cast<int>(it->second.size()) - 1;
42            const Tweet& tweet = it->second[index];
43            heap.push({tweet.time, tweet.id, user, index});
44        };
45
46        addLatestTweet(userId);
47
48        auto followIt = following.find(userId);
49        if (followIt != following.end()) {
50            for (int followeeId : followIt->second) {
51                addLatestTweet(followeeId);
52            }
53        }
54
55        vector<int> feed;
56        while (!heap.empty() && feed.size() < 10) {
57            HeapEntry current = heap.top();
58            heap.pop();
59            feed.push_back(current.id);
60
61            if (current.index > 0) {
62                const Tweet& previous = tweets[current.user][current.index - 1];
63                heap.push({previous.time, previous.id, current.user, current.index - 1});
64            }
65        }
66
67        return feed;
68    }
69
70    void follow(int followerId, int followeeId) {
71        following[followerId].insert(followeeId);
72    }
73
74    void unfollow(int followerId, int followeeId) {
75        auto it = following.find(followerId);
76        if (it != following.end()) {
77            it->second.erase(followeeId);
78        }
79    }
80};

Java Solution for LeetCode 355

java

1class Twitter {
2    private final java.util.Map<Integer, java.util.List<Tweet>> tweets;
3    private final java.util.Map<Integer, java.util.Set<Integer>> following;
4    private int time;
5
6    private static class Tweet {
7        int time;
8        int id;
9
10        Tweet(int time, int id) {
11            this.time = time;
12            this.id = id;
13        }
14    }
15
16    private static class Entry {
17        int time;
18        int source;
19        int index;
20
21        Entry(int time, int source, int index) {
22            this.time = time;
23            this.source = source;
24            this.index = index;
25        }
26    }
27
28    public Twitter() {
29        tweets = new java.util.HashMap<>();
30        following = new java.util.HashMap<>();
31        time = 0;
32    }
33
34    public void postTweet(int userId, int tweetId) {
35        time += 1;
36        tweets.computeIfAbsent(userId, k -> new java.util.ArrayList<>())
37              .add(new Tweet(time, tweetId));
38    }
39
40    public int[] getNewsFeed(int userId) {
41        java.util.Set<Integer> sources = new java.util.HashSet<>();
42        java.util.Set<Integer> followed = following.get(userId);
43        if (followed != null) {
44            sources.addAll(followed);
45        }
46        sources.add(userId);
47
48        java.util.PriorityQueue<Entry> heap = new java.util.PriorityQueue<>(
49            (a, b) -> {
50                int comparison = Integer.compare(b.time, a.time);
51                if (comparison != 0) {
52                    return comparison;
53                }
54                comparison = Integer.compare(a.source, b.source);
55                if (comparison != 0) {
56                    return comparison;
57                }
58                return Integer.compare(a.index, b.index);
59            }
60        );
61
62        for (int source : sources) {
63            java.util.List<Tweet> sourceTweets = tweets.get(source);
64            if (sourceTweets != null && !sourceTweets.isEmpty()) {
65                int index = sourceTweets.size() - 1;
66                heap.add(new Entry(sourceTweets.get(index).time, source, index));
67            }
68        }
69
70        java.util.List<Integer> feed = new java.util.ArrayList<>();
71        while (!heap.isEmpty() && feed.size() < 10) {
72            Entry entry = heap.poll();
73            java.util.List<Tweet> sourceTweets = tweets.get(entry.source);
74            feed.add(sourceTweets.get(entry.index).id);
75
76            if (entry.index > 0) {
77                int previous = entry.index - 1;
78                heap.add(new Entry(sourceTweets.get(previous).time, entry.source, previous));
79            }
80        }
81
82        int[] result = new int[feed.size()];
83        for (int i = 0; i < feed.size(); i++) {
84            result[i] = feed.get(i);
85        }
86        return result;
87    }
88
89    public void follow(int followerId, int followeeId) {
90        following.computeIfAbsent(followerId, k -> new java.util.HashSet<>())
91                 .add(followeeId);
92    }
93
94    public void unfollow(int followerId, int followeeId) {
95        java.util.Set<Integer> followed = following.get(followerId);
96        if (followed != null) {
97            followed.remove(followeeId);
98        }
99    }
100}

Python Solution for LeetCode 355

python

1from typing import List, Optional
2import heapq
3
4
5class Twitter:
6    def __init__(self):
7        self._tweets = {}
8        self._following = {}
9        self._time = 0
10
11    def postTweet(self, userId: int, tweetId: int) -> None:
12        self._time += 1
13        self._tweets.setdefault(userId, []).append((self._time, tweetId))
14
15    def getNewsFeed(self, userId: int) -> List[int]:
16        sources = set(self._following.get(userId, ()))
17        sources.add(userId)
18
19        heap = []
20        for source in sources:
21            tweets = self._tweets.get(source)
22            if tweets:
23                index = len(tweets) - 1
24                heap.append((-tweets[index][0], source, index))
25
26        heapq.heapify(heap)
27
28        feed = []
29        while heap and len(feed) < 10:
30            _, source, index = heapq.heappop(heap)
31            tweets = self._tweets[source]
32            feed.append(tweets[index][1])
33
34            if index > 0:
35                previous = index - 1
36                heapq.heappush(
37                    heap,
38                    (-tweets[previous][0], source, previous),
39                )
40
41        return feed
42
43    def follow(self, followerId: int, followeeId: int) -> None:
44        self._following.setdefault(followerId, set()).add(followeeId)
45
46    def unfollow(self, followerId: int, followeeId: int) -> None:
47        following = self._following.get(followerId)
48        if following is not None:
49            following.discard(followeeId)

AI Coach Insight

For Design Twitter, focus on explaining why the structure works, not just naming Heap (Priority Queue) Patterns.

Complexity Analysis

Let:

F be the number of eligible sources, including the user.
K = min(10, T) be the number of tweets returned.
T be the total number of eligible tweets.

Time Complexity

Building the initial heap: O(F log F) using individual insertions.
Extracting up to K tweets: O(K log F).
Each extraction adds at most one replacement entry.

Overall:

text

O(F log F + K log F)

Since K <= 10, this is effectively:

text

O(F log F)

The verified implementations use heap construction in language-specific ways, but the same asymptotic bound applies.

Space Complexity

Stored tweets and follow relationships: proportional to the total data maintained by the service.
Temporary heap: O(F).
Feed result: O(10), which is constant.

For the additional space used by one getNewsFeed call:

text

O(F)

Related Patterns

Pattern: Heap (Priority Queue) Patterns
Subpattern: K-way Merge

This problem fits K-way Merge because every eligible user contributes one independently sorted tweet sequence. Each sequence is ordered from oldest to newest, so its latest tweet is at the end. The feed is produced by merging these sequences in descending timestamp order.

The heap stores at most one currently visible tweet from each source. After removing the newest tweet from one source, the next older tweet from that same source becomes eligible and is inserted into the heap.

Common Mistakes & FAQ

Q: Why does the naive solution TLE?

The naive solution collects every eligible tweet and sorts the complete collection for every feed request. A user may follow many accounts, and each account may have posted many tweets. The feed needs only 10 results, but the algorithm still processes and sorts all T tweets, resulting in O(T log T) work per request. The heap-based K-way Merge solution processes only the current head of each source and up to 10 selected tweets.

Q: Why must the heap initially contain only the newest tweet from each source?

The heap represents the current merge frontier. Inserting every tweet from every source destroys the main efficiency benefit and increases heap construction to the total number of eligible tweets. More importantly, K-way Merge works by exposing one next candidate per sorted sequence. The older tweets from a source become candidates only after its newer tweet has been removed.

Q: Why is the previous index inserted after removing a tweet?

Each user's tweet list is stored from oldest to newest. Therefore, if the current index is i, the next older tweet is at i - 1. Inserting any other index could skip tweets or produce an incorrect order. The consequence is a correctness failure because the feed may omit a newer eligible tweet from that source.

Q: Why must the requesting user be added as a source?

A user's own tweets always belong in their feed, regardless of follow relationships. If the requesting user is not inserted into the source set, their tweets are omitted entirely. This produces incomplete feeds even when the heap merge itself is implemented correctly.

Q: Why should follow and unfollow use sets?

A follow relationship is binary: following the same user twice should not create duplicate sources. A set makes repeated follow calls idempotent. It also makes unfollow safe when the relationship does not exist. Using a list can create duplicate heap streams and duplicate tweet IDs in the feed, while incorrect unfollow handling can remove unrelated relationships or raise errors.

Practise Design Twitter and the problems around it

Design Twitter is a Heap (Priority Queue) Patterns problem, in the K-way Merge subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Design Twitter · Heap (Priority Queue) Patterns

Core Insight for Design Twitter

The brute force method sorts all eligible tweets, even though the feed needs only the 10 newest. The key improvement is to merge the tweet lists incrementally.

For every eligible source:

The source's tweets are stored in posting order.
Its last tweet is currently the newest tweet available from that source.
The newest tweet among all sources must be the maximum timestamp among those source-ending tweets.

A max-heap can identify that tweet efficiently. Once it is removed, only one new candidate is revealed: the immediately older tweet from the same source. No other source changes state.

The central K-way Merge invariant is:

At every iteration, the heap contains the newest not-yet-selected tweet from each source that still has remaining tweets.

The algorithm does not need to merge complete lists. It stops after extracting 10 tweets or when all eligible tweets have been exhausted.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 355: Design Twitter Solution & Explanation

Problem Overview

TL;DR: Store each user's tweets in chronological order, then use a max-heap to perform a K-way merge of the current user's and followed users' tweet streams, extracting only the 10 newest tweets.

Brute Force Approach for Design Twitter

A straightforward approach is:

Store every tweet with its posting timestamp.
For getNewsFeed(userId):
- Collect tweets posted by userId.
- Collect tweets posted by every user followed by userId.
- Sort all collected tweets by timestamp in descending order.
- Return the first 10 tweet IDs.

Naive Pseudocode

text

postTweet(userId, tweetId):
    append (timestamp, tweetId) to the user's tweet list
    increment timestamp

follow(followerId, followeeId):
    add followeeId to followerId's follow set

unfollow(followerId, followeeId):
    remove followeeId from followerId's follow set if present

getNewsFeed(userId):
    candidates = empty list

    add all tweets from userId to candidates

    for each followed user:
        add all of that user's tweets to candidates

    sort candidates by timestamp descending

    return the first 10 tweet IDs

Let:

F be the number of eligible sources: the user plus followed users.
T be the total number of tweets posted by those sources.

For one feed request, collecting tweets takes O(T) time and sorting takes O(T log T) time. Therefore:

text

getNewsFeed: O(T log T)

Algorithm Strategy: Heap (Priority Queue) Patterns

Maintain a monotonically increasing global timestamp.
Store each user's tweets in a list in posting order.
Store follow relationships in a set for each follower.
For getNewsFeed(userId):
- Build the set of eligible sources by combining userId with all users followed by userId.
- Insert the newest tweet from every nonempty source into a max-heap.
- Repeatedly remove the newest heap entry.
- Add its tweet ID to the result.
- If that source has an older tweet, insert that tweet into the heap.
- Stop after 10 results or when the heap becomes empty.
Use set insertion and removal for idempotent follow and safe unfollow operations.

The heap boundary enforces that only the newest unselected tweet from each source is active. This is the constraint that makes the merge efficient.

Execution Flow

Posting a tweet
- Increment the global timestamp.
- Append (timestamp, tweetId) to the posting user's tweet list.
- Since tweets are appended, each user's list remains chronologically sorted.
Following
- Insert the followee into the follower's set.
- Repeating the same follow has no additional effect.
Unfollowing
- Remove the followee from the follower's set if the relationship exists.
- Removing a nonexistent relationship is a no-op.
Starting a feed request
- Include the requesting user as a source.
- Include every currently followed user as a source.
- For each source with tweets, point to its last tweet and push that entry into the max-heap.
Selecting feed entries
- The heap top is the newest currently available tweet across all sources.
- Remove it and append its ID to the feed.
- Move that source's index one position backward.
- If an older tweet exists in that source, push it into the heap.
Stopping
- Stop after 10 tweets because no feed can contain more than 10 results.
- If the heap becomes empty first, return all available eligible tweets.

Proof of Correctness

We prove that getNewsFeed returns the eligible tweets in descending posting order.

Heap Invariant

Before every extraction, the heap contains the newest not-yet-selected tweet from every eligible source that still has unselected tweets.

Initialization: For each nonempty source, the algorithm inserts its newest tweet. Therefore, the invariant holds before the first extraction.
Maintenance: Suppose the heap invariant holds before an extraction. The heap top is the newest available tweet among all sources, so it is safe to append it to the feed. After removing it, only that same source can expose a new candidate: its immediately older tweet. The algorithm inserts that tweet if it exists. All other sources remain unchanged. Thus, the invariant holds for the next iteration.

Correct Ordering

Completeness of the First 10 Results

Therefore, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 355

cpp

1class Twitter {
2    struct Tweet {
3        long long time;
4        int id;
5    };
6
7    struct HeapEntry {
8        long long time;
9        int id;
10        int user;
11        int index;
12    };
13
14    struct Compare {
15        bool operator()(const HeapEntry& a, const HeapEntry& b) const {
16            return a.time < b.time;
17        }
18    };
19
20    long long currentTime = 0;
21    unordered_map<int, vector<Tweet>> tweets;
22    unordered_map<int, unordered_set<int>> following;
23
24public:
25    Twitter() {
26    }
27
28    void postTweet(int userId, int tweetId) {
29        tweets[userId].push_back({++currentTime, tweetId});
30    }
31
32    vector<int> getNewsFeed(int userId) {
33        priority_queue<HeapEntry, vector<HeapEntry>, Compare> heap;
34
35        auto addLatestTweet = [&](int user) {
36            auto it = tweets.find(user);
37            if (it == tweets.end() || it->second.empty()) {
38                return;
39            }
40
41            int index = static_cast<int>(it->second.size()) - 1;
42            const Tweet& tweet = it->second[index];
43            heap.push({tweet.time, tweet.id, user, index});
44        };
45
46        addLatestTweet(userId);
47
48        auto followIt = following.find(userId);
49        if (followIt != following.end()) {
50            for (int followeeId : followIt->second) {
51                addLatestTweet(followeeId);
52            }
53        }
54
55        vector<int> feed;
56        while (!heap.empty() && feed.size() < 10) {
57            HeapEntry current = heap.top();
58            heap.pop();
59            feed.push_back(current.id);
60
61            if (current.index > 0) {
62                const Tweet& previous = tweets[current.user][current.index - 1];
63                heap.push({previous.time, previous.id, current.user, current.index - 1});
64            }
65        }
66
67        return feed;
68    }
69
70    void follow(int followerId, int followeeId) {
71        following[followerId].insert(followeeId);
72    }
73
74    void unfollow(int followerId, int followeeId) {
75        auto it = following.find(followerId);
76        if (it != following.end()) {
77            it->second.erase(followeeId);
78        }
79    }
80};

Java Solution for LeetCode 355

java

1class Twitter {
2    private final java.util.Map<Integer, java.util.List<Tweet>> tweets;
3    private final java.util.Map<Integer, java.util.Set<Integer>> following;
4    private int time;
5
6    private static class Tweet {
7        int time;
8        int id;
9
10        Tweet(int time, int id) {
11            this.time = time;
12            this.id = id;
13        }
14    }
15
16    private static class Entry {
17        int time;
18        int source;
19        int index;
20
21        Entry(int time, int source, int index) {
22            this.time = time;
23            this.source = source;
24            this.index = index;
25        }
26    }
27
28    public Twitter() {
29        tweets = new java.util.HashMap<>();
30        following = new java.util.HashMap<>();
31        time = 0;
32    }
33
34    public void postTweet(int userId, int tweetId) {
35        time += 1;
36        tweets.computeIfAbsent(userId, k -> new java.util.ArrayList<>())
37              .add(new Tweet(time, tweetId));
38    }
39
40    public int[] getNewsFeed(int userId) {
41        java.util.Set<Integer> sources = new java.util.HashSet<>();
42        java.util.Set<Integer> followed = following.get(userId);
43        if (followed != null) {
44            sources.addAll(followed);
45        }
46        sources.add(userId);
47
48        java.util.PriorityQueue<Entry> heap = new java.util.PriorityQueue<>(
49            (a, b) -> {
50                int comparison = Integer.compare(b.time, a.time);
51                if (comparison != 0) {
52                    return comparison;
53                }
54                comparison = Integer.compare(a.source, b.source);
55                if (comparison != 0) {
56                    return comparison;
57                }
58                return Integer.compare(a.index, b.index);
59            }
60        );
61
62        for (int source : sources) {
63            java.util.List<Tweet> sourceTweets = tweets.get(source);
64            if (sourceTweets != null && !sourceTweets.isEmpty()) {
65                int index = sourceTweets.size() - 1;
66                heap.add(new Entry(sourceTweets.get(index).time, source, index));
67            }
68        }
69
70        java.util.List<Integer> feed = new java.util.ArrayList<>();
71        while (!heap.isEmpty() && feed.size() < 10) {
72            Entry entry = heap.poll();
73            java.util.List<Tweet> sourceTweets = tweets.get(entry.source);
74            feed.add(sourceTweets.get(entry.index).id);
75
76            if (entry.index > 0) {
77                int previous = entry.index - 1;
78                heap.add(new Entry(sourceTweets.get(previous).time, entry.source, previous));
79            }
80        }
81
82        int[] result = new int[feed.size()];
83        for (int i = 0; i < feed.size(); i++) {
84            result[i] = feed.get(i);
85        }
86        return result;
87    }
88
89    public void follow(int followerId, int followeeId) {
90        following.computeIfAbsent(followerId, k -> new java.util.HashSet<>())
91                 .add(followeeId);
92    }
93
94    public void unfollow(int followerId, int followeeId) {
95        java.util.Set<Integer> followed = following.get(followerId);
96        if (followed != null) {
97            followed.remove(followeeId);
98        }
99    }
100}

Python Solution for LeetCode 355

python

1from typing import List, Optional
2import heapq
3
4
5class Twitter:
6    def __init__(self):
7        self._tweets = {}
8        self._following = {}
9        self._time = 0
10
11    def postTweet(self, userId: int, tweetId: int) -> None:
12        self._time += 1
13        self._tweets.setdefault(userId, []).append((self._time, tweetId))
14
15    def getNewsFeed(self, userId: int) -> List[int]:
16        sources = set(self._following.get(userId, ()))
17        sources.add(userId)
18
19        heap = []
20        for source in sources:
21            tweets = self._tweets.get(source)
22            if tweets:
23                index = len(tweets) - 1
24                heap.append((-tweets[index][0], source, index))
25
26        heapq.heapify(heap)
27
28        feed = []
29        while heap and len(feed) < 10:
30            _, source, index = heapq.heappop(heap)
31            tweets = self._tweets[source]
32            feed.append(tweets[index][1])
33
34            if index > 0:
35                previous = index - 1
36                heapq.heappush(
37                    heap,
38                    (-tweets[previous][0], source, previous),
39                )
40
41        return feed
42
43    def follow(self, followerId: int, followeeId: int) -> None:
44        self._following.setdefault(followerId, set()).add(followeeId)
45
46    def unfollow(self, followerId: int, followeeId: int) -> None:
47        following = self._following.get(followerId)
48        if following is not None:
49            following.discard(followeeId)

Core Insight for Design Twitter

LeetCode 355: Design Twitter Solution & Explanation

Problem Overview

Brute Force Approach for Design Twitter

Naive Pseudocode

Algorithm Strategy: Heap (Priority Queue) Patterns

Execution Flow

Proof of Correctness

Heap Invariant

Correct Ordering

Completeness of the First 10 Results

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 355

Java Solution for LeetCode 355

Python Solution for LeetCode 355

Practise Design Twitter and the problems around it

Related problems

Core Insight for Design Twitter

LeetCode 355: Design Twitter Solution & Explanation

Problem Overview

Brute Force Approach for Design Twitter

Naive Pseudocode

Algorithm Strategy: Heap (Priority Queue) Patterns

Execution Flow

Proof of Correctness

Heap Invariant

Correct Ordering

Completeness of the First 10 Results

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 355

Java Solution for LeetCode 355

Python Solution for LeetCode 355

Practise Design Twitter and the problems around it

Related problems