LeetCode Weekly Contest 315 #

6204. Largest Positive Integer That Exists With Its Negative #

https://leetcode.com/contest/weekly-contest-315/problems/largest-positive-integer-that-exists-with-its-negative/

Pretty straightforward, with use of max and default to do much of the heavy lifting. Using a Counter could be replaced with a set for pretty equivalent performance.

from typing import List
from collections import Counter
class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        c = Counter(nums)

        return max([k for k in c.keys() if k > 0 and -k in c], default=-1)

6205. Count Number of Distinct Integers After Reverse Operations #

https://leetcode.com/contest/weekly-contest-315/problems/count-number-of-distinct-integers-after-reverse-operations/

Using a set, a brute force approach runs in time. The trickiest thing here is reversing integers, which can be done with [::-1] to reverse a string and int(x, 10) to parse the string x as base-10. (I worried about 0-prefix triggering octal, but perhaps this is not a concern.)

from typing import List
class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        s = set(nums) | { int(str(x)[::-1], 10) for x in nums }
        return len(s)

6219. Sum of Number and Its Reverse #

https://leetcode.com/contest/weekly-contest-315/problems/sum-of-number-and-its-reverse/

Because the constraint is up to 10^5, an O(N) brute force is sufficient. One trick I use here is brute-force checking the upper half and reversing into the lower half. If we start the brute from 0, then we’ll need special logic to determine how many 0s to trail after values.

For example – for 456, the reverse of 1 should be 100, not 1. Padding the end with zeros might work? But that does not seem sound, certainly not as sound as starting from halfway and working upward.

class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        for a in range(max(0, (num // 2) - 1), num + 1):
            if a + int(str(a)[::-1], 10) == num:
                return True
        return False

6207. Count Subarrays With Fixed Bounds #

https://leetcode.com/contest/weekly-contest-315/problems/count-subarrays-with-fixed-bounds/

This question is a sizable increment in difficulty above the previous questions. I spent about 10 minutes trying to think through a sliding window approach with nothing to show for it. I decided there are certain values that can definitely not be included that I should discard – any outside the range minK<=x<=maxK.

From here, I started to consider how to count the number of subarrays that contain both minK and maxK. My realization was that the “must be min” of minK and “must be max” of maxK don’t really matter at this point – we only need to ensure that minK and maxK are members of the subarray.

The number of subarrays containing minK and maxK can be found by:

(count of subarrays) - (count of subarrays that don't contain desired values)

With some background knowledge in combinatorics, I knew we could find the number of subarrays that don’t contain either of minK or maxK by counting the number of subarrays that don’t contain them independently, then subtract the overcount of subarrays that contain neither. A venn diagram is helpful for understanding.

Using a function to extract runs of a list that match a predicate is useful for both extracting the runs without the outliers and runs that do not contain either or both bounds.

from typing import List
class Solution:
    
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        run = -1
        total = 0
        
        within_bound_runs = list(self.runsWhere(nums, lambda x: minK <= x <= maxK))
        
        # print(within_bound_runs)
        
        return sum([self.withBounds(nums[run0:run1], minK, maxK) for run0, run1 in within_bound_runs])
        
    def runsWhere(self, nums: List[int], pred):
        run = -1
        total = 0
        for idx, val in enumerate(nums):
            if not pred(val):
                if run >= 0:
                    yield run, idx
                run = -1
                continue
            
            if run == -1:
                run = idx
        
        if run >= 0:
            yield run, len(nums)
    
    def withBounds(self, nums: List[int], minK: int, maxK: int) -> int:
        no_lower = list(self.runsWhere(nums, lambda x: x != minK))
        no_upper = list(self.runsWhere(nums, lambda x: x != maxK))
        no_neither = list(self.runsWhere(nums, lambda x: x != minK and x != maxK))
        # print('withBounds', nums)
        # print(no_lower)
        # print(no_upper)
        # print(no_neither)
        
        def num_suba(runs):
            return sum([self.numSubarrays(run1 - run0) for run0, run1 in runs])
        
        return self.numSubarrays(len(nums)) - num_suba(no_lower) - num_suba(no_upper) + num_suba(no_neither)
        
    
    def numSubarrays(self, n):
        return n * (n+1) // 2