2021 LC Weekly Contest 222

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

Contest - LeetCode 222

Q2 1711 - Count Good Meals

Solution: HashMap

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.

1. since the deliciousness is within a fixed range which is 2^20 then we can iterate each power of 2 for given deliciousness value.
2. 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

Q4 1713 - Minimum Operations to Make a Subsequence

TODO