[C++ / Beats 99%] Concise solution with explanation


  • 1
    H
    class Twitter {
    private:
        // Twitters from all users.
        vector<int> msg;
        
        // Key - user_id; Val - the [indexes] of [twitters in msg] belong to this user.
        // Because user cannot delete message, we use vector for better random access performance.
        unordered_map<int, vector<int>> post;
        
        // Key - user_id; Val - the [user_ids] that this user follows.
        // Because user can add/delete other users, we use set for better search/add/remove performance.
        unordered_map<int, set<int>> following;
        
        class cmp {
            public:
                // The compare function for priority queue.
                bool operator() (pair<vector<int>*, int> &a, pair<vector<int>*, int> &b) {
                    // Compare the indexes (represent the timestamp) in msg.
                    return (*a.first)[a.second] < (*b.first)[b.second];
                }
        };
        
    public:
        Twitter() { }
        
        void postTweet(int userId, int tweetId) {
            post[userId].push_back(msg.size());
            msg.push_back(tweetId);
        }
        
        vector<int> getNewsFeed(int userId) {
            // Pair.first - the msg index vector from one user; Pair.second - the index to be considered next.
            priority_queue<pair<vector<int>*, int>, vector< pair<vector<int>*, int> >, cmp> pq;
            if (!post[userId].empty()) pq.push(make_pair(&post[userId], post[userId].size() - 1));
            for (int i : following[userId]) if (!post[i].empty()) pq.push(make_pair(&post[i], post[i].size() - 1));
            
            vector<int> res;
            while (!pq.empty() && res.size() < 10) {
                auto it = pq.top(); 
                pq.pop();
                
                int msg_idx = (*it.first)[it.second];
                res.push_back(msg[msg_idx]);
                
                --it.second;
                if (it.second >= 0) pq.push(it);
            }
            return res;
        }
        
        void follow(int followerId, int followeeId) {
            // A user cannot follow self.
            if (followerId != followeeId) following[followerId].insert(followeeId);
        }
        
        void unfollow(int followerId, int followeeId) {
            if (following[followerId].count(followeeId)) following[followerId].erase(followeeId);
        }
    };
    

    Time complexity:

    1. Post twitter - O(1)
    2. Follow - O(1)
    3. Unfollow - O(1)
    4. Get new feed - O(m) (follows m users)
      4.1 Build heap from m elements - O(m)
      4.2 Retrieve 10 times from this heap - O(10 * log(m)) = O(log(m))
      4.3 Insert 10 times into this heap - O(10 * log(m)) = O(log(m))

    Space complexity:

    1. Minimum redundancy in msg, post and following.
    2. When retrieve new feed: O(m) additional spaces (follows m users)
      2.1 Vector(the container for priority queue) is of size m, will not increase.
      2.2 Vector contains pointers and int values, both are small in size.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.