class Solution:
    def reformatDate(self, date: str) -> str:
        m_to_idx = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
        day, month, year = date.split()
        day, month = day[:-2], str(m_to_idx.index(month)+1)
        if len(day) < 2: day = '0' + day
        if len(month) < 2: month = '0' + month
        return f'{year}-{month}-{day}'

class Solution:
    def canMakeArithmeticProgression(self, A: List[int]) -> bool:
        A = sorted(A)
        dis = A[0] - A[1]
        return all(a-b==dis for a, b in zip(A, A[1:]))

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        rst = []
        stack, cur = [], root
        while cur or stack:
            while cur:
                # Push current node
                stack.append(cur)
                # move to left or right child
                cur = cur.left or cur.right
            # all child is processed.
            cur = stack.pop()
            # update current state based on state from child nodes
            rst.append(cur.val)
            # upload state to parent
            # ...

            # Move to right node or previous level
            if stack and stack[-1].left == cur:
                cur = stack[-1].right
            else:
                cur = None
        return rst

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        '''
        # Recursive
        def dfs(cur):
            if cur is None: return 0, None
            cnt_l, node_l = dfs(cur.left)
            cnt_r, node_r = dfs(cur.right)
            if cnt_l == 2: return 2, node_l
            if cnt_r == 2: return 2, node_r

            if (cnt_l+cnt_r+(cur.val in [p.val, q.val])) == 2: return 2, cur
            
            return (1, cur) if cur.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))
        return dfs(root)[1]
        '''
        
        # Non-recursive
        ret = [0] * 4 # cnt_l, node_l, cnt_r, node_r
        stack, cur = [], ((root, [0] * 4), ret, 'l') # Carry all necessary data for current node and parent node
        while cur[0][0] or stack:
            while cur[0][0]:
                stack.append(cur)
                if cur[0][0].left: cur = ((cur[0][0].left,  [0]*4), cur[0][1], 'l')
                else: cur = ((cur[0][0].right,  [0]*4), cur[0][1], 'r')
            # Pop and unpack node and state
            # ((cur_node, cur_state), (parent...), dir)
            (node, (cnt_l, node_l, cnt_r, node_r)), p_state, dir = stack.pop()

            # Compute local state based on state from childs
            if cnt_l == 2: my_ret = 2, node_l
            elif cnt_r == 2:  my_ret = 2, node_r
            elif (cnt_l+cnt_r+(node.val in [p.val, q.val])) == 2:  my_ret = 2, node 
            else: my_ret = (1, node) if node.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))

            # Upload state to parent 
            if dir == 'l': p_state[:2] = my_ret
            else: p_state[2:] = my_ret
            
            # :) Move to right or previous level
            if stack and stack[-1][0][0].left == node:
                cur = ((stack[-1][0][0].right, [0] * 4), stack[-1][0][1], 'r')
            else:
                cur = ((None, None), (None, None), None)

        return ret[1]

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        arr = [start+2*i for i in range(n)]
        rst = 0
        for a in arr:
            rst ^= a
        return rst

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        rst = []
        for i, price in enumerate(prices):
            for j in range(i+1, len(prices)):
                if prices[j] <= price:
                    rst.append(price-prices[j])
                    break
            else:
                rst.append(price)
        return rst

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # Next smaller num
        stack = []
        for i, v in enumerate(prices):
            while stack and prices[stack[-1]] >= v:
                prices[stack.pop()] -= v
            stack.append(i)
        return prices

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        rst = [0] * (len(nums)+1)
        for i, v in enumerate(nums):
            rst[i+1] = rst[i] + v
        return rst[1:]

Python 3.7.3 (default, Mar 27 2019, 09:23:15)
[Clang 10.0.1 (clang-1001.0.46.3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a, *args = [1, 2, 3, 4]
>>> a
1
>>> args
[2, 3, 4]

#!/usr/local/bin/python3

from typing import List
from collections import defaultdict

def topological_sort(vertices: int, edges: List[List[int]]) -> List[int]:
    '''
    Args:
        vertices: 0, 1, 2, .... , vertices-1
        edges: (start, end, weight)
    Return:
        A valid topological ordering
    Raise:
        ValueError: if there is not a valid topological ordering.
    '''
    # build graph
    graph, indegrees = defaultdict(set), [0] * vertices
    for (start, end, weight) in edges:
        graph[start].add(end)
        indegrees[end] += 1
    # find vertices have zero indegree
    zero_degrees = [vertex for vertex, indegree in enumerate(indegrees) if indegree == 0]
    ordering = []
    while zero_degrees:
        vertex = zero_degrees.pop()
        ordering.append(vertex)
        for successor in graph[vertex]:
            indegrees[successor] -= 1
            if indegrees[successor] == 0:
                zero_degrees.append(successor)
    if len(ordering) != vertices:
        raise ValueError('There is not a valid topological ordering')
    return ordering


ordering = topological_sort(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]])
print('->'.join([str(vertex) for vertex in ordering]))