BakerHub

# A. Finding 3-Digit Even Numbers (opens new window)

Permutation.

DETAILS 
def findEvenNumbers(self, A: List[int]) -> List[int]:
        c = collections.Counter(A)
        res = []
        for k in c.keys():
            res.extend([k] * min(3, c[k]))
        ans = []
        for _ in itertools.permutations(res, 3):
            ans.append("".join(map(str, list(_))))
        ans = list(set(ans))

        return sorted([x for x in ans if x[0] != "0" and int(x[2]) %2 == 0])

# B. Delete the Middle Node of a Linked List (opens new window)

Two-Pass.

DETAILS 
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = q = head
        num = 0
        while p:
            num += 1
            p = p.next
        if num == 1: 
            return None
        curr, mid = 0, num // 2
        
        while q:
            curr += 1
            if curr == mid:
                q.next = q.next.next
                return head
            else:
                q = q.next

One-Pass

DETAILS 
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        fast = slow = ListNode(0)
        fast.next = slow.next = head
        if not fast.next.next:
            fast.next = fast.next.next
            return fast.next
        
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        slow.next = slow.next.next
        return head

# C. Step-By-Step Directions From a Binary Tree Node to Another (opens new window)

LCA

DETAILS 
def getDirections(self, root: Optional[TreeNode], start: int, dest: int) -> str:
        p, q = TreeNode(0), TreeNode(0)
        dq = collections.deque([root])
        fa = collections.defaultdict(int)
        lft = collections.defaultdict(int)
        rgt = collections.defaultdict(int)
        
        while dq:
            curr = dq.popleft()
            if curr.val == start:
                p = curr
            if curr.val == dest:
                q = curr
            if curr.left:
                fa[curr.left.val] = curr.val
                lft[curr.val] = curr.left.val
                dq.append(curr.left)
            if curr.right:
                fa[curr.right.val] = curr.val
                rgt[curr.val] = curr.right.val
                dq.append(curr.right)
        
        def LCA(root, p, q):
            if root in (None, p, q): return root
            left, right = (LCA(kid, p, q)
                           for kid in (root.left, root.right))
            return root if left and right else left or right
        
        anc = LCA(root, p, q)
        ans = ""
        while start != anc.val:
            start = fa[start]
            ans += "U"
        nxt = ""
        while dest != anc.val:
            tmp = fa[dest]
            if lft[tmp] == dest:
                nxt += "L"
            else:
                nxt += "R"
            dest = tmp

        return ans + nxt[::-1]

# D. Valid Arrangement of Pairs (opens new window)

DETAILS 
def validArrangement(self, A: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        degree = defaultdict(int)
        for x, y in A: 
            graph[x].append(y)
            degree[x] += 1
            degree[y] -= 1
                
        for k in degree: 
            if degree[k] == 1: 
                x = k
                break 
                
        ans = []

        def fn(x): 
            while graph[x]: 
                fn(graph[x].pop()) 
            ans.append(x)
        
        fn(x)
        ans.reverse()
        return [[ans[i], ans[i + 1]] for i in range(len(ans) - 1)]

← Weekly Contest 269 →