Day 25 of LeetCode

Documenting LeetCode solving.

Q77

355. Design Twitter

Medium. Min heap. Should be hard.

class Twitter:

    def __init__(self):
        self.count = 0
        self.followMap = defaultdict(set) # userId -> set of followerId
        self.tweetMap = defaultdict(list) # userId -> list of [count, tweetId]

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        # Using negative in pythin min heap to get the most recent
        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        minHeap = []

        # Follower is its followee
        self.followMap[userId].add(userId)
        # Get each followee's most recent tweet and add it to the min heap
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap:
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                # index - 1: get the next most recent tweet
                minHeap.append([count, tweetId, followeeId, index - 1])
        heapq.heapify(minHeap)

        # Get 10 most recent
        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            # If the current followee still has tweets
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        return res

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.followMap:
            self.followMap[followerId].remove(followeeId)

Q78

78. Subsets

Medium. Backtracking

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        subset = []
        def dfs(i):
            if i >= len(nums):
                # Append the subset list directly 
                # without copying (i.e., res.append(subset)), 
                # would be appending a reference to the subset list, 
                # not its current snapshot.
                res.append(subset.copy())
                return

            # Decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)

            # Decision NOT to include nums[i]
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

Q79

39. Combination Sum

Medium. Backtracking

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        cur = []
        def dfs(i, total):
            if total == target:
                res.append(cur.copy())
                return
            if i >= len(candidates) or total > target:
                return

            cur.append(candidates[i])
            # One candidates can repeat
            dfs(i, total + candidates[i])

            cur.pop()
            dfs(i + 1, total)

        dfs(0, 0)

        return res