355. Design Twitter (Medium)

Problem

Design a simplified Twitter where each user can post tweets, follow/unfollow users, and view the 10 most recent tweets in their news feed (including from themselves and followed users).

Required methods:

postTweet(userId, tweetId)
follow(followerId, followeeId)
unfollow(followerId, followeeId)
getNewsFeed(userId), return the 10 most-recent tweet IDs from the user and those they follow, most recent first.

LeetCode 355 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, merge all tweets and sort

Per-user tweet list; on getNewsFeed, concatenate relevant lists and sort by timestamp.

from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)   # user -> list[(time, tweetId)]
        self.follows = defaultdict(set)   # follower -> set(followees)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))  # L1: O(1) append
        self.time += 1

    def follow(self, followerId, followeeId):
        self.follows[followerId].add(followeeId)           # L2: O(1) set add

    def unfollow(self, followerId, followeeId):
        self.follows[followerId].discard(followeeId)       # L3: O(1) set discard

    def getNewsFeed(self, userId):
        users = self.follows[userId] | {userId}
        feed = []
        for u in users:
            feed.extend(self.tweets[u])                    # L4: O(T) collect all
        feed.sort(reverse=True)                            # L5: O(T log T) sort
        return [t for _, t in feed[:10]]

class Twitter {
    private time = 0;
    private tweets = new Map<number, Array<[number, number]>>();
    private follows = new Map<number, Set<number>>();

    private getTweets(u: number): Array<[number, number]> {
        if (!this.tweets.has(u)) this.tweets.set(u, []);
        return this.tweets.get(u)!;
    }
    private getFollows(u: number): Set<number> {
        if (!this.follows.has(u)) this.follows.set(u, new Set());
        return this.follows.get(u)!;
    }

    postTweet(userId: number, tweetId: number): void {
        this.getTweets(userId).push([this.time++, tweetId]);  // L1: O(1) append
    }
    follow(followerId: number, followeeId: number): void {
        this.getFollows(followerId).add(followeeId);           // L2: O(1) set add
    }
    unfollow(followerId: number, followeeId: number): void {
        this.getFollows(followerId).delete(followeeId);        // L3: O(1) set delete
    }
    getNewsFeed(userId: number): number[] {
        const users = new Set([userId, ...this.getFollows(userId)]);
        const feed: Array<[number, number]> = [];
        for (const u of users)
            feed.push(...this.getTweets(u));                   // L4: O(T) collect all
        feed.sort((a, b) => b[0] - a[0]);                     // L5: O(T log T) sort
        return feed.slice(0, 10).map(([, tid]) => tid);
    }
}

import "sort"

type Twitter struct {
    time    int
    tweets  map[int][][2]int
    follows map[int]map[int]bool
}

func Constructor() Twitter {
    return Twitter{tweets: make(map[int][][2]int), follows: make(map[int]map[int]bool)}
}

func (t *Twitter) PostTweet(userId, tweetId int) {
    t.tweets[userId] = append(t.tweets[userId], [2]int{t.time, tweetId}) // L1: O(1)
    t.time++
}

func (t *Twitter) Follow(followerId, followeeId int) {
    if t.follows[followerId] == nil { t.follows[followerId] = make(map[int]bool) }
    t.follows[followerId][followeeId] = true // L2: O(1)
}

func (t *Twitter) Unfollow(followerId, followeeId int) {
    delete(t.follows[followerId], followeeId) // L3: O(1)
}

func (t *Twitter) GetNewsFeed(userId int) []int {
    users := map[int]bool{userId: true}
    for u := range t.follows[userId] { users[u] = true }
    var feed [][2]int
    for u := range users { feed = append(feed, t.tweets[u]...) } // L4: O(T) collect all
    sort.Slice(feed, func(i, j int) bool { return feed[i][0] > feed[j][0] }) // L5: O(T log T)
    result := []int{}
    for i := 0; i < len(feed) && i < 10; i++ { result = append(result, feed[i][1]) }
    return result
}

private struct TweetRecord { let time: Int; let user: Int; let id: Int }
final class Twitter {
    private var clock = 0
    private var tweets: [TweetRecord] = []
    private var following: [Int: Set<Int>] = [:]
    init() {}
    func postTweet(_ userId: Int, _ tweetId: Int) { clock += 1; tweets.append(TweetRecord(time: clock, user: userId, id: tweetId)) }
    func getNewsFeed(_ userId: Int) -> [Int] { var users = following[userId, default: []]; users.insert(userId); return tweets.reversed().lazy.filter { users.contains($0.user) }.prefix(10).map(\.id) }
    func follow(_ followerId: Int, _ followeeId: Int) { following[followerId, default: []].insert(followeeId) }
    func unfollow(_ followerId: Int, _ followeeId: Int) { following[followerId]?.remove(followeeId) }
}

Where the time goes, line by line

Variables: k = number of users being followed, T = total tweets across those users.

Line	Per-call cost	Times executed	Contribution
L1-L3 (postTweet/follow/unfollow)	$O(1)$	1 per call	$O(1)$
L4 (collect all tweets)	$O(T)$	1 per getNewsFeed	$O(T)$
L5 (sort feed)	$O(T log T)$	1 per getNewsFeed	$O(T log T)$ ← dominates getNewsFeed

Complexity

getNewsFeed: $O(T log T)$ where T is total tweets across followed users (L5).
Others: $O(1)$ .

Approach 2: Per-user sorted list + k-way merge with a heap (optimal)

Store each user’s tweets as a list (append-only, so it’s naturally sorted by time). On getNewsFeed, k-way-merge the latest 10 from each followed user using a max-heap of size at most k + 1.

from collections import defaultdict
import heapq

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)   # user -> list[(time, tweetId)]
        self.follows = defaultdict(set)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))   # L1: O(1)
        self.time += 1

    def follow(self, followerId, followeeId):
        self.follows[followerId].add(followeeId)            # L2: O(1)

    def unfollow(self, followerId, followeeId):
        self.follows[followerId].discard(followeeId)        # L3: O(1)

    def getNewsFeed(self, userId):
        users = self.follows[userId] | {userId}
        heap = []
        # Seed the heap with the latest tweet from each user
        for u in users:                                     # L4: O(k) seed
            if self.tweets[u]:
                i = len(self.tweets[u]) - 1
                t, tid = self.tweets[u][i]
                heap.append((-t, u, i, tid))
        heapq.heapify(heap)                                 # L5: O(k) heapify

        feed = []
        while heap and len(feed) < 10:                     # L6: at most 10 iters
            neg_t, u, i, tid = heapq.heappop(heap)        # L7: O(log k) pop
            feed.append(tid)
            if i > 0:
                i -= 1
                t2, tid2 = self.tweets[u][i]
                heapq.heappush(heap, (-t2, u, i, tid2))   # L8: O(log k) push
        return feed

// Min-heap on negated timestamp acts as max-heap by time.
// Each entry: [negTime, userId, tweetIndex, tweetId]
type HeapEntry = [number, number, number, number];

class MinHeap {
    private data: HeapEntry[] = [];
    get size(): number { return this.data.length; }
    push(val: HeapEntry): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): HeapEntry {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] <= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l][0] < this.data[smallest][0]) smallest = l;
            if (r < n && this.data[r][0] < this.data[smallest][0]) smallest = r;
            if (smallest === i) break;
            [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]]; i = smallest;
        }
    }
}

class Twitter {
    private time = 0;
    private tweets = new Map<number, Array<[number, number]>>();
    private follows = new Map<number, Set<number>>();

    private getTweets(u: number): Array<[number, number]> {
        if (!this.tweets.has(u)) this.tweets.set(u, []);
        return this.tweets.get(u)!;
    }
    private getFollows(u: number): Set<number> {
        if (!this.follows.has(u)) this.follows.set(u, new Set());
        return this.follows.get(u)!;
    }

    postTweet(userId: number, tweetId: number): void {
        this.getTweets(userId).push([this.time++, tweetId]);  // L1: O(1)
    }
    follow(followerId: number, followeeId: number): void {
        this.getFollows(followerId).add(followeeId);           // L2: O(1)
    }
    unfollow(followerId: number, followeeId: number): void {
        this.getFollows(followerId).delete(followeeId);        // L3: O(1)
    }

    getNewsFeed(userId: number): number[] {
        const users = new Set([userId, ...this.getFollows(userId)]);
        const heap = new MinHeap();
        // Seed: latest tweet from each user              L4: O(k) seed
        for (const u of users) {
            const tw = this.getTweets(u);
            if (tw.length > 0) {
                const i = tw.length - 1;
                heap.push([-tw[i][0], u, i, tw[i][1]]);
            }
        }
        const feed: number[] = [];
        while (heap.size > 0 && feed.length < 10) {      // L6: at most 10 iters
            const [, u, i, tid] = heap.pop();             // L7: O(log k) pop
            feed.push(tid);
            if (i > 0) {
                const tw = this.getTweets(u);
                heap.push([-tw[i - 1][0], u, i - 1, tw[i - 1][1]]); // L8: O(log k) push
            }
        }
        return feed;
    }
}

package main

import (
    "container/heap"
    "fmt"
)

type heapEntry [4]int // [negTime, userId, tweetIndex, tweetId]
type FeedHeap []heapEntry
func (h FeedHeap) Len() int            { return len(h) }
func (h FeedHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h FeedHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *FeedHeap) Push(x any)         { *h = append(*h, x.(heapEntry)) }
func (h *FeedHeap) Pop() any { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type Twitter struct {
    time    int
    tweets  map[int][][2]int
    follows map[int]map[int]bool
}

func Constructor() Twitter {
    return Twitter{tweets: make(map[int][][2]int), follows: make(map[int]map[int]bool)}
}

func (t *Twitter) PostTweet(userId, tweetId int) {
    t.tweets[userId] = append(t.tweets[userId], [2]int{t.time, tweetId}) // L1: O(1)
    t.time++
}

func (t *Twitter) Follow(followerId, followeeId int) {
    if t.follows[followerId] == nil { t.follows[followerId] = make(map[int]bool) }
    t.follows[followerId][followeeId] = true // L2: O(1)
}

func (t *Twitter) Unfollow(followerId, followeeId int) {
    delete(t.follows[followerId], followeeId) // L3: O(1)
}

func (t *Twitter) GetNewsFeed(userId int) []int {
    users := map[int]bool{userId: true}
    for u := range t.follows[userId] { users[u] = true }
    h := &FeedHeap{}
    heap.Init(h)
    for u := range users { // L4: O(k) seed
        tw := t.tweets[u]
        if len(tw) > 0 { i := len(tw) - 1; heap.Push(h, heapEntry{-tw[i][0], u, i, tw[i][1]}) }
    }
    feed := []int{}
    for h.Len() > 0 && len(feed) < 10 { // L6: at most 10 iters
        e := heap.Pop(h).(heapEntry) // L7: O(log k) pop
        _, u, i, tid := e[0], e[1], e[2], e[3]
        feed = append(feed, tid)
        if i > 0 {
            tw := t.tweets[u]
            heap.Push(h, heapEntry{-tw[i-1][0], u, i - 1, tw[i-1][1]}) // L8: O(log k) push
        }
    }
    return feed
}

func sliceEqual(a, b []int) bool {
    if len(a) != len(b) { return false }
    for i := range a { if a[i] != b[i] { return false } }
    return true
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    t := Constructor()
    t.PostTweet(1, 5); assert(sliceEqual(t.GetNewsFeed(1), []int{5}))
    t.Follow(1, 2); t.PostTweet(2, 6); assert(sliceEqual(t.GetNewsFeed(1), []int{6, 5}))
    t.Unfollow(1, 2); assert(sliceEqual(t.GetNewsFeed(1), []int{5}))
    t2 := Constructor()
    for i := 0; i < 12; i++ { t2.PostTweet(1, i) }
    feed := t2.GetNewsFeed(1); assert(len(feed) == 10)
    assert(sliceEqual(feed, []int{11, 10, 9, 8, 7, 6, 5, 4, 3, 2}))
    fmt.Println("all tests pass")
}

func main() { runTests() }

private struct TweetRecord { let time: Int; let id: Int }
private struct FeedCursor { let user: Int; let index: Int; let tweet: TweetRecord }
final class Twitter {
    private var clock = 0
    private var tweets: [Int: [TweetRecord]] = [:]
    private var following: [Int: Set<Int>] = [:]
    init() {}
    func postTweet(_ userId: Int, _ tweetId: Int) { clock += 1; tweets[userId, default: []].append(TweetRecord(time: clock, id: tweetId)) }
    func getNewsFeed(_ userId: Int) -> [Int] {
        var users = following[userId, default: []]; users.insert(userId)
        var heap = BinaryHeap<FeedCursor> { $0.tweet.time > $1.tweet.time }
        for user in users { if let list = tweets[user], let tweet = list.last { heap.insert(FeedCursor(user: user, index: list.count - 1, tweet: tweet)) } }
        var feed: [Int] = []
        while feed.count < 10, let cursor = heap.removeRoot() { feed.append(cursor.tweet.id); let next = cursor.index - 1; if next >= 0, let tweet = tweets[cursor.user]?[next] { heap.insert(FeedCursor(user: cursor.user, index: next, tweet: tweet)) } }
        return feed
    }
    func follow(_ followerId: Int, _ followeeId: Int) { following[followerId, default: []].insert(followeeId) }
    func unfollow(_ followerId: Int, _ followeeId: Int) { following[followerId]?.remove(followeeId) }
}

Where the time goes, line by line

Variables: k = number of users being followed (heap size at most k + 1).

Line	Per-call cost	Times executed	Contribution
L1-L3 (postTweet/follow/unfollow)	$O(1)$	1 per call	$O(1)$
L4-L5 (seed + heapify)	$O(k)$	1 per getNewsFeed	$O(k)$
L6-L8 (drain 10 from heap)	$O(log k)$ each	10	$O(10 log k)$ = $O(log k)$ ← dominates getNewsFeed

The heap never exceeds k + 1 entries. Each of the 10 pops and up to 10 pushes costs $O(log k)$ . The seed phase at L4-L5 is $O(k)$ .

Complexity

getNewsFeed: $O(k + 10 log k)$ = $O(k)$ for seeding + $O(log k)$ for draining (L4-L8).
Others: $O(1)$ amortized.

Same pattern as problem 23 (Merge k Sorted Lists).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Cap per-user feed; global merge

If each user only ever needs the last 10 tweets, truncate the per-user list to length 10 (a rolling window). Then merge at most 10 · k tweets on getNewsFeed.

Complexity

getNewsFeed: $O(10 · k)$ .
Others: $O(1)$ .

Lower memory if you don’t need long-term history.

Swift

private struct TweetRecord { let time: Int; let id: Int }
private struct FeedCursor { let user: Int; let index: Int; let tweet: TweetRecord }
final class Twitter {
    private var clock = 0
    private var tweets: [Int: [TweetRecord]] = [:]
    private var following: [Int: Set<Int>] = [:]
    init() {}
    func postTweet(_ userId: Int, _ tweetId: Int) { clock += 1; tweets[userId, default: []].append(TweetRecord(time: clock, id: tweetId)); if tweets[userId]!.count > 10 { tweets[userId]!.removeFirst() } }
    func getNewsFeed(_ userId: Int) -> [Int] {
        var users = following[userId, default: []]; users.insert(userId)
        var heap = BinaryHeap<FeedCursor> { $0.tweet.time > $1.tweet.time }
        for user in users { if let list = tweets[user], let tweet = list.last { heap.insert(FeedCursor(user: user, index: list.count - 1, tweet: tweet)) } }
        var feed: [Int] = []
        while feed.count < 10, let cursor = heap.removeRoot() { feed.append(cursor.tweet.id); let next = cursor.index - 1; if next >= 0, let tweet = tweets[cursor.user]?[next] { heap.insert(FeedCursor(user: cursor.user, index: next, tweet: tweet)) } }
        return feed
    }
    func follow(_ followerId: Int, _ followeeId: Int) { following[followerId, default: []].insert(followeeId) }
    func unfollow(_ followerId: Int, _ followeeId: Int) { following[followerId]?.remove(followeeId) }
}

# Quick smoke tests, paste into a REPL or save as test_355.py and run.
# Uses the heap k-way merge approach (Approach 2).
import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)
        self.follows = defaultdict(set)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1

    def follow(self, followerId, followeeId):
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.follows[followerId].discard(followeeId)

    def getNewsFeed(self, userId):
        users = self.follows[userId] | {userId}
        heap = []
        for u in users:
            if self.tweets[u]:
                i = len(self.tweets[u]) - 1
                t, tid = self.tweets[u][i]
                heap.append((-t, u, i, tid))
        heapq.heapify(heap)
        feed = []
        while heap and len(feed) < 10:
            neg_t, u, i, tid = heapq.heappop(heap)
            feed.append(tid)
            if i > 0:
                i -= 1
                t2, tid2 = self.tweets[u][i]
                heapq.heappush(heap, (-t2, u, i, tid2))
        return feed

def _run_tests():
    t = Twitter()
    t.postTweet(1, 5)
    assert t.getNewsFeed(1) == [5]

    t.follow(1, 2)
    t.postTweet(2, 6)
    # user 1 follows user 2; most recent is tweet 6, then 5
    assert t.getNewsFeed(1) == [6, 5]

    t.unfollow(1, 2)
    # after unfollow, user 1 only sees their own tweet
    assert t.getNewsFeed(1) == [5]

    # User sees own tweets even without explicit self-follow
    t2 = Twitter()
    for i in range(12):
        t2.postTweet(1, i)
    feed = t2.getNewsFeed(1)
    assert len(feed) == 10
    assert feed == list(range(11, 1, -1))  # most recent 10: 11,10,...,2

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses the heap k-way merge approach (Approach 2).
// See 355-design-twitter-approach2.ts for the full implementation.
const t = new Twitter();
t.postTweet(1, 5);
console.assert(JSON.stringify(t.getNewsFeed(1)) === JSON.stringify([5]));

t.follow(1, 2);
t.postTweet(2, 6);
console.assert(JSON.stringify(t.getNewsFeed(1)) === JSON.stringify([6, 5]));

t.unfollow(1, 2);
console.assert(JSON.stringify(t.getNewsFeed(1)) === JSON.stringify([5]));

const t2 = new Twitter();
for (let i = 0; i < 12; i++) t2.postTweet(1, i);
const feed = t2.getNewsFeed(1);
console.assert(feed.length === 10);
console.assert(JSON.stringify(feed) === JSON.stringify([11, 10, 9, 8, 7, 6, 5, 4, 3, 2]));

console.log("all tests pass");

Summary

Approach	getNewsFeed	postTweet	Notes
Collect all + sort	$O(T log T)$	$O(1)$	Simplest
Heap k-way merge	$O(10 log k)$	$O(1)$	Canonical answer
Rolling per-user window	$O(10 · k)$	$O(1)$	If history truncation is OK

The k-way merge pattern is the right generalization: it’s the same code you’d use to implement Kafka partition consumers, merged log readers, or any “top-N across ordered streams” system.

Heaps / Priority Queues, k-way merge on per-user feeds
Hash Tables, user → tweets, follower → followees
Linked Lists, could replace the per-user list if you need $O(1)$ prepend

Heap and Priority Queue, priority-frontier tactics for repeatedly extracting the smallest, largest, or most urgent item.
K-way Merge, multi-stream ordering tactics for combining several sorted sources through one priority queue.
Simulation, state-machine tactics for faithfully executing rules while keeping state small and explicit.

355. Design Twitter (Medium)

Problem

Try it yourself

Approach 1: Brute force, merge all tweets and sort

Approach 2: Per-user sorted list + k-way merge with a heap (optimal)

Approach 3: Cap per-user feed; global merge

Test cases

Summary

Related data structures

Related concepts