[LeetCode] 355. Design Twitter (Max Priority Queue Algorithm)

Table of Contents

Description

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user’s news feed.

Implement the Twitter class:

• Twitter() Initializes your twitter object.
• void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
• List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
• void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Example 1:

Input

["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

Output

[null, null, [5], null, null, [6, 5], null, [5]]

Explanation

Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Approach (Max Priority Queue / Heap)

We previously used merge and sort to retrieve the most recent tweets from a user’s feed, which can be inefficient, especially with many users and tweets. 👉 Solution

However, we use a max heap (priority queue) to efficiently retrieve the 10 most recent tweets among all followees and the user. Each user’s tweets are stored in reverse chronological order. We push the latest tweet from each user into the heap, then repeatedly pop the most recent tweet and push the next most recent tweet from the same user, until we have 10 tweets or the heap is empty.

Solution

var Twitter = function () {
  // Map from userId to list of tweets (each tweet has id, createdAt timestamp, and userId)
  this.tweetsMap = {};
  // Map from followerId to a set of followeeIds (users being followed)
  this.followMap = {};
  // Global timestamp to simulate tweet posting time, increments with each tweet
  this.timestamp = 0;
};

/**
 * Compose a new tweet
 * @param {number} userId - ID of the user posting the tweet
 * @param {number} tweetId - ID of the tweet
 * @return {void}
 */
Twitter.prototype.postTweet = function (userId, tweetId) {
  // Initialize tweet list for user if not present
  this.tweetsMap[userId] ||= [];

  // Add the new tweet with incremented timestamp and userId
  this.tweetsMap[userId].push({
    id: tweetId,
    createdAt: ++this.timestamp,
    userId,
  });
};

/**
 * Retrieve the 10 most recent tweet IDs in the user's news feed.
 * News feed includes tweets by the user and those they follow.
 * @param {number} userId - ID of the user retrieving the news feed
 * @return {number[]} List of tweet IDs ordered from most recent to least recent
 */
Twitter.prototype.getNewsFeed = function (userId) {
  const LIMIT = 10;
  // Max priority queue to retrieve tweets ordered by createdAt timestamp
  const maxHeap = new MaxPriorityQueue(tweet => tweet.createdAt);
  // Set of userIds that user follows; empty set if none
  const followeeIds = this.followMap[userId] || new Set();
  // Map to track how many tweets have been popped per user
  const tweetCountMap = {};
  const result = [];

  // Include user's own tweets by adding userId to followeeIds set
  followeeIds.add(userId);

  // For each followed user, enqueue their latest tweet and initialize pop count
  followeeIds.forEach(id => {
    const tweets = (this.tweetsMap[id] ||= []);

    if (tweets.length) {
      maxHeap.enqueue(tweets[tweets.length - 1]);
      tweetCountMap[id] = 0;
    }
  });

  // Retrieve up to LIMIT most recent tweets
  while (result.length < LIMIT && maxHeap.size() > 0) {
    // Get the most recent tweet
    const tweet = maxHeap.dequeue();
    const userId = tweet.userId;

    // Add tweet id to result
    result.push(tweet.id);
    // Increment pop count for this user
    tweetCountMap[userId]++;

    // Calculate the index of the next older tweet for this user
    const tweets = this.tweetsMap[userId];
    const nextIndex = tweets.length - 1 - tweetCountMap[userId];

    // If there is an older tweet, enqueue it
    if (tweets[nextIndex]) {
      maxHeap.enqueue(tweets[nextIndex]);
    }
  }

  return result;
};

/**
 * Follower follows a followee
 * @param {number} followerId - ID of the follower
 * @param {number} followeeId - ID of the user to be followed
 * @return {void}
 */
Twitter.prototype.follow = function (followerId, followeeId) {
  // Initialize followee set for follower if not present
  this.followMap[followerId] ||= new Set();
  // Add followee to follower's follow set
  this.followMap[followerId].add(followeeId);
};

/**
 * Follower unfollows a followee
 * @param {number} followerId - ID of the follower
 * @param {number} followeeId - ID of the user to be unfollowed
 * @return {void}
 */
Twitter.prototype.unfollow = function (followerId, followeeId) {
  // Initialize followee set for follower if not present (to avoid errors)
  this.followMap[followerId] ||= new Set();
  // Remove followee from follower's follow set
  this.followMap[followerId].delete(followeeId);
};

/**
 * Your Twitter object will be instantiated and called as such:
 * var obj = new Twitter()
 * obj.postTweet(userId,tweetId)
 * var param_2 = obj.getNewsFeed(userId)
 * obj.follow(followerId,followeeId)
 * obj.unfollow(followerId,followeeId)
 */

Complexity Analysis

Time Complexity

The time complexity is as follows:

• postTweet: $O(1)$, since appending a tweet to a user’s list is a constant-time operation.
• follow / unfollow: $O(1)$, as adding or removing a user from a set is constant time.
• getNewsFeed: $O(N \log N + k \log N)$, where $N$ is the number of users in the feed (the user and their followees), and $k$ is the maximum number of tweets per user considered (typically up to 10). We push the latest tweet from each user into a max heap (size $N$), and for up to $10$ tweets, we pop from the heap and may push the next tweet from the same user. Thus, the dominant cost is heap operations, each $O(\log N)$, for up to $kN$ tweets in the worst case, but typically $O(N \log N)$ for initialization and $O(10 \log N)$ for extracting the feed.

Space Complexity

The space complexity is $O(n + t)$, where $n$ is the number of users and $t$ is the total number of tweets stored.