2021 LC Weekly Contest 222Created: 2021/01/04 Updated:
Table of Contents
- Q2 1711 - Count Good Meals
- Q3 1712 - Ways to Split Array Into Three Subarrays
- Q4 1713 - Minimum Operations to Make a Subsequence
Q2 1711 - Count Good Meals
This problem is similar to two sum question Two Sum - LeetCode What we need to do is to store and count the seen values in a HashMap/Dict, then once we found the target (power of 2 minus current value) is in the map, we can increment it to our sum result.
- since the deliciousness is within a fixed range which is 2^20 then we can iterate each power of 2 for given deliciousness value.
- use bitwise operation for power of 2, 2 « x
- Time: O(21*n) where n is length of deliciousness and 21 is the power iteration count from 1.
- Space: O(n) where n is length of deliciousness.
from collections import Counter class Solution: def countPairs(self, deliciousness: List[int]) -> int: # similar to two sum. res = 0 counted = Counter() for d in deliciousness: for i in range(22): twoPorwer = 1 << i res += counted[twoPorwer - d] counted[d] += 1 return res % (10**9 + 7)
Q3 1712 - Ways to Split Array Into Three Subarrays
Solution: PrefixSum + Binary Search
- TODO(Write binary search to find leftmost or rightmost by hand)
Solution: PrefixSum + Two pointer
PrefixSum takes O(n) but save our time for compute any sum of sublist by O(1). We use i, j, k to be the variables for computing.
- i: first pointer we choose.
- j: leftmost pointer that we can choose for second pointer, inclusive.
- k: k - 1 is rightmost pointer that we can choose for second pointer, exclusive.
For finding j: prefixSum[i] * 2 == prefixSum[j] -> j+1
For finding k: prefixSum[-1] - prefixSum[i] >= (prefixSum[k] - prefixSum[i]) * 2 -> k+1
- Time: O(n) since j and k never decreases.
- Space: O(n) where n is length of nums, for saving prefixSum. can be O(1) if replacing input into prefixSum.
class Solution: def waysToSplit(self, nums: List[int]) -> int: mod = 10**9 + 7 # prefix sum O(n) prefixSum =  curSum = 0 for num in nums: curSum += num prefixSum.append(curSum) # i, j ,k # right pointer can be chosed from j ~ k # leftmost j: prefix[i] * 2 == prefix[j] # rightmost k: (prefix[-1] - prefix[i]) // 2 == prefix[k] - prefix[i] res = j = k = 0 for i in range(len(nums)): # Find qualified [j, k) # j might be greater than i+1 after first for. # j is inclusive j = max(i + 1, j) while j < len(nums)-1 and prefixSum[i] * 2 > prefixSum[j]: j += 1 # k is exclusive k = max(j, k) while k < len(nums)-1 and prefixSum[-1] - prefixSum[i] >= (prefixSum[k] - prefixSum[i]) * 2: k += 1 res += (k - j) return res % mod