LeetCode 355: Design Twitter Solution in Python – A Step-by-Step Guide

What Is LeetCode 355: Design Twitter?

In LeetCode 355: Design Twitter, you need to design a Twitter-like system with four key methods:

• postTweet(userId, tweetId): User posts a tweet.
• getNewsFeed(userId): Retrieve the 10 most recent tweets from the user and their followees.
• follow(followerId, followeeId): Follower follows followee.
• unfollow(followerId, followeeId): Follower unfollows followee.

For example, posting tweets and following users should update the feed to show the latest from all relevant sources, efficiently handling up to 10 tweets. The system must track tweets and relationships dynamically.

Problem Statement

• Input: Method calls with userId, tweetId, followerId, followeeId (integers).
• Output: Varies by method (None or list of tweet IDs).
• Rules:
• Tweets are ordered by recency (most recent first).
• Feed includes user’s own tweets and followees’ tweets, up to 10.
• Handle follow/unfollow dynamically.

Constraints

• 1 <= userId, followeeId, followerId <= 500
• 0 <= tweetId <= 10⁴
• All tweet IDs are unique.
• Up to 3000 method calls.
• getNewsFeed returns at most 10 tweets.

Examples

• Operations:
• postTweet(1, 5) → User 1 posts tweet 5.
• getNewsFeed(1) → [5].
• follow(1, 2) → User 1 follows user 2.
• postTweet(2, 6) → User 2 posts tweet 6.
• getNewsFeed(1) → [6, 5] (recent from 1 and 2).
• unfollow(1, 2) → User 1 unfollows user 2.
• getNewsFeed(1) → [5].
• Why: Tracks tweets and follows, retrieves recent 10.

Understanding the Problem: Designing Twitter

To solve LeetCode 355: Design Twitter in Python, we need a system to:

• Store tweets with timestamps.
• Track follow relationships.
• Retrieve the 10 most recent tweets efficiently.

A naive approach—storing all tweets in a list and filtering for each feed—would be slow for large numbers of tweets and users. Instead, we’ll use data structures to optimize:

• Best Solution (Hash Map with Heap): O(1) post, O(f log f) feed (f = followees), O(1) follow/unfollow—fast feed retrieval.
• Alternative Solution (List-Based): O(1) post/follow/unfollow, O(n log n) feed (n = total tweets)—simpler but slower feed.

Let’s dive into the Best Solution—hash map with heap—and break it down step-by-step.

Best Solution: Hash Map with Heap

Why This Is the Best Solution

The hash map with heap approach is the top choice because it balances efficiency across all operations—O(1) for posting and follow/unfollow, O(f log f) for feed retrieval (f = number of followees)—using O(n) space for tweets and O(u²) for follows (u = users). It stores tweets per user in a hash map and uses a heap to merge the latest tweets from multiple sources efficiently. It’s like keeping a personal tweet log for each user, then smartly picking the top 10 from a crowd—optimized and scalable!

How It Works

Here’s the strategy:

• Data Structures:
• tweets: Hash map mapping user ID to list of (timestamp, tweetId) pairs.
• follows: Hash map mapping follower ID to set of followee IDs.
• timestamp: Global counter for tweet recency.
• Methods:
• postTweet: Add tweet to user’s list with timestamp.
• follow: Add followee to follower’s set.
• unfollow: Remove followee from follower’s set.
• getNewsFeed: Use heap to merge recent tweets from user and followees, return top 10.

Step-by-Step Example

Example Operations:

• Initialize: tweets = {}, follows = {}, timestamp = 0.
• postTweet(1, 5):
• tweets[1] = [(0, 5)], timestamp = 1.
• getNewsFeed(1):
• Heap: [(0, 5)], pop 5 → [5].
• follow(1, 2):
• follows[1] = {2}.
• postTweet(2, 6):
• tweets[2] = [(1, 6)], timestamp = 2.
• getNewsFeed(1):
• User 1: [(0, 5)], User 2: [(1, 6)].
• Heap: [(-1, 6), (-0, 5)], pop 6, 5 → [6, 5].
• unfollow(1, 2):
• follows[1] = {}.
• getNewsFeed(1):
• Only User 1: [(0, 5)] → [5].
• Result: Follows example flow.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import defaultdict
import heapq

class Twitter:
    def __init__(self):
        # Step 1: Initialize data structures
        self.tweets = defaultdict(list)  # userId -> list of (timestamp, tweetId)
        self.follows = defaultdict(set)  # followerId -> set of followeeIds
        self.timestamp = 0  # Global tweet counter

    def postTweet(self, userId: int, tweetId: int) -> None:
        # Step 2: Add tweet with current timestamp
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        # Step 3: Get all relevant users (self + followees)
        users = self.follows[userId] | {userId}  # Union with self
        feed = []

        # Step 4: Heap to merge recent tweets
        heap = []
        for uid in users:
            for time, tweet in reversed(self.tweets[uid][-10:]):  # Last 10 tweets
                heapq.heappush(heap, (-time, tweet))

        # Step 5: Extract top 10 recent tweets
        while heap and len(feed) < 10:
            _, tweet = heapq.heappop(heap)
            feed.append(tweet)

        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        # Step 6: Add followee to follower's set
        self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        # Step 7: Remove followee from follower's set
        self.follows[followerId].discard(followeeId)

• Line 6-9: Initialize:
• tweets: Maps user to tweet list.
• follows: Maps follower to followees.
• timestamp: Tracks order.
• Line 12-14: postTweet:
• Append (time, tweet), increment time.
• Line 17-27: getNewsFeed:
• Line 19: Combine user and followees.
• Line 22-23: Push recent tweets to heap (negate time for max heap).
• Line 25-27: Pop top 10.
• Line 30-31: follow: Add followee.
• Line 34-35: unfollow: Remove followee.
• Time Complexity:
• postTweet: O(1).
• getNewsFeed: O(f log f), f = followees + 1.
• follow/unfollow: O(1).
• Space Complexity: O(n) tweets, O(u²) follows.

This is a tweet-streaming star!

Alternative Solution: List-Based Approach

Why an Alternative Approach?

The list-based approach offers a simpler, more straightforward design—O(1) for post/follow/unfollow, O(n log n) for feed retrieval—using lists to store all tweets and follower relationships. It’s easier to implement but less efficient for feed retrieval. It’s like keeping a big logbook of all tweets, then sorting through it each time—basic but clear!

How It Works

• Data Structures:
• tweets: List of (userId, tweetId, timestamp).
• follows: Hash map of follower to followee set.
• Methods:
• postTweet: Append to tweet list.
• follow/unfollow: Update follow set.
• getNewsFeed: Filter and sort all tweets, take top 10.

Step-by-Step Example

Same Operations as Above:

• Initialize: tweets = [], follows = {}.
• postTweet(1, 5): tweets = [(1, 5, 0)].
• getNewsFeed(1): Filter → [(1, 5, 0)] → [5].
• follow(1, 2): follows[1] = {2}.
• postTweet(2, 6): tweets = [(1, 5, 0), (2, 6, 1)].
• getNewsFeed(1): Filter → [(1, 5, 0), (2, 6, 1)] → sort → [6, 5].
• unfollow(1, 2): follows[1] = {}.
• getNewsFeed(1): Filter → [(1, 5, 0)] → [5].

Code for List-Based Approach

Copy codeclass Twitter:
    def __init__(self):
        self.tweets = []  # List of (userId, tweetId, timestamp)
        self.follows = defaultdict(set)
        self.timestamp = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets.append((userId, tweetId, self.timestamp))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        users = self.follows[userId] | {userId}
        feed = [tweet for uid, tweet, time in self.tweets if uid in users]
        feed.sort(key=lambda x: x[2], reverse=True)
        return [tweet for _, tweet, _ in feed[:10]]

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

• Line 6-9: Simple list and set setup.
• Line 12-14: Append tweet with timestamp.
• Line 17-20: Filter, sort, take top 10.
• Time Complexity:
• postTweet/follow/unfollow: O(1).
• getNewsFeed: O(n log n)—sort all tweets.
• Space Complexity: O(n) tweets, O(u²) follows.

It’s a tweet-logging basic!

Comparing the Two Solutions

• Hash Map with Heap (Best):
• Pros: O(f log f) feed, O(1) others, efficient for frequent feeds.
• Cons: More complex with heap.
• List-Based (Alternative):
• Pros: O(1) operations except feed, simpler.
• Cons: O(n log n) feed, slower for large tweet counts.

Heap wins for feed efficiency.

Additional Examples and Edge Cases

• Single user, one tweet: [5].
• No follows: Only user’s tweets.
• Empty feed: [].

Both handle these perfectly.

Complexity Breakdown

• Heap: Feed O(f log f), Others O(1), Space O(n + u²).
• List: Feed O(n log n), Others O(1), Space O(n + u²).

Heap’s feed speed shines.

Key Takeaways

• Heap: Merge efficiently!
• List: Sort simply!
• Design: Balance trade-offs.
• Python Tip: Heaps optimize—see [Python Basics](/python/basics).

Final Thoughts: Tweet Like a Pro

LeetCode 355: Design Twitter in Python is a system design delight. The heap approach streams feeds with flair, while the list method keeps it basic. Want more design fun? Try LeetCode 146: LRU Cache or LeetCode 208: Implement Trie. Ready to design? Head to Solve LeetCode 355 on LeetCode and build your Twitter today!