2021 LC Weekly Contest 230
Created: 2021/02/28 Updated: 2021/02/28 14:00 JSTTable of Contents
 Q2 1774  Closest Dessert Cost
 Q3 1775  Equal Sum Arrays With Minimum Number of Operations
 Q4 1776  Car Fleet II
Q2 1774  Closest Dessert Cost
Solution: Bruteforce with limit
BruteForce thinking, go and grab single base then go through toppings by acending order.
To avoid traversing all possible combinations, we have a diff which represents the absolute value of difference between current cost and target. If current cost exceed is smaller than target, we can continue without thinking about this, otherwise we need to stop if current cost is much greater than tracked minimal value.
Return target if current cost exactly equals to target.

Time: O(logM + logN + logN * 2) = O(logM logN)  Space: O(M*N) where N is length of M * N
class Solution:
def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) > int:
# Need one base and 0 or n toppings to have minimize(diff(target, cost)), if multiple choose smaller cost
# dfs?
# bfs?
toppingCosts.sort()
baseCosts.sort()
targets = collections.deque()
minDiff = float("inf")
for base in baseCosts:
targets.append(target  base)
minDiff = min(minDiff, abs(target  base))
# If any of base cost is greater than target
if targets[0] < 0:
return baseCosts[0]
for top in toppingCosts:
newTargets = []
i = 0
while i < len(targets):
# 0
top0 = targets[i]
if top0 > 0:
newTargets.append(top0)
elif top0 == 0:
return target
else:
if abs(top0) <= minDiff:
newTargets.append(top0)
minDiff = abs(top0)
# 1
top1 = targets[i]  top
if top1 > 0:
newTargets.append(top1)
elif top1 == 0:
return target
else:
if abs(top1) <= minDiff:
newTargets.append(top1)
minDiff = abs(top1)
# 2
top2 = targets[i]  top * 2
if top2 > 0:
newTargets.append(top2)
elif top2 == 0:
return target
else:
if abs(top2) <= minDiff:
newTargets.append(top2)
minDiff = abs(top2)
i += 1
# print(minDiff, newTargets)
if len(newTargets) == 0:
break
targets = newTargets
# print(targets)
targets.sort(key=lambda key: abs(key))
return target  targets[0]
Q3 1775  Equal Sum Arrays With Minimum Number of Operations
Solution: Greedy with min/max heap
To shrink diff between two array, we greedly change the small/large value from one of the array under the condition that it has larger effect on shrinking the difference.
 Time: O(M * logM + N * logN) where M is length of nums1, and N is length of nums2
 Space: O(M + N)
from heapq import heapify, heappush, heappop
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int]) > int:
# [1, 6]
# abs(sum(nums1)  sum(nums[2])) > 0
# Edge case
if len(nums1) > 6 * len(nums2) or len(nums2) > 6 * len(nums1):
return 1
self.res = 0
sum1 = sum(nums1)
sum2 = sum(nums2)
big = None
small = None
if sum1 > sum2:
big = [1 * i for i in nums1]
heapify(big)
small = nums2
heapify(small)
elif sum2 > sum1:
big = [1 * i for i in nums2]
heapify(big)
small = nums1
heapify(small)
else:
return 0
diff = abs(sum1  sum2)
res = 0
canChangeBig = True
while diff > 0:
# print(big[0], small[0])
if abs(1 * big[0]  1) >= abs(small[0]  6) and canChangeBig:
if big[0] == 1:
canChangeBig = False
continue
if big[0]  1 >= diff:
return res + 1
pop = 1 * heappop(big)
#print("big: ", pop, " > 1")
diff = (pop  1)
heappush(big, 1)
else:
if 6  small[0] >= diff:
return res + 1
pop = heappop(small)
#print("small: ", pop, " > 6")
diff = (6  pop)
heappush(small, 6)
res += 1
return res