Practice #017: Leetcode Biweekly Contest 82

Leetcode: 2331. Evaluate Boolean Binary Tree

Problem Statement

Traverse the full binary tree applying the rule. Time complexity is \(O(n)\) and space is \(O(maxDepth)\). 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if root.val == 0:
            return False
        if root.val == 1:
            return True
        if root.val == 2:
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)
        return self.evaluateTree(root.left) and self.evaluateTree(root.right)

Leetcode: 2332. The Latest Time to Catch a Bus

Problem Statement

Retrospective: Simplify the problem by generating the possible candidates and them pick between them!

Can we first generate all candidates and then pick the best one? Generate numbers that represent either a real ticket and the possible new one. Then, simulate the problem and keep track of the last possible candidate to pick a bus. Time and space complexity is \(O(n)\). 

from typing import List

class Solution:
    def latestTimeCatchTheBus(self, b: List[int], p: List[int], c: int) -> int:
        b = list(sorted(b))
        p = list(sorted(p))

        u = set(p)
        t = [(s, True) for s in p]
        for i in range(len(p)):
            if p[i] - 1 not in u:
                u.add(p[i] - 1)
                t.append((p[i] - 1, False))
            if p[i] + 1 not in u and p[i] + 1 <= b[-1]:
                u.add(p[i] + 1)
                t.append((p[i] + 1, False))
        for i in range(len(b)):
            if b[i] not in u:
                t.append((b[i], False))
        t = list(sorted(t))

        i = 0
        j = 0
        ans = None
        while i < len(b) and j < len(t):
            k = 0
            while k < c and j < len(t) and t[j][0] <= b[i]:
                if t[j][1] == False:
                    ans = t[j][0]
                else:
                    k += 1
                j += 1
            i += 1

        return ans

assert Solution().latestTimeCatchTheBus([10,20], [2,17,18,19], 2) == 16
assert Solution().latestTimeCatchTheBus([20,30,10], [19,13,26,4,25,11,21], 2) == 20

Leetcode: 2333. Minimum Sum of Squared Difference

Problem Statement

Can we simplify the problem while keeping it the same? We can substitute \(nums_1\) and \(nums_2\) by \(a[i]=\mbox{abs}(nums_1[i], nums_2[i])\). With that, the problem continues the same: modify any elements of \(a\) by \(+1\) or \(-1\) at most \(k=k_1+k_2\). The key to make this process efficient is to group \(a[i]\) with \(a[j]\) if \(a[i]=a[j]\). To do so, we have to pick the biggest \(a[i]\) and reduce it until there is no more operations left. This can generate a new number smaller than the previous one or two numbers if we couldn't reduce them all, but we will never have more than \(10^5\) numbers in the process. 

from typing import List
from heapq import heappush, heappop


class Solution:
    def minSumSquareDiff(self, a: List[int], b: List[int], k1: int, k2: int) -> int:
        n = len(a)
        k = k1 + k2

        c = {}
        p = []

        def push(v, cnt=1):
            if v not in c:
                heappush(p, -v)
                c[v] = cnt
            else:
                c[v] += cnt

        def pop():
            v = -heappop(p)
            cnt = c[v]
            c.pop(v)
            return (v, cnt)

        for i in range(n):
            push(abs(a[i] - b[i]))

        while k > 0 and p[0] != 0:
            if len(p) == 1:
                v, cnt = pop()
                d = min(v, k // cnt)
                if d > 0:
                    push(v - d, cnt)
                    k -= d * cnt
                else:
                    push(v - 1, k)
                    push(v, cnt - k)
                    k -= k
            else:
                v, cnt = pop()
                d = min(v, k // cnt, abs(v + p[0]))
                if d > 0:
                    push(v - d, cnt)
                    k -= d * cnt
                else:
                    push(v - 1, k)
                    push(v, cnt - k)
                    k -= k

        ans = 0
        for v, c in c.items():
            ans += v * v * c
        return ans


assert Solution().minSumSquareDiff([1, 2, 3, 4], [2, 10, 20, 19], 0, 0) == 579
assert Solution().minSumSquareDiff([1, 4, 10, 12], [5, 8, 6, 9], 1, 1) == 43

Leetcode: 2334. Subarray With Elements Greater Than Varying Threshold

Problem Statement

How can we find the solution knowing part of it? Suppose that we know the largest value \(k\) contained the in the solution of the problem. We can find the subarray by extending the subarray with \(k\) to left (Problem: Previous greater integer in unsorted array) and right (Problem: Next greater integer in unsorted array) while they are smaller than \(k\). This process can be solved efficiently with \(O(n)\) pre-processing and \(O(1)\) to query. We don't know \(k\), but we can try all possible ones. Time and space complexity is \(O(n)\). 

from typing import List
from math import floor


def prev_greater(a):
    ans = [-1] * len(a)
    stack = []
    for i, x in enumerate(a):
        while len(stack) > 0 and a[stack[-1]] < x:
            stack.pop()
        ans[i] = -1 if len(stack) == 0 else stack[-1]
        stack.append(i)
    return ans


def next_greater(a):
    ans = [len(a)] * len(a)
    stack = []
    for i, x in enumerate(a):
        while len(stack) > 0 and a[stack[-1]] < x:
            ans[stack.pop()] = i
        stack.append(i)
    return ans


class Solution:
    def validSubarraySize(self, nums: List[int], t: int) -> int:
        a = [floor(t / v) + 1 for v in nums]
        for p, x, n in zip(prev_greater(a), a, next_greater(a)):
            s = p + 1
            e = n - 1
            if e - s + 1 >= x:
                return e - s + 1
        return -1


assert Solution().validSubarraySize([1, 3, 4, 3, 1], 6) == 3
assert Solution().validSubarraySize([6, 5, 6, 5, 8], 7) == 5