LeetCode 355 · Heap / Priority Queue

Design Twitter, explained with a picture

A news feed merged from the people you follow.

MediumHeap / Priority Queue
▶ Watch it step by step

The problem

Design a tiny Twitter: users can post, follow, unfollow, and get a news feed of the 10 most recent posts from themselves and the people they follow.

Input:  post 1 5, feed 1, follow 1 2, post 2 6, post 1 7, feed 1, unfollow 1 2, feed 1
Output: [5], [7, 6, 5], [7, 5]

Picture it

Picture each user with their own stack of posts, newest on top, each stamped with a time. To build a feed, look at the top post of your own pile and of each person you follow, and put those into a heap ordered by time. Repeatedly take the newest, and replace it with the next post from the same person’s pile.

How to recognise it

  • It is a design problem: a class with several operations (postTweet, follow, unfollow, getNewsFeed) and a hidden question about which one is hot.
  • The feed needs the 10 most recent items out of several sources (you and everyone you follow). Each source is already in time order.
  • "Merge several sorted lists and stop after a few items" is the signal for a heap (a tree stored in a list with O(log n) push and pop) or a partial sort.
  • Following and unfollowing are add and remove on a set of people, so a hash set per user gives O(1) for both.
  • The limits are up to 3 × 10^4 calls and at most 500 users, so a feed must not scan every post ever made.

Start with brute force

Keep one global list of all posts. For a feed, filter the posts written by you or someone you follow, sort them newest first, and take 10.

from collections import defaultdict

class TwitterBrute:
    def __init__(self):
        self.time = 0
        self.all_posts = []                 # (time, user, tweet)
        self.follows = defaultdict(set)

    def postTweet(self, user, tweet):
        self.time += 1
        self.all_posts.append((self.time, user, tweet))

    def getNewsFeed(self, user):
        people = self.follows[user] | {user}
        mine = [p for p in self.all_posts if p[1] in people]
        mine.sort(reverse=True)
        return [tweet for _, _, tweet in mine[:10]]

    def follow(self, a, b): self.follows[a].add(b)
    def unfollow(self, a, b): self.follows[a].discard(b)

Every feed touches all posts and sorts the relevant ones: O(P log P) for P posts. With 10^4 posts and 10^4 feed calls that is about 10^4 × 10^4 × 13, roughly 10^9 steps. Space is O(P).

From brute force to the idea

  1. Find the waste. Only 10 posts are shown, yet the brute force sorts everything.
  2. Split posts by author. Each user keeps their own list, already in time order because posts are appended with an increasing time stamp.
  3. Only the last 10 of each person can matter. The newest 10 overall can include at most 10 from any single author, so take posts[p][-10:].
  4. Select the 10 newest of the candidates. Build tuples (-time, tweet); the most negative is the newest. nsmallest(10, ...) uses a heap of size 10 internally and returns them newest first.
  5. Use sets for people. follows[user] | {user} adds yourself without storing a self-follow.

This is the key idea: per-user post lists, at most 10 candidates from each followed person, and a heap-based selection of the 10 newest.

The key idea

Merge k sorted lists with a heap, stopping after 10 posts. Follow sets are hash sets.

Python solution

class Twitter:
    def __init__(self):
        self.time = 0
        self.posts = defaultdict(list)      # user -> [(time, id)]
        self.follows = defaultdict(set)
    def postTweet(self, user, tweet):
        self.time += 1
        self.posts[user].append((self.time, tweet))
    def getNewsFeed(self, user):
        people = self.follows[user] | {user}
        heap = [(-t, id) for p in people for t, id in self.posts[p][-10:]]
        return [id for _, id in nsmallest(10, heap)]   # newest first
    def follow(self, a, b): self.follows[a].add(b)
    def unfollow(self, a, b): self.follows[a].discard(b)

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict from heapq import nsmallest

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forcepostTweet O(1); getNewsFeed O(P log P) for all P posts; follow and unfollow O(1)O(P)
Per-user lists and nsmallest (shown code)postTweet, follow, unfollow O(1) on average; getNewsFeed O(F · 10) to collect candidates, then about O(F · 10 · log 10) to select, F = people followedO(P) for all posts, O(F) extra per feed

Edge cases

  • New user with no posts or follows: getNewsFeed returns [].
  • Following yourself or unfollowing someone you never followed: harmless; discard does not raise. Your own posts stay in your feed even after unfollow(1, 1), because getNewsFeed adds you back.
  • Unfollow removes their posts at once: a feed is rebuilt each call, so nothing stale remains.
  • Fewer than 10 posts: you get all of them.
  • Example: post 1 → 5, feed gives [5]; follow 2, post 2 → 6, post 1 → 7, feed gives [7, 6, 5]; unfollow 2, feed gives [7, 5].
  • Imports: the snippet needs from collections import defaultdict and from heapq import nsmallest (LeetCode adds them for you).

Common mistakes

  • Taking the oldest 10 of each user (posts[p][:10]) instead of the newest. A user with 12 posts then shows tweets 10 down to 1.
  • Sorting by tweet id instead of by a time stamp. Ids need not grow with time.
  • Using a list for follows so the same follow is stored twice.
  • Forgetting to include the user's own posts.
Your turn: a feed of any length

Change getNewsFeed so the caller chooses the length: getNewsFeed(user, m) returns the m newest posts. Describe what changes, then write it if you like.

Compare with our answer

Both places that mention 10 must become m: the slice of each person's list and the selection. If you only change the selection, a user with more than 10 posts would still contribute at most 10 candidates and the feed would come up short.

from heapq import nsmallest

def getNewsFeed(self, user, m):
    people = self.follows[user] | {user}
    heap = [(-t, id) for p in people for t, id in self.posts[p][-m:]]
    return [id for _, id in nsmallest(m, heap)]    # newest first

Time is O(F · m) to collect and about O(F · m · log m) to select. For large m, merging the per-user lists lazily with a heap that holds one entry per person does better, because it never looks at more than m posts in total.

A strong answer mentions: changing both the per-person slice and the selection, why one of them alone is a bug, and the cost in terms of F and m.

Check what stuck

1. A forum shows each reader the 20 newest comments out of the threads they watch (each thread's comments are stored oldest to newest). Which approach fits best?

2. What does nsmallest(10, heap) cost in the shown getNewsFeed, if the candidate list has c entries?

3. A learner changes self.posts[p][-10:] to self.posts[p][:10]. Which test exposes the bug?

Score 60% or more and the lesson is marked complete.