# 2021 LC Weekly Contest 226

Created: 2021/01/31 Updated: 2021/01/31 18:30 JST### 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

## 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:

`day = 0 && type = 0`

: always true since`candy type`

will be eaten on the first day in the very beginning.`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.`day != 0 && type = 0`

:`candy 0`

will be eaten firstly so it needs to have more than`limit = 1`

multiply`day - 1`

`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`(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.

## 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
```