```py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        c = 0
        res = []
        while(l1 or l2):
            s = 0 + c
            if l1:
                s += int(l1.val)
                l1 = l1.next
            if l2:
                s += int(l2.val)
                l2 = l2.next
            print(s) 
            
            resa = s % 10            
            res.append(resa)
            c = s // 10
            
        if(c!=0):
            res.append(c)
            
        l3 = ListNode(0)
        head = l3
        for i in range(0, len(res)):
            lt = res[i]
            l3.next = ListNode(lt)
            l3 = l3.next
        return head.nextclass Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)
        content = 0
        while s and g:
            if s[-1] >= g[-1]:
                s.pop()
                content += 1
            g.pop()
        return content# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.ans = 0
        def add(node):
            if not node:
                return
            add(node.right)
            self.ans += node.val
            node.val = self.ans
            add(node.left)
        add(root)
        return root## Recursive Solution
# ------------------------------------------

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        io = []
        
        if(root==None):
            return []
        
        def inorder(x):
            if(x.left!=None):
                inorder(x.left)
            io.append(int(x.val))
            if(x.right!=None):
                inorder(x.right)
                
        inorder(root)
        return io

# ------------------------------------------

## Iterative Solution using Stack
# ------------------------------------------

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        if(root==None):
            return []
        stack = []
        io = []
        c = root
        
        while(c!=None or len(stack)!=0):
            while(c!=None):
                stack.append(c)
                c = c.left
            c = stack.pop()
            io.append(c.val)
            c = c.right
        return io
                
            # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# ------------------------------------------

## Recursive Solution

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if (root==None):
            return []
        po = []
        def postorder(x):
            if not x:
                return
            postorder(x.left)
            postorder(x.right)
            po.append(x.val)
        postorder(root)
        return po
# ------------------------------------------

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# ------------------------------------------

## Recursive Solution

class Solution:                
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if(root==None):
            return []
        po = []
        def preorder(x):
            if x:
                po.append(x.val)
                preorder(x.left)
                preorder(x.right)

        preorder(root)
        return po

# ------------------------------------------

## Iterative Solution

class Solution:                
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if(root==None):
            return []
        stack = []
        po = []
        c = root
        
        while(c!=None or len(stack)!=0):
            while(c!=None):
                stack.append(c)
                po.append(c.val)
                c = c.left                
            c = stack.pop()
            c = c.right
        return po
            class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        def deleteBackSpace(X):
            stack = []
            for i in X:
                if not i=='#':
                    stack.append(i)
                elif(len(stack)==0):
                    continue
                else:
                    stack.pop()
            return stack
        return deleteBackSpace(S)==deleteBackSpace(T)# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        result = []
        
        def inorder(node):
            if node:
                if node.left!=None:
                    inorder(node.left)
                result.append(int(node.val))
                if node.right!=None:
                    inorder(node.right)
                    
        def constructBalancedTree(arr):
            if not arr:
                return None
            mid = len(arr)//2
            root = TreeNode(arr[mid])
            root.left = constructBalancedTree(arr[:mid])
            root.right = constructBalancedTree(arr[mid+1:])
            return root
        
        inorder(root)
        # result = [int(x.val) for x in result]
        return constructBalancedTree(result)class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(0, len(prices)-1):
            if(prices[i+1] > prices[i]):
                profit += prices[i+1] - prices[i]
        return profitimport math
class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        ans = m
        if not m==0:
            x = math.log2(m)
            x = int(x)+1
            x = 2**x
        else:
            return 0
        if(n>=x):
            return 0
        for i in range(m+1, n+1):
            ans = ans & i   
        return ansfrom collections import Counter
class Solution:
    def count(self, d1, d2):
        s = 0
        for i in 'abcdefghijklmnopqrstuvwxyz':
            s += d1[i] - d2[i]
            if s < 0:
                return False
        return True
    
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        d1 = Counter(s1)
        d2 = Counter(s2)
        return self.count(d1, d2) | self.count(d2, d1)class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height)-1
        maxarea = 0
        while(i!=j):
            a = (j-i)*(min(height[i], height[j]))
            if(a>maxarea):
                maxarea = a
            if(height[i]>height[j]):
                j -= 1
            else:
                i += 1
        return maxareaclass Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not len(nums) == len(set(nums))class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        dic = { 0:-1 }
        ps = 0
        max_length = 0
        for idx, number in enumerate(nums):
            if number:
                ps += 1
            else:
                ps -= 1
            if ps in dic:
                max_length = max(max_length, idx-dic[ps])
            else:
                dic[ps] = idx
        return max_length# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.c = 0
        def count(node):
            if node:
                if node.left:
                    count(node.left)
                if node.right:
                    count(node.right)
                self.c += 1
            return self.c
        
        count(root)
        return self.cclass Solution:
    def countBits(self, num: int) -> List[int]:
        ans = [0]
        offset = 1
        for i in range(1, num+1):
            if(offset*2 == i):
                offset = i
            ans.append(ans[i-offset]+1)
        return ansclass Solution:
    def countElements(self, arr: List[int]) -> int:
        s = set()
        s = set(arr)
        c = 0
        for i in range(len(arr)):
            if(arr[i]+1 in s):
                c += 1
        return cfrom collections import deque
class Solution:
    def canFinish(self, numCourses, prerequisites) -> bool:
        adjList = [[] for _ in range(numCourses)]
        inDegree = [0 for _ in range(numCourses)]
        queue = deque()
        visited = 0
        for i in range(len(prerequisites)):
            adjList[prerequisites[i][0]].append(prerequisites[i][1])
        for i in range(numCourses):
            for j in adjList[i]:
                inDegree[j] += 1
        for i in range(len(inDegree)):
            if inDegree[i] == 0:
                queue.append(i)
        while queue:
            el = queue.popleft()
            for i in adjList[el]:
                inDegree[i] -= 1
                if inDegree[i] == 0:
                    queue.append(i)
            visited += 1
        if visited == numCourses:
            return True
        else:
            return Falseclass Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        s = 0
        for col in zip(*A):
            if any(col[i] > col[i+1] for i in range(len(col)-1)):
                s += 1
        return sclass Solution:
    def deleteNode(self, root, key):
        if not root:
            return
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            else:
                temp = root.left
                while temp.right:
                    temp = temp.right
                root.val = temp.val
                root.left = self.deleteNode(root.left, temp.val)
        return root# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.nextclass MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.maxsize = k
        self.size = 0
        self.decq = [0]*k
        self.front = self.rear = -1

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if self.size == self.maxsize:
            return False
        else:
            if self.front == -1:
                self.front = self.rear = 0
            else:
                self.front = (self.front-1)%self.maxsize
            self.decq[self.front] = value
            self.size += 1
            return True

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if self.size == self.maxsize:
            return False
        else:
            if self.rear == -1:
                self.front = self.rear = 0
            else:
                self.rear = (self.rear+1)%self.maxsize
            self.decq[self.rear] = value
            self.size += 1
            return True

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.size == 0:
            return False
        else:
            if self.front == self.rear:
                self.front = self.rear = -1
            else:
                self.decq[self.front] = 0
                self.front = (self.front+1)%self.maxsize
            self.size -= 1
            return True                

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.size == 0:
            return False
        else:
            if self.front == self.rear:
                self.front = self.rear = -1
            else:
                self.decq[self.rear] = 0
                self.rear = (self.rear-1)%self.maxsize
            self.size -= 1
            return True       

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        return self.decq[self.front] if self.size != 0 else -1

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        return self.decq[self.rear] if self.size != 0 else -1

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return self.size == 0

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return self.size == self.maxsize

# ------------------------------------------

# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()
# ------------------------------------------

# Another Optimized Solution
class MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.decq = []
        self.maxsize = k

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if len(self.decq) < self.maxsize:
            self.decq.append(value)
            return True

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if len(self.decq) < self.maxsize:
            self.decq.insert(0, value)
            return True

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.decq:
            self.decq.pop()
            return True

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.decq:
            del self.decq[0]
            return True

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        return self.decq[-1] if self.decq else -1

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        return self.decq[0] if self.decq else -1

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return len(self.decq)==0

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return len(self.decq)==self.maxsize

# ------------------------------------------

# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()class MyCircularQueue:

    def __init__(self, k: int):
        self.size = 0
        self.maxsize = k
        self.cq = [0]*k   
        self.front = self.rear = -1

    def enQueue(self, value: int) -> bool:
        if self.size == self.maxsize:
            return False
        else:
            if self.rear == -1:
                self.rear = self.front = 0
            else:
                self.rear = (self.rear+1)%self.maxsize
            self.cq[self.rear] = value
            self.size += 1
            return True
        
    def deQueue(self) -> bool:
        if self.size == 0:
            return False
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front+1)%self.maxsize
        self.size -= 1
        return True

    def Front(self) -> int:
        return self.cq[self.front] if self.size!=0 else -1

    def Rear(self) -> int:
        return self.cq[self.rear] if self.size!=0 else -1

    def isEmpty(self) -> bool:
        return self.size == 0        

    def isFull(self) -> bool:
        return self.size == self.maxsize

# ------------------------------------------

# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        
        self.depth = 1
        def findDepth(first):
            if not first:
                return 0
            ld = findDepth(first.left)
            rd = findDepth(first.right)
            self.depth = max(self.depth, ld+rd+1)
            return max(ld,rd) + 1
        
        findDepth(root)
        return self.depth - 1class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        m = 5
        while (n/m >= 1):
            count += int(n/m)
            m *= 5
        return count        # 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 findBottomLeftValue(self, root: TreeNode) -> int:
        queue = deque([root])
        visited = set()
        while queue:
            size = len(queue)
            leftmost = math.inf
            for i in range(size):
                node = queue.popleft()
                if leftmost == math.inf:
                    leftmost = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if not queue:
                return leftmost
        return 0# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        tree = collections.defaultdict()
        tree.default_factory = tree.__len__
        c = collections.Counter()
        anslist = []
        def find(node):
            if node:
                tid = tree[node.val, find(node.left), find(node.right)]
                c[tid] += 1
                if c[tid] == 2:
                    anslist.append(node)
                return tid
        
        find(root)
        return anslistfrom collections import Counter
class Solution:
    def firstUniqChar(self, s: str) -> int:
        c = Counter(s)
        for i in range(len(s)):
            if c[s[i]] == 1:
                return i
        return -1class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        res = []
        for i in range(1, n+1):
            if i % 3 == 0 and i % 5 == 0:
                res.append("FizzBuzz")
            elif i % 3 == 0:
                res.append("Fizz")
            elif i % 5 == 0:
                res.append("Buzz")
            else:
                res.append(str(i))
        return resimport collections
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        word = collections.defaultdict(list)
        for s in strs:
            word[tuple(sorted(s))].append(s)
        return word.values()class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.s1 = []
        self.s2 = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.s1.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        while len(self.s1) > 1:
            self.s2.append(self.s1.pop())
        temp = self.s1.pop()
        while len(self.s2):
            self.s1.append(self.s2.pop())
        return temp

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.s1[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return False if len(self.s1) else True

# ------------------------------------------

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()## Implementation Using queue.Queue()
## Faster than 67%

from queue import Queue
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = Queue(maxsize=0)
        self.q2 = Queue(maxsize=0)

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q1.put(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        while(self.q1.qsize()>1):
            self.q2.put(self.q1.get())
        temp = self.q1.get()
        while(self.q2.qsize()>0):
            self.q1.put(self.q2.get())
        return temp

    def top(self) -> int:
        """
        Get the top element.
        """
        while(self.q1.qsize()>1):
            self.q2.put(self.q1.get())
        temp = self.q1.get()
        while(self.q2.qsize()>0):
            self.q1.put(self.q2.get())
        self.q1.put(temp)
        return temp

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.q1.empty()
# ------------------------------------------

## Implementation using Deque
## Faster than 100%

from collections import deque
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q.append(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q.pop()

    def top(self) -> int:
        """
        Get the top element.
        """
        temp = self.q.pop()
        self.q.append(temp)
        return temp

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return False if len(self.q) else True
# ------------------------------------------

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.maxSize = maxSize

    def push(self, x: int) -> None:
        if(len(self.stack) < self.maxSize):
            self.stack.append(x)

    def pop(self) -> int:
        if(len(self.stack)!=0):
            return self.stack.pop()
        else:
            return -1    

    def increment(self, k: int, val: int) -> None:
        for i in range(min(k, len(self.stack))):
            self.stack[i] += val        

# ------------------------------------------

# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)import math
class Solution:
    def integerReplacement(self, n: int) -> int:
        s = 0
        while(n!=1):
            if(n%2==0):
                n //= 2
                s += 1
                continue
            if(n==3):
                return s+2
            else:
                if(math.ceil(math.log2(n-1))==math.floor(math.log2(n-1))):
                    n -= 1
                elif((math.ceil(math.log2(n+1))==math.floor(math.log2(n+1))) or ((n+1)%4==0)):
                    n += 1
                else:
                    n -= 1
                s += 1
        return sclass Solution:
    def intToRoman(self, num: int) -> str:
        dic = { 1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I' }
        ans = ''
        for i in dic:
            while num>=i:
                ans += dic[i]
                num -= i
        return ansclass Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            i = 0
            while i < len(nums2):
                if nums2[i] in set(nums1):
                    nums1.remove(nums2[i])
                    i += 1 
                else:
                    nums2.remove(nums2[i])
            return nums2
        else:
            i = 0
            while i < len(nums1):
                if nums1[i] in set(nums2):
                    nums2.remove(nums1[i])
                    i += 1 
                else:
                    nums1.remove(nums1[i])
            return nums1
# ------------------------------------------

# Alternate Approach

from collections import Counter
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list((Counter(nums1)&Counter(nums2)).elements())# 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 invertTree(self, root: TreeNode) -> TreeNode:
        def invert(node):
            if node.left:
                invert(node.left)
            if node.right:
                invert(node.right)
            temp = node.left
            node.left = node.right
            node.right = temp
        if root:
            invert(root)
        return rootclass Solution: 
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        if len(t) == 0:
            return False
        sp = 0 
        for tc in t:
            if s[sp] == tc:
                sp += 1
                if sp == len(s):
                    return True 
        return Falseclass Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while(len(stones)!=1 and len(stones)!=0):
            stones = sorted(stones)
            t = abs(stones[-1]-stones[-2])
            if(t!=0):
                stones.pop()
                stones[-1] = t
            else:
                stones.pop()
                stones.pop()
        if(stones):
            return stones[0]
        return 0class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        denom = {
            5: 0,
            10: 0,
            20: 0
        }
        for i in range(len(bills)):
            denom[bills[i]] += 1
            if bills[i] > 5:
                bal = bills[i] - 5
                if bal % 5 == 0 and bal % 10 != 0:
                    if denom[5] > 0:
                        denom[5] -= 1
                        bal -= 5
                        if bal == 0:
                            continue
                if bal % 10 == 0 and bal % 20 != 0:
                    if denom[10] > 0:
                        denom[10] -= 1
                        bal -= 10
                        if bal == 0:
                            continue                
                if denom[5] > 1:
                    denom[5] -= 2
                    bal -= 10
                    if bal == 0:
                        continue
                if bal > 0:
                    return False
        return Trueclass Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        x = 0
        for i in zip(*strs):
            r = all(a == i[0] for a in i)
            if r:
                x += 1
            else:
                break
        return strs[0][0:x] if x else ''class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A = sorted(A)
        for i in range(len(A)):
            if A[i] < 0:
                A[i] = -A[i]
                K -= 1
            elif A[i] >= 0:
                if K % 2 == 0:
                    break
                else:
                    A[A.index(min(A))] = -A[A.index(min(A))]
                    break
            if K == 0:
                break
        return sum(A)          # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = l3 = ListNode(0)
        while l1 and l2:
            if l1.val > l2.val:
                l3.next = ListNode(l2.val)
                l3 = l3.next
                l2 = l2.next
            else:
                l3.next = ListNode(l1.val)
                l3 = l3.next
                l1 = l1.next
        while l1:
            l3.next = ListNode(l1.val)
            l3 = l3.next
            l1 = l1.next
        while l2:
            l3.next = ListNode(l2.val)
            l3 = l3.next
            l2 = l2.next
        return dummy.next
# ------------------------------------------

# Slightly More Optimized
# ------------------------------------------

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l3 = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                l3.next = ListNode(l1.val)
                l1 = l1.next
                l3 = l3.next
            else:
                l3.next = ListNode(l2.val)
                l2 = l2.next
                l3 = l3.next
        l3.next = l1 or l2
        return head.next# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A)//2]
# ------------------------------------------

# Solution using Slow and Fast Pointers

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slowPointer = head
        fastPointer = head
        
        while(fastPointer and fastPointer.next):
            
            slowPointer = slowPointer.next
            fastPointer = fastPointer.next.next
            
        return slowPointer        import math
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = math.inf

    def push(self, x: int) -> None:
        self.x = x
        self.stack.append(x)
        if(x < self.min):
            self.min = x               
            
    def pop(self) -> None:
        t = self.stack.pop()
        if(t==self.min and len(self.stack)):
            self.min = min(self.stack)   
        elif(t==self.min and not len(self.stack)):
            self.min = math.inf

    def top(self) -> int:
        return self.stack[-1]        

    def getMin(self) -> int:
        return self.min     
# ------------------------------------------

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums = sorted(nums)[::-1]
        x = sum(nums)
        s = 0
        if len(nums) == 1:
            return nums
        for i in range(len(nums)+1):
            s += nums[i]
            if s > x-s:
                return nums[0:i+1]class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        inc = True
        dec = True
        for i in range(0, len(A)-1):
            if(A[i] > A[i+1]):
                inc = False
            if(A[i] < A[i+1]):
                dec = False
        return inc or dec
            class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        t = nums.count(0)
        nzpos = 0
        if(t==0):
            return nums
        for i in range(0, len(nums)):
            if(nums[i]!=0):
                nums[nzpos] = nums[i]
                nzpos = nzpos+1
        for i in range(len(nums)-t, len(nums)):
            nums[i] = 0             from collections import deque
class Solution:
    def numIslands(self, grid) -> int:
        if not grid:
            return 0
        r = len(grid)
        c = len(grid[0])
        queue = deque()
        islands = 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == '1':
                    islands += 1
                    grid[i][j] = '0'
                    queue.append([i, j])
                    while queue:
                        el = queue.popleft()
                        rs = el[0]
                        cs = el[1]
                        if rs - 1 >= 0 and grid[rs-1][cs] == '1':
                            queue.append([rs-1, cs])
                            grid[rs-1][cs] = '0'
                        if rs + 1 < r and grid[rs+1][cs] == '1':
                            queue.append([rs+1, cs])
                            grid[rs+1][cs] = '0'
                        if cs - 1 >= 0 and grid[rs][cs-1] == '1':
                            queue.append([rs, cs-1])
                            grid[rs][cs-1] = '0'
                        if cs + 1 < c and grid[rs][cs+1] == '1':
                            queue.append([rs, cs+1])
                            grid[rs][cs+1] = '0'
        return islandsclass RecentCounter:
    def __init__(self):
        self.q = collections.deque()
    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q[0] < t-3000:
            self.q.popleft()
        return len(self.q)class Solution:
    def hammingWeight(self, n: int) -> int:
        return (bin(n).count('1'))# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution1:
    def isPalindrome(self, head: ListNode) -> bool:
        temp = head
        stack = []
        l = 0
        while temp:
            l += 1
            temp = temp.next
        temp = head
        for i in range(0, l//2):
            stack.append(temp.val)
            temp = temp.next
        if l % 2 != 0:
            temp = temp.next
        for i in range(0, l//2):
            if temp.val == stack.pop():
                continue
            return False
        return True
# ------------------------------------------

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution2:
    def isPalindrome(self, head: ListNode) -> bool:
        el = []
        while head:
            el.append(head.val)
            head = head.next
        for i in range(0, len(el)//2):
            if not el[i] == el[-i-1]:
                return False
        return Trueclass Solution:
    def isPalindrome(self, x: int) -> bool:
        a = []
        x = str(x)
        x = list(x)
        a = x[::-1]
        if (str(a)==str(x)):
            return True
        else:
            return False"""
This first solution uses the interval splitting method
This is achieved by using a dp table.
Time Complexity: O(n^1.5)
"""
class Solution1:
    def numSquares(self, n) -> int:
        if n <= 3:
            return n
        dp = [0 for _ in range(n+1)]
        dp[1], dp[2], dp[3] = 1, 2, 3
        for i in range(4, len(dp)):
            dp[i] = i
            j = 1
            while j*j <= i:
                dp[i] = min(dp[i], 1 + dp[i - j*j])
                j += 1
        return dp[-1]

"""
Lagrange's 4 square and 3 square theorem

Theorem: Every natural number can be represented as the sum of 4 integer squares.
N = a^2 + b^2 + c^2 + d^2

Theorem: A natural number can be represented as sum of 3 squares of integers.
N = a^2 + b^2 + c^2

if and only if the N is not of the form,

N = 4^a (8b + 7) -- (1)

LOGIC: 
- if N is a perfect square, return 1
- if N is of form (1),
    - keep dividing by 4
    - divide by 8
        - if rem == 7:
            return 4
- check if N can be split into two perfect squares. If yes, return 2
- if all fails, return 3
"""

class Solution:
    def numSquares(self, n: int) -> int:
        if ceil(sqrt(n)) == floor(sqrt(n)):
            return 1
        
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4
        
        j = 1
        while j*j <= n:
            if ceil(sqrt(n - j*j)) == floor(sqrt(n - j*j)):
                return 2
            j += 1
        
        else:
            return 3class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        amount = 0
        for i in range(len(shift)):
            if(shift[i][0]==0):
                amount += (-1)*shift[i][1]
            else:
                amount += 1*shift[i][1]
        print(amount)
        if amount == 0:
            return s
        elif amount < 0:
            return s[(abs(amount)%len(s)):] + s[0:(abs(amount)%len(s))]
        else:
            return s[len(s)-(amount%len(s)):] + s[0:len(s)-(amount%len(s))]class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 0
        for i in range(len(digits)-1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                break
            else:
                digits[i] = 0
                if i == 0:
                    digits.insert(0, 1)
        return digitsclass Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n < 1:
            return False
        if n == 1:
            return True
        if sum(list(map(int, str(n)))) % 3 != 0:
            return False
        else:
            while n > 1:
                if n % 3 == 0:
                    n /= 3
                else:
                    return False
        if n != 1:
            return False
        else:
            return True
# ------------------------------------------

# Alternate Approach
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n < 1:
            return False
        else:
            return 1162261467 % n == 0# Classic Solution
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True
        if n == 0:
            return False
        while n % 2 == 0:
            n = n / 2
        if n == 1:
            return True
        else:
            return False
# ------------------------------------------

# Solution Using Bit Manipulation
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and bin(n).count('1') == 1class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        rec = []
        for p in people:
            rec.insert(p[1], p)
        return recfrom random import choices
class Solution:

    def __init__(self, w: List[int]):
        self.w = w

    def pickIndex(self) -> int:
        return choices(range(len(self.w)), self.w)[0]
# ------------------------------------------

# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        p = 0
        while p < len(nums)-1:
            if nums[p] == nums[p+1]:
                nums.pop(p+1)
                continue
            p += 1
        return len(nums)# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        pointer = ListNode(0)
        pointer.next = head
        
        tempnode = pointer
        while tempnode.next != None:
            if tempnode.next.val == val:
                tempnode.next = tempnode.next.next
            else:
                tempnode = tempnode.next
        return pointer.next# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        tail = head
        length = 1
        while tail.next:
            length += 1
            tail = tail.next
        if(length==1):
            return None
        if(length==n):
            return head.next
        tempnode = head
        for _ in range(0, length-n-1):
            tempnode = tempnode.next
        tempnode.next = tempnode.next.next
        return head
# ------------------------------------------

# One Pass
# ------------------------------------------

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = fast = slow = ListNode()
        dummy.next = head
        if not head.next:
            return None 
        for _ in range(n+1):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.nextclass Solution:
    def reorganizeString(self, S: str) -> str:
        l = len(S)
        A = []
        for k, v in sorted((S.count(x), x) for x in set(S)):
            if k > (l+1) / 2 : 
                return ""
            A.extend(k * v)
        # print(A)
        ans = [None] * l
        ans[::2], ans[1::2] = A[(l//2) : ], A[: (l//2)]
        return ''.join(ans)class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        dic = {}
        ans = []
        for i in range(0, len(s)-9):
            if s[i:i+10] not in dic:
                dic[s[i:i+10]] = 1
            else:
                dic[s[i:i+10]] += 1
        for k, v in dic.items():
            if v>1:
                ans.append(k)
        return ansclass Solution:
    def reverseBits(self, n: int) -> int:
        s = str(bin(n))
        s = s[2:]
        s = '0'*(32-len(s)) + s
        s = int(s[::-1], 2)
        return sclass Solution:
    def reverse(self, x: int) -> int:
        x = str(x)
        if (x[0] == '-'):
            a = x[1:2147483648:1]
            a = a[::-1]
            if (int(a)>2147483648):
                return 0
            return int("-"+a)
        else:
            a = x[::-1]
            if (int(a)>2147483647):
                return 0
            return int(a)# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        temp = head
        prev = None
        
        while(temp!=None):
            next = temp.next
            temp.next = prev
            prev = temp
            temp = next            
        return prevclass Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        head = 0
        temp = ''
        tail = len(s) - 1
        while head < tail:
            temp = s[head]
            s[head] = s[tail]
            s[tail] = temp
            head += 1
            tail -= 1class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []
        s = list(s)
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
                continue
            if s[i] == ')':
                idx = stack.pop()
                s[idx+1 : i] = s[idx+1 : i][::-1]
        ans = ""
        for i in s:
            if i=="(" or i==")":
                continue
            ans += i
        return ansclass Solution:
    def romanToInt(self, s: str) -> int:
        ans = 0
        prev = ''
        for i in range(len(s)):
            if(s[i]=='M'):
                if(prev=='C'):
                    ans += 800
                    prev = 'M'
                    continue
                ans += 1000
                prev = 'M'
                continue
            if(s[i]=='D'):
                if(prev=='C'):
                    ans += 300
                    prev = 'D'
                    continue
                ans += 500
                prev = 'D'
                continue
            if(s[i]=='C'):
                if(prev=='X'):
                    ans += 80
                    prev = 'C'
                    continue
                ans += 100
                prev = 'C'
                continue
            if(s[i]=='L'):
                if(prev=='X'):
                    ans += 30
                    prev = 'L'
                    continue
                ans += 50
                prev = 'L'
                continue
            if(s[i]=='X'):
                if(prev=='I'):
                    ans += 8
                    prev = 'X'
                    continue
                ans += 10
                prev = 'X'
                continue
            if(s[i]=='V'):
                if(prev=='I'):
                    ans += 3
                    prev = 'V'
                    continue
                ans += 5
                prev = 'V'
                continue
            if(s[i]=='I'):                                   
                ans += 1
                prev = 'I'
        return ansclass Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        x = len(nums)
        A = [0]*x
        for i in range(0, x):
            A[(i+k)%x] = nums[i]
        for i in range(0, x):
            nums[i] = A[i]class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for x in zip(*matrix):
            matrix.pop(0)
            matrix.append(x[::-1])# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        if not k==0:        
            tail = head
            length = 1

            while(tail.next):
                length += 1
                tail = tail.next

            k = k % length

            tail.next = head

            tempnode = head

            for _ in range(0, length-k-1):
                tempnode = tempnode.next
            a = tempnode.next
            tempnode.next = None
            return a
        return headclass Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binary(nums, low, high, target):
            if low <= high:
                mid = low + (high - low) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    return binary(nums, low, mid-1, target)
                else:
                    return binary(nums, mid+1, high, target)
            else:
                return high+1
        return binary(nums, 0, len(nums)-1, target)
# ------------------------------------------

# Iterative Binary Search 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        else:
            return high + 1class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        shuf = self.nums.copy()
        self.shuf = shuf

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        self.shuf = self.nums.copy()
        return self.shuf

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        x = len(self.nums)
        for i in range(x):
            j = random.randrange(i, x)
            self.shuf[i], self.shuf[j] = self.shuf[j], self.shuf[i]
        return self.shuf
# ------------------------------------------

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()# from collections import deque

class Solution:
    def simplifyPath(self, path: str) -> str:
        if(len(path)==0 or path==None or path==''):
            return '/'
        
        p = path.split('/')
        stack = []
        for item in p:
            if (item=='..'):
                if(stack):
                    stack.pop()
                continue
            if item=='.' or len(item)==0:
                pass
            else:
                stack.append(item)
        return '/'+'/'.join(stack)
    
                class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return int(((sum(set(nums))*3) - sum(nums))/2)class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        ans = []
        for i in set(nums):
            if nums.count(i)==1:
                ans.append(i)
                if(len(ans)==2):
                    return ans
        return ansfrom collections import Counter
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = Counter(nums)
        nums.clear()
        for v in range(3):
            for i in range(n[v]):
                nums.append(v)class Solution:
    def balancedStringSplit(self, s: str) -> int:
        c = 0
        rc = 0
        lc = 0
        for i in range(len(s)):
            if s[i] == 'R':
                rc += 1
            if s[i] == 'L':
                lc += 1
            if rc == lc:
                c += 1
                rc = 0
                lc = 0
        return cclass Solution:
    def myAtoi(self, str: str) -> int:
        if len(str)==0:
            return 0
        str = list(str.strip())
        if len(str)==0:
            return 0
        if(str[0]=='-'):
            s = -1
        else:
            s = 1
        if str[0] in ['-', '+']:
            del str[0]
        i = 0
        exp = 0
        while(i < len(str) and str[i].isdigit()):
            exp = exp*10 + ord(str[i]) - ord('0')
            i += 1
        return max(-2**31, min(exp*s, 2**31-1))class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        tasksDict = collections.Counter(tasks)
        heap = []
        c = 0
        for k, v in tasksDict.items():
            heappush(heap, (-v,k))
        while heap:
            i = 0
            stack = []
            while i<=n:
                if len(heap)>0:
                    index, task = heappop(heap)
                    if index!=-1:
                        stack.append((index+1, task))
                c += 1
                if len(heap)==0 and len(stack)==0:
                    break
                i += 1
            for i in stack:
                heappush(heap, i)
        return c## Naive Solution that runs in O(n^2)
## Traverses the array, and finds the maximum left or right element.
## rainwater that can be stored in the column =  min(left, right) - height[i]
class NaiveSolution:
    def trap(self, height) -> int:
        res = 0
        n = len(height)
        for i in range(1, n-1):
            left = height[i]
            for j in range(i):
                left = max(left, height[j])
            right = height[i]
            for j in range(i+1, n):
                right = max(right, height[j])
            res += min(left, right) - height[i]
        return res
# ------------------------------------------

## Optimized solution that runs in O(N)
## Stores the left and right maximum values in two dp arrays.
## Space Complexity - O(N)

class Solution:
    def trap(self, height: List[int]) -> int:
        if height == []:
            return 0
        n = len(height)
        res = 0
        left = [0 for _ in range(n)]
        right = [0 for _ in range(n)]
        left[0] = height[0]
        right[n-1] = height[n-1]
        for i in range(1, n):
            left[i] = max(left[i-1], height[i])
        for i in range(n-2, -1, -1):
            right[i] = max(right[i+1], height[i])
        for i in range(n):
            res += min(left[i], right[i]) - height[i]
        return res    class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [0 for _ in range(len(triangle)+1)]
        for r in triangle[::-1]:
            for i in range(len(r)):
                dp[i] = r[i] + min(dp[i], dp[i+1])      
        return dp[0]class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs = sorted(costs, key = lambda x: x[0] - x[1])
        return sum(i[0] for i in costs[0:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:len(costs)])class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        if obstacleGrid[0][0] == 1:
            return 0
        
        obstacleGrid[0][0] = 1
        for i in range(1, m):
            obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)
        for i in range(1, n):
            obstacleGrid[0][i] = int(obstacleGrid[0][i] == 0 and obstacleGrid[0][i-1] == 1)
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:                    
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0
                    
        return obstacleGrid[-1][-1]            from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(a for a in s if a.isalnum()).lower()
        return s == s[::-1]class Solution:
    def checkValidString(self, s: str) -> bool:
        lb = 0
        rb = 0
        for i in s:
            if(i=='(' or i=='*'):
                lb += 1
            else:
                lb -= 1
            if lb < 0:
                return False
        if(lb==0):
            return True
        
        for i in range(len(s)-1, -1, -1):
            if(s[i]==')' or s[i]=='*'):
                rb += 1
            else:
                rb -= 1
            if rb < 0:
                return False
        return Trueclass Solution(object):
    def robotSim(self, commands, obstacles):
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        x = y = di = 0
        obstacleSet = set(map(tuple, obstacles))
        ans = 0

        for cmd in commands:
            if cmd == -2:  #left
                di = (di - 1) % 4
            elif cmd == -1:  #right
                di = (di + 1) % 4
            else:
                for k in range(cmd):
                    if (x+dx[di], y+dy[di]) not in obstacleSet:
                        x += dx[di]
                        y += dy[di]
                        ans = max(ans, x*x + y*y)

# ------------------------------------------


# Solution for https://leetcode.com/problems/two-sum/
# Language : Python3
# ------------------------------------------

# O(n^2) Solution
class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if(nums[i]+nums[j]==target):
                    return i, j


# O(n) Solution
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = { v:k for k, v in enumerate(nums) }
        for i in range(len(nums)):
            if target - nums[i] in dict and nums.index(target - nums[i]) != i:
                return i, nums.index(target-nums[i])
# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# -------------------------------------------
```