2021 LC Weekly Contest 226

Table of Contents

• Q1 1742 - Maximum Number of Balls in a Box
• Q2 1743 - Restore the Array From Adjacent Pairs
• Q3 1744 - Can You Eat Your Favorite Candy on Your Favorite Day?
• Q4 1745 - Palindrome Partitioning IV

Contest - LeetCode 226

Q1 1742 - Maximum Number of Balls in a Box

Solution: HashMap

This first question needs a little bit more work than the ones in normal weekly contest. But we still can just loop al numbers, for each one try to calculate the sum of each digit then plus one in the map.

• Time: O(N * L) where N is the number count and L is the digit count for each number.
• Space: O(N) where N is the number count and used for hashMap.

Q2 1743 - Restore the Array From Adjacent Pairs

Solution: HashMap and Graph traversal

Since each number is unique, it is perfect for key of hashMap. Another key point is to find any end of the original array, which has the property that it has no two neighbors. After forming this map, we can traverse from any one of the end number, then form the rest of the numbers by using a queue.

• Time: O(N) where N is the number count.
• Space: O(N) where N is the number count.

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        if len(adjacentPairs) == 1:
            return adjacentPairs[0]
        
        m = collections.defaultdict(list)
        for pair in adjacentPairs:
            l, r = pair[0], pair[1]
            m[l].append(r)
            m[r].append(l)
        
        res = []
        # find one which has no only one neighbor
        q = collections.deque()
        for k, v in m.items():
            if len(v) == 1:
                q.append(k)
                break
        visited = set()
        while len(q) > 0:
            cur = q.pop()
            visited.add(cur)
            res.append(cur)
            for neighbor in m[cur]:
                if neighbor not in visited:
                    q.append(neighbor)
        
        return res

Q3 1744 - Can You Eat Your Favorite Candy on Your Favorite Day?

Solution: think about the conditions?

Because the candies need to be consumed sequentially, it is perfect for prefix sum. prefix[i]indicates the total sum until type i. Let’s give the parameter name: type, day and limit. Since the all parameters given by query is 0-indexed, we need to think about easy cases:

1. day = 0 && type = 0: always true since candy type will be eaten on the first day in the very beginning.
2. day = 0 && type != 0: one day can be up to limit, so if prefix sum of previous day is less then limit, then we can assure than candy type will be eaten.
3. day != 0 && type = 0: candy 0 will be eaten firstly so it needs to have more than limit = 1 multiply day - 1
4. day > prefix[t]: when using minimal limit = 1 multiply day - 1 is greater than prefix sum of type, which means candies will be eaten to 0 before day, then it is not possible
5. (day + 1) * limit <= prefix[t-1]: if even eat maximally candy until day, we cannot finish prefix[t-1] candies, then it is not possible to eat candy t on this day.

• Time: O(max(M, N)): where M is candy types and N is query count.
• Space: O(M): where M is candy types.

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        prefix = [candiesCount[0]]
        for i in range(1, len(candiesCount)):
            prefix.append(candiesCount[i] + prefix[-1])
        
        def check(query):
            t, day, limit = query
            # check limit 
            if day == 0 and t == 0:
                return True
            if day == 0 and t != 0:
                return prefix[t-1] < limit
            if day != 0 and t == 0:
                return prefix[t] > day
            if day >= prefix[t] :
                return False
            if limit * (day + 1) <= prefix[t-1]:
                return False
            
            return True
        
        res = []
        for query in queries:
            res.append(check(query))
        return res

Q4 1745 - Palindrome Partitioning IV

Solution: DP with table (traditional dp for palindrome)

The key point to consider what does dp[i][j] mean in this case. So the best answer is boolean value of palindrome for substring s[i:j+1].

What about the state transition? it is simple to know when substring from i to j inclusive is palindrome, then whether larger subtring from i-1 to j+1 is palindrome depends on s[i-1] == s[j+1], so the state transition is dp[i][j] = s[i] == s[j] && dp[i-1][j+1].

So a bottom-up solution is to expand the i and j. Then we need to iterate i and j in opposite direction. In this case is: i goes left and j goes right.

• Time: O(N^2) where N is length of given string.
• Space: O(N^2) where N is length of given string. For dp table.

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        
        for i in reversed(range(len(s))):
            for j in range(i, len(s)):
                if i == j:
                    dp[i][j] = True
                elif i + 1 == j:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
                    
        
        for i in range(1, len(s)):
            for j in range(i, len(s) - 1):
                if dp[0][i-1] and dp[i][j] and dp[j+1][len(s) - 1]:
                    return True
        
        return False