These are some cool solutions to leetcode problems

    217. Contains Duplicate

                                    from typing import List
                                    class Solution:
    
                                        def containsDuplicate(self, nums: List[int]) -> bool:
                                            new_set = set();
                                            for i in range(0, len(nums)):
                                                if nums[i] not in new_set:
                                                    new_set.add(nums[i])
                                                else:
                                                    return True;
                                            return False;
                                
    242. Valid Anagram
                                    class Solution:
                                    def isAnagram(self, s: str, t: str) -> bool:
                                        hash_table = {}
                                        for ch in s:
                                            if ch not in hash_table:
                                                hash_table[ch] = 1
                                            else:
                                                hash_table[ch] = hash_table[ch] + 1
    
                                        for ch in t:
                                            if ch not in hash_table:
                                                return False
                                            else:
                                                hash_table[ch] = hash_table[ch] - 1
    
                                        for code in range(ord('a'), ord('z') + 1):
                                            if chr(code) in hash_table and hash_table[chr(code)] != 0:
                                                return False
                                        return True
                                
    1. Two Sum
                                    from typing import List
                                    class Solution:
                                        def twoSum(self, nums: List[int], target: int) -> List[int]:
                                            hash_table = {}
                                            for i in range(0, len(nums)):
                                                remainder = target - nums[i]
                                                if remainder in hash_table.keys():
                                                    return [hash_table[remainder], i]
                                                hash_table[nums[i]] = i
                                            return []
                                
    49. Group Anagrams
                                        from typing import List
                                        class Solution:
                                            def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
                                                hash_table = {}
                                                for string in strs:
                                                    sorted_str = str(sorted(string))
                                                    if sorted_str not in hash_table.keys():
                                                        hash_table[sorted_str] = [string]
                                                    else:
                                                        hash_table[sorted_str].append(string)
    
                                                sol = []
    
                                                for key in hash_table.keys():
                                                    sol.append(hash_table[key])
    
                                                return sol 
                                    
    347. Top K Frequent Elements
                                        import heapq
                                        from typing import List
    
                                        class Solution:
                                            def topKFrequent(self, nums: List[int], k: int) -> List[int]:
                                                hash_table = {}
                                                for x in nums:
                                                    if x not in hash_table:
                                                        hash_table[x] = 1
                                                    else:
                                                        hash_table[x] = hash_table[x] + 1
                                                pq = []
    
                                                for key in hash_table.keys():
                                                    heapq.heappush(pq, (hash_table[key], key))
    
                                                sol = []
    
                                                for x in heapq.nlargest(iterable=pq, n=k):
                                                    sol.append(x[1])
                                                return sol
                                    
    Better approach (Bucket Sort)
                                        from typing import List
                                        class Solution:
                                            def topKFrequent(self, nums: List[int], k: int) -> List[int]:
                                                hash_table = {}
                                                for i in range(0, len(nums)):
                                                    if nums[i] not in hash_table:
                                                        hash_table[nums[i]] = 1
                                                    else:
                                                        hash_table[nums[i]] = hash_table[nums[i]] + 1
                                        
                                                count = [[] for i in range(0, len(nums) + 1)]
                                        
                                                for key, val in hash_table.items():
                                                    count[val].append(key)
                                        
                                                sol = []
                                        
                                                for i in range(len(count) - 1, 0, -1):
                                                    for x in count[i]:
                                                        sol.append(x)
                                                        if len(sol) == k:
                                                            return sol                                    
                                    
    String Encode and Decode
                                        from typing import List
                                        class Solution:
    
                                            def encode(self, strs: List[str]) -> str:
                                                encoded_string = ""
                                                for string in strs:
                                                    encoded_string += str(len(string)) + "#" + string
                                                return encoded_string
    
                                            def decode(self, s: str) -> List[str]:
                                                sol = []
                                                i = 0
                                                while i < len(s):
                                                    j = i
                                                    while s[j] != '#':
                                                        j += 1
    
                                                    length = int(s[i:j])
    
                                                    sol.append(s[j + 1 : j + 1 + length])
    
                                                    i = j + 1 + length
                                                    
                                                return sol
                                    
    238. Product of Array Except Self
                                        from typing import List
                                        class Solution:
                                            def productExceptSelf(self, nums: List[int]) -> List[int]:
                                                sol = []
                                                lt = []
                                                rt = []
                                                for i in range(0, len(nums)):
                                                    if i == 0:
                                                        lt.append(nums[i])
                                                    else:
                                                        lt.append(lt[i - 1] * nums[i])
    
                                                for i in range(len(nums) - 1, -1, -1):
                                                    if i == len(nums) - 1:
                                                        rt.append(nums[i])
                                                    else:
                                                        rt.append(rt[len(rt) - 1] * nums[i])
    
                                                rt.reverse()
    
                                                for i in range(0, len(nums)):
                                                    if i == 0:
                                                        sol.append(rt[i + 1])
                                                    elif i == len(nums) - 1:
                                                        sol.append(lt[i - 1])
                                                    else:
                                                        sol.append(lt[i - 1] * rt[i + 1])
    
                                                return sol
    
                                    
    36. Valid Sudoku
                                        from typing import List
                                        class Solution:
                                            def isValidSudoku(self, board: List[List[str]]) -> bool:
                                                
                                                for i in range(0, 9):
                                                    sodoku_set = set()
                                                    for j in range(0, 9):
                                                        if board[i][j] in sodoku_set:
                                                            return False
                                                        elif board[i][j] != ".":
                                                            print(board[i][j])
                                                            sodoku_set.add(board[i][j])
    
                                                for j in range(0, 9):
                                                    sudoku_set = set()
                                                    for i in range(0, 9):
                                                        if board[i][j] in sudoku_set:
                                                            return False
                                                        elif board[i][j] != ".":
                                                            sudoku_set.add(board[i][j])
    
                                                ist = 0
                                                jst = 0
    
                                                while True:
                                                    sudoku_set = set()
    
                                                    for i in range(ist, ist + 3):
                                                        for j in range(jst, jst + 3):
                                                            if board[i][j] in sudoku_set:
                                                                return False
                                                            elif board[i][j] != ".":
                                                                sudoku_set.add(board[i][j])
    
                                                    jst += 3
    
                                                    if jst == 9:
                                                        jst = 0 
                                                        ist += 3
    
                                                    if ist == 9:
                                                        break
    
                                                return True
                                    
    128. Longest Consecutive Sequence
                                        from typing import List
                                        class Solution:
                                            def longestConsecutive(self, nums: List[int]) -> int:
                                                if len(nums) == 0:
                                                    return 0
    
                                                nums.sort()
                                                longest = 1
                                                current = 1
                                                for i in range(1, len(nums)):
                                                    if nums[i] ==  nums[i - 1] + 1:
                                                        current += 1
                                                    elif nums[i] > nums[i - 1] + 1:
                                                        current = 1
                                                    if longest < current:
                                                        longest = current
    
                                                return longest
                                    
    Better approach (Using Set())
                                        from typing import List
                                        class Solution:
                                            def longestConsecutive(self, nums: List[int]) -> int:
                                                nSet = set(nums)
                                                longest = 0
                                                current = 0
                                                for x in nums:
                                                    if (x - 1) not in nSet:
                                                        current = 1
                                                        while (x + current) in nSet:
                                                            current += 1
                                                        if longest < current:
                                                            longest = current 
    
                                                return longest
                                    
    20. Valid Parentheses
                                        class Solution:
                                        def isValid(self, s: str) -> bool:
                                            st = []
                                            for ch in s:  
                                                top = st[len(st) - 1] if len(st) > 0 else -1
                                                if  ch == '(' or ch == '[' or  ch == '{':
                                                    st.append(ch)
                                                elif ch == ')' and top == '(' or ch == ']' and top == '[' or ch == '}' and top == '{':
                                                    st.pop()
                                                else:
                                                    return False
    
                                            if len(st) != 0:
                                                return False
                                            return True
    
                                    
    155. Min Stack
                                        class MinStack:
    
                                        def __init__(self):
                                            self.st = []
    
                                        def push(self, val: int) -> None:
                                            self.st.append(val)
    
                                        def pop(self) -> None:
                                            self.st.pop()
    
                                        def top(self) -> int:
                                            return  self.st[-1] 
    
                                        def getMin(self) -> int:
                                            minim = self.st[-1]
                                            for x in self.st:
                                                if minim > x:
                                                    minim = x
                                            return minim
                                    
    Better approach (Two Stacks)
                                        class MinStack:
    
                                        def __init__(self):
                                            self.st = []
                                            self.min_stack = []
    
                                        def push(self, val: int) -> None:
                                            self.min_stack.append(min(val, self.min_stack[-1] if len(self.min_stack) > 0 else val))
                                            self.st.append(val)
    
                                        def pop(self) -> None:
                                            self.st.pop()
                                            self.min_stack.pop()
    
    
                                        def top(self) -> int:
                                            return  self.st[-1] 
    
                                        def getMin(self) -> int:
                                            return self.min_stack[-1]
                                    
    150. Evaluate Reverse Polish Notation
                                        from typing import List
                                        class Solution:
                                            def evalRPN(self, tokens: List[str]) -> int:
                                                operators = {'+', '-', '*', '/'}
                                                st = []
    
                                                for t in tokens:
                                                    if t in operators:
                                                        s_item = int(st.pop())
                                                        f_item = int(st.pop())
                                                        if t == '+':
                                                            res = f_item + s_item
                                                        elif t == '-':
                                                            res = f_item - s_item
                                                        elif t == '*':
                                                            res = f_item * s_item
                                                        else:
                                                            res = int(f_item / s_item)
                                                        st.append(res)
                                                    else:
                                                        st.append(t)
    
                                                return int(st.pop())
                                    
    22. Generate Parentheses
                                        from typing import List
                                        class Solution:
                                            def __init__(self):
                                                self.sol = []
                                        
                                            def isValid(self, s : List[str]) -> bool:
                                                st = []
                                                for p in s:
                                                    if p == '(':
                                                        st.append(p)
                                                    elif p == ')':
                                                        top = 0 if len(st) == 0 else st[-1]
                                                        if top == '(':
                                                            st.pop()
                                                        else:
                                                            return False
                                                if len(st) > 0:
                                                    return False
                                               
                                                return True
                                        
                                            def bkt(self, n : int, s: List[str], index : int) -> None:
                                                par = {'(', ')'}
                                                for p in par:
                                                    s[index] = p 
                                                    if index == (2 * n - 1) and self.isValid(s) == True:
                                                        self.sol.append(''.join(s))
                                                    elif index < (2 * n - 1):
                                                        self.bkt(n, s, index + 1)
                                        
                                            def generateParenthesis(self, n: int) -> List[str]:
                                                s = [0] * 2 * n 
                                                self.bkt(n, s, 0)
                                                return self.sol 
                                        
                                    
    Better approach
                                        from typing import List
    
                                        class Solution:
    
                                            def __init__(self):
                                                self.stack = []
                                                self.sol = []
    
                                            def bkt(self, openP: int, closeP: int, n: int) -> None:
                                                if openP == closeP == n:
                                                    self.sol.append(''.join(self.stack))
                                                    return None
    
                                                if openP < n:
                                                    self.stack.append("(")
                                                    self.bkt(openP=openP + 1, closeP=closeP, n=n)
                                                    self.stack.pop()
    
                                                if closeP < openP:
                                                    self.stack.append(")")
                                                    self.bkt(openP=openP, closeP=closeP + 1, n=n)
                                                    self.stack.pop()
    
                                            def generateParenthesis(self, n: int) -> List[str]:
                                                self.bkt(openP=0, closeP=0, n=n)
                                                return self.sol
                                    
    739. Daily Temperatures
                                        from typing import List
                                        class Solution:
                                            def dailyTemperatures(self, temp: List[int]) -> List[int]:
                                                ans = [0] * len(temp)
                                                st = []
    
                                                for i in range(0, len(temp)):
                                                    while len(st) > 0 and temp[st[-1]] < temp[i]:
                                                        ans[st[-1]] = i - st[-1]
                                                        st.pop()
    
                                                    st.append(i)
    
                                                return ans
                                    
    853. Car Fleet
                                        from typing import List
    
                                        class Solution:
                                            def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
                                                pair = [[p, s] for p, s in zip(position, speed)]
                                                st = []
    
    
                                                for p, s in sorted(pair)[::-1]:
                                                    st.append((target - p) / s)
                                                    if len(st) >= 2 and st[-1] <= st[-2]:
                                                        st.pop()
    
                                                return len(st)
    
                                    
    84. Largest Rectangle in Histogram
                                        from typing import List
    
                                        class Solution:
                                            def largestRectangleArea(self, heights: List[int]) -> int:
                                                maxArea = 0
                                                st = []
    
                                                for i, h in enumerate(heights):
                                                    start = i 
                                                    while len(st) > 0 and st[-1][1] > h:
                                                        index , height = st.pop()
                                                        maxArea = max(maxArea, height * (i - index))
                                                        start = index
    
                                                    st.append((start, h))
    
                                                for i, h in st:
                                                    maxArea = max(maxArea, h * (len(heights) - i))
    
                                                return maxArea
    
                                    
    125. Valid Palindrome
                                        class Solution:
                                        def isPalindrome(self, s: str) -> bool:
                                            new_s = ""
                                            for c in s:
                                                c = c.lower()
                                                if c >= 'a' and c <= 'z' or c >= '0' and c <= '9':
                                                    new_s += c 
    
    
                                            i = 0 
                                            j = len(new_s) - 1
                                            while i < j :
                                                if new_s[i] != new_s[j]:
                                                    return False
    
                                                i += 1
                                                j -= 1
    
                                            return True 
                                    
    167. Two Sum II - Input Array Is Sorted
                                        from typing import List
                                        class Solution:
                                            def twoSum(self, numbers: List[int], target: int) -> List[int]:
                                                i = 0
                                                j = len(numbers) - 1
    
                                                while i < j:
                                                    s = numbers[i] + numbers[j]
                                                    if s == target:
                                                        return [i + 1, j + 1]
    
                                                    elif s < target:
                                                        i += 1
                                                    else:
                                                        j -= 1
    
                                                return []
                                    
    15. 3Sum
                                        from typing import List
    
                                        class Solution:
                                            def __init__(self):
                                                self.sol = []
    
                                            def twoSum(self, nums: List[int], target: int, k: int,i : int, j: int ) -> List[int]:
                                                while i < j:
                                                    s = nums[i] + nums[j]
                                                    if s < target or i == k:
                                                        i += 1
                                                    elif s > target or j == k:
                                                        j -= 1
                                                    else:
                                                        cand = [nums[i], nums[j], nums[k]]
                                                        self.sol.append(cand)
                                                        i += 1
                                                        while nums[i] == nums[i - 1] and i < j:
                                                            i += 1
    
                                                return []
    
                                            def threeSum(self, nums: List[int]) -> List[List[int]]:
                                                nums.sort()
    
                                                for k in range(0, len(nums) - 2):
                                                    if k > 0 and nums[k] == nums[k - 1]:
                                                        continue
                                                    print(nums[k])
                                                    self.twoSum(nums,(nums[k] * -1), k,  k + 1,len(nums) - 1)
    
                                                return self.sol
                                    
    11. Container With Most Water
                                        from typing import List
                                        class Solution:
                                            def maxArea(self, height: List[int]) -> int:
                                                max_area = -1
                                                i = 0
                                                j = len(height) - 1
                                                while i < j :
                                                    c_area = min(height[i], height[j]) * (j - i)
                                                    if c_area > max_area or max_area == -1:
                                                        max_area = c_area
    
                                                    if height[i] < height[j]:
                                                        i += 1
                                                    else:
                                                        j -= 1
    
                                                return max_area
    
                                    
    42. Trapping Rain Water
                                        from typing import List
                                        class Solution:
                                            def trap(self, h: List[int]) -> int:
                                                diff = [0] * len(h)
                                                maxim = 0
    
                                                for i in range(0, len(h)):
                                                    if maxim < h[i]:
                                                        maxim = h[i]
                                                        diff[i] = 0
                                                    else:
                                                        diff[i] = maxim - h[i]
    
                                                w = 0
                                                maxim = 0
    
                                                for i in range(len(h) - 1, -1, -1):
                                                    if maxim < h[i]:
                                                        maxim = h[i]
                                                    else:
                                                        diff[i] = min(diff[i], maxim - h[i])
                                                        w += diff[i]
    
                                                return w
                                    
    Better approach (Two Pointers)
                                        from typing import List
                                        class Solution:
                                            def trap(self, h: List[int]) -> int:
                                                i = 0
                                                j = len(h) - 1
                                                w = 0
                                                maxL = 0
                                                maxR = 0
    
                                                while i < j:
                                                    if maxL < h[i]:
                                                        maxL = h[i]
    
                                                    if maxR < h[j]:
                                                        maxR = h[j]
    
                                                    maxMin = min(maxL, maxR)
    
                                                    if maxMin > h[i]:
                                                        w += maxMin - h[i]
    
                                                    if maxMin > h[j]:
                                                        w += maxMin - h[j]
    
                                                    if maxL < maxR:
                                                        i += 1
                                                    else:
                                                        j -= 1
    
                                                return w
    
                                    
    121. Best Time to Buy and Sell Stock
                                        from typing import List
    
                                        class Solution:
                                            def maxProfit(self, p: List[int]) -> int:
                                                i = 0
                                                j = 1
                                                max_profit = 0
    
                                                while j < len(p):
                                                    while p[j] >= p[i]: 
                                                        if max_profit < p[j] - p[i]:
                                                            max_profit = p[j] - p[i]
                                                        j += 1
    
                                                        if j == len(p):
                                                            break
                                                    i = j 
                                                    j = i + 1
    
                                                return max_profit
                                    
    3. Longest Substring Without Repeating Characters
                                        from typing import List
                                        class Solution:
                                            def lengthOfLongestSubstring(self, s: str) -> int:
                                                hash_table = {}
                                                i = 0
                                                j = 0
                                                l_s = 0
    
                                                while j < len(s):
                                                
                                                    if s[j] not in hash_table.keys():
                                                        hash_table[s[j]] = j
                                                    else:
                                                        i = max(i, hash_table[s[j]] + 1)
                                                        hash_table[s[j]] = j
    
                                                    l_s = max(l_s, j - i + 1)
                                                    j += 1
    
                                                return l_s
    
                                    
    424. Longest Repeating Character Replacement
                                        class Solution:
                                        def characterReplacement(self, s: str, k: int) -> int:
                                            i = 0
                                            j = 0
                                            max_f = 0
                                            longest = 0
                                            hash_t = {}
                                            while j < len(s):
                                                if s[j] not in hash_t:
                                                    hash_t[s[j]] = 1
                                                    
                                                else:
                                                    hash_t[s[j]] += 1
    
                                                max_f = max(max_f, hash_t[s[j]])
    
                                                if (j - i + 1) - max_f <= k:
                                                    longest = max(longest, (j - i + 1))
                                                else:
                                                    hash_t[s[i]] -= 1
                                                    i += 1
    
                                                j += 1
    
                                            return longest
                                    
    567. Permutation in String
                                    from typing import List
                                    class Solution:
                                        def checkInclusion(self, s1: str, s2: str) -> bool:
                                            if len(s2) < len(s1):
                                                return False
                                            hash_s1 = {}
                                            hash_s2 = {}
    
                                            for k in range(ord('a'), ord('z') + 1):
                                                c = chr(k)
                                                hash_s1[c] = 0
                                                hash_s2[c] = 0
    
    
                                            for c in s1:
                                                hash_s1[c] += 1
    
                                            i = 0
                                            j = len(s1) -  1
    
                                            for x in range(i, j):
                                                hash_s2[s2[x]] += 1
    
    
                                            while j < len(s2):
                                                hash_s2[s2[j]] += 1
    
                                                ok = True
    
                                                for k in range(ord('a'), ord('z') + 1):
                                                    c = chr(k)
    
                                                    if (c in hash_s1) != (c in hash_s2):
                                                        ok = False
    
                                                    if (c in hash_s1 ) and ( c in hash_s2):
                                                        if hash_s1[c] != hash_s2[c]:
                                                            ok = False
    
                                                if ok == True:
                                                    return True
    
                                                hash_s2[s2[i]] -= 1
    
                                                i += 1
                                                j += 1
    
                                            return False
    
                                    
    76. Minimum Window Substring
                                        class Solution:
                                            def minWindow(self, s: str, t: str) -> str:
                                                if t == "":
                                                    return ""
                                        
                                                l = 0
                                                r = 0
                                        
                                                hash_t, hash_s = {}, {}
                                        
                                                min_seq = float("infinity")
                                        
                                                sl, sr = [-1, -1]
                                        
                                        
                                                for c in t:
                                                    hash_t[c] = 1 + hash_t.get(c, 0)
                                        
                                                have = 0
                                                need = len(hash_t)
                                        
                                                while r < len(s):
                                                    hash_s[s[r]] = hash_s.get(s[r], 0) + 1
                                        
                                                    if s[r] in hash_t and hash_s[s[r]] == hash_t[s[r]]:
                                                        have += 1
                                        
                                                    while have == need:
                                                        if min_seq > (r - l + 1):
                                                            min_seq = r - l + 1
                                                            sl = l
                                                            sr = r 
                                        
                                                        hash_s[s[l]] -= 1 
                                        
                                                        if s[l] in hash_t and hash_s[s[l]] < hash_t[s[l]]:
                                                            have -= 1
                                        
                                                        l += 1
                                                    r += 1
                                                return s[sl : sr + 1] if min_seq != float("infinity") else ""
                                    
    239. Sliding Window Maximum
                                        from collections import deque
                                        from typing import List
    
    
                                        class Solution:
                                            def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
                                                sol = []
                                                dq = deque()
    
                                                l = 0
                                                r = l + k - 1
    
                                                for x in range(r + 1):
                                                    while len(dq) > 0 and nums[x] > dq[-1]:
                                                        dq.pop()
    
                                                    dq.append(nums[x])
                                                
                                                sol.append(dq[0])
    
                                                while r < (len(nums) - 1):
                                                    if nums[l] == dq[0]:
                                                        dq.popleft()
    
                                                    l += 1
    
                                                    r += 1
    
                                                    while len(dq) > 0 and nums[r] > dq[-1]:
                                                        dq.pop()
                                                    dq.append(nums[r])
                                                    sol.append(dq[0])
    
                                                return sol 
                                    
    704. Binary Search
                                        from typing import List
                                        class Solution:
                                            def search(self, nums: List[int], target: int) -> int:
                                                l = 0
                                                r = len(nums) - 1
    
                                                while l <= r:
                                                    mid = (l + r) // 2 
                                                    if nums[mid] == target:
                                                        return mid
                                                    elif nums[mid] > target:
                                                        r = mid - 1
                                                    else:
                                                        l = mid + 1 
    
                                                return -1
                                    
    74. Search a 2D Matrix
                                        from typing import List
                                        class Solution:
                                            def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
                                                arr = []
    
                                                for r in range(len(matrix)):
                                                    for c in range(len(matrix[0])):
                                                        arr.append(matrix[r][c])
    
                                                l = 0 
                                                r = len(arr) - 1
    
                                                while l <= r:
                                                    mid = (l + r) // 2
                                                    if arr[mid] == target:
                                                        return True 
                                                    elif target > arr[mid]:
                                                        l = mid + 1
                                                    else:
                                                        r = mid - 1
    
                                                return False 
                                    
    Better approach (No Extra Space)
                                        from typing import List
                                        class Solution:
                                            def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
                                                ROWS, COLS = len(matrix), len(matrix[0])
    
                                                bot, top = 0, ROWS - 1 
    
                                                while bot <= top:
                                                    m_row = (bot + top) // 2 
                                                    if target > matrix[m_row][-1]:
                                                        bot = m_row + 1 
                                                    elif target < matrix[m_row][0]:
                                                        top = m_row - 1 
                                                    else:
                                                        break
    
                                                if bot > top:
                                                    return False 
    
                                                row = (top + bot) // 2 
                                                print(row)
                                                l, r = 0, COLS - 1 
    
                                                while l <= r: 
                                                    m = (l + r) // 2 
                                                    print(m)
                                                    if target > matrix[row][m]:
                                                        l = m + 1
                                                    elif target < matrix[row][m]:
                                                        r = m - 1
                                                    else :
                                                        return True 
                                                return False 
                                    
    875. Koko Eating Bananas
                                        import math 
                                        from typing import List
                                        class Solution:
                                            def minEatingSpeed(self, piles: List[int], h: int) -> int:
                                                l = 1
                                                r = max(piles)
    
                                                sol = float("infinity")
    
                                                while l <= r:
                                                    k = (l + r) // 2
                                                    print(k)
                                                    h_e = 0
    
                                                    for i in range(len(piles)):
                                                        h_e += math.ceil(piles[i] / k)
    
                                                    if h_e <=  h:
                                                        sol = k 
                                                        r = k - 1
                                                    else:
                                                        l = k + 1
    
                                                return sol
    
                                    
    153. Find Minimum in Rotated Sorted Array
                                        from typing import List
                                        class Solution:
                                            def findMin(self, nums: List[int]) -> int:
                                                res = nums[0]
    
                                                l, r = 0, len(nums) - 1
    
                                                while l <= r:
                                                    if nums[l] < nums[r]:
                                                        res = min(res, nums[l])
                                                        break
    
                                                    m = (l + r) // 2
                                                    res = min(res, nums[m])
    
                                                    if nums[m] >= nums[l]:
                                                        l = m + 1
                                                    else:
                                                        r = m - 1
                                                return res 
                                    
    33. Search in Rotated Sorted Array
                                        from typing import List
    
                                        class Solution:
                                            def search(self, nums: List[int], target: int) -> int:
                                                l, r = 0, len(nums) - 1
    
                                                while l <= r:
                                                    m = (l + r) // 2
                                                    if target == nums[m]:
                                                        return m
    
                                                    if nums[l] <= nums[m]:
                                                        if target > nums[m] or target < nums[l]:
                                                            l = m + 1 
                                                        else:
                                                            r = m - 1 
                                                    else:
                                                        if target < nums[m] or target > nums[r]:
                                                            r = m - 1
                                                        else:
                                                            l = m + 1
    
                                                return -1 
                                    
    981. Time Based Key-Value Store
                                        class TimeMap:
    
                                        def __init__(self):
                                            self.hash = {}
    
                                        def set(self, key: str, value: str, timestamp: int) -> None:
                                            if key not in self.hash:
                                                self.hash[key] = { "v" : [], "t" : []}
    
                                            self.hash[key]["v"].append(value)
                                            self.hash[key]["t"].append(timestamp)
    
                                        def get(self, key: str, timestamp: int) -> str:
                                            if key not in self.hash:
                                                return ""
                                            arr = self.hash[key]["t"]
    
                                            l , r = 0, len(arr) - 1 
                                            index = float("infinity")
                                            while l <= r:
                                                m = (l + r) // 2 
                                                if arr[m] <= timestamp:
                                                    index = m
                                                    if arr[m] == timestamp:
                                                        break
                                                    else:
                                                        l = m + 1 
                                                else:
                                                    r = m - 1
                                            if index != float("infinity"):
                                                return self.hash[key]["v"][index]
                                            return ""
                                    
    4. Median of Two Sorted Arrays
                                        from typing import List
                                        class Solution:
                                            def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
                                                A, B = nums1, nums2
                                                total = len(nums1) + len(nums2)
                                                half = total // 2
    
                                                if len(B) < len(A):
                                                    A, B = B, A
    
                                                l, r = 0, len(A) - 1
                                                while True:
                                                    i = (l + r) // 2  
                                                    j = half - i - 2  
    
                                                    Aleft = A[i] if i >= 0 else float("-infinity")
                                                    Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
                                                    Bleft = B[j] if j >= 0 else float("-infinity")
                                                    Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
    
                                                    if Aleft <= Bright and Bleft <= Aright:
                                                        if total % 2:
                                                            return min(Aright, Bright)
                                                        return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
                                                    elif Aleft > Bright:
                                                        r = i - 1
                                                    else:
                                                        l = i + 1
                                    
    206. Reverse Linked List
    ITERATIVE APPROACH:
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
                                                    current = head;
                                                    prev = None;
                                                    if current == None:
                                                        return current
                                                    while current.next != None:
                                                        next_node = current.next
                                                        current.next = prev
                                                        prev = current
                                                        current = next_node
                                                    current.next = prev
                                                    return current
                                        
                                    
    RECURSIVE APPROACH:
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
                                                    def recursive(ll, rl):
                                                        if not ll:
                                                            return rl
                                                        return recursive(ll.next, ListNode(ll.val, rl))
                                                    
                                                    return recursive(head, None)
                                        
                                    
    21. Merge Two Sorted Lists
                                        
                                            # 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, list1, list2):
                                                    head = None
                                                    current = None
                                                    
                                                    while list1 != None and list2 != None:
                                                        new_node = ListNode()
                                                        if list1.val < list2.val:
                                                            new_node.val = list1.val
                                                            list1 = list1.next
                                                        else:
                                                            new_node.val = list2.val
                                                            list2 = list2.next
                                                        if head == None:
                                                            head = new_node
                                                            current = head
                                                        else:
                                                            current.next = new_node
                                                            current = new_node
    
                                                    if list1 != None:
                                                        if current == None:
                                                            head = list1
                                                        else:
                                                            current.next = list1
                                                    if list2 != None:
                                                        if current == None:
                                                            head = list2
                                                        else:
                                                            current.next = list2
    
                                                    current = head
                                                    while current != None:
                                                        current = current.next
                                                    
                                                    return head
                                                    
                                        
                                    
    143. Reorder List
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
    
                                            class Solution:
                                                def reorderList(self, head: Optional[ListNode]) -> None:
                                                    """
                                                    Do not return anything, modify head in-place instead.
                                                    """
                                                    # 1 Find the middle and split the list in two segments
    
                                                    slow = head 
                                                    fast = head.next
    
                                                    while fast and fast.next:
                                                        slow = slow.next
                                                        fast = fast.next.next
    
                                                    second = slow.next
                                                    slow.next = prev = None
    
                                                    # 2 Reverse the second segment
    
                                                    while second:
                                                        tmp = second.next 
                                                        second.next = prev
                                                        prev = second
                                                        second = tmp
                                                    
                                                    first = head
                                                    second = prev
    
                                                    # 3 Merge the two segments
    
                                                    while second:
                                                        tmp1 = first.next
                                                        tmp2 = second.next
    
                                                        first.next = second
                                                        second.next = tmp1
                                                        first = tmp1
                                                        second = tmp2
    
                                                    #4 Return the reordered list
    
                                                    return head                                    
                                        
                                    
    19. Remove Nth Node From End of List
                                        
                                            # 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: Optional[ListNode], n: int) -> Optional[ListNode]:
                                                    # 1 Initialize two pointers
                                            
                                                    p1 = head
                                                    p2 = head
                                            
                                                    # 2 Move the second pointer n nodes away from the first pointer
                                            
                                                    while n > 0:
                                                        p2 = p2.next
                                                        n -= 1
                                                    
                                                    # 3 Iterate the second pointer until it reaches the end of the list
                                            
                                                    while p2 and p2.next:
                                                        p1 = p1.next
                                                        p2 = p2.next
                                                    
                                                    # 4 Remove the n-th node from the end of the list
                                            
                                                    if p2 == None: # if the first node should be removed
                                                        head = head.next
                                                    else:
                                                        p1.next = p1.next.next
                                                    
                                                    # 5 Return the list
                                            
                                                    return head
                                         
                                    
    138. Copy List with Random Pointer
                                        
                                            """
                                            # Definition for a Node.
                                            class Node:
                                                def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
                                                    self.val = int(x)
                                                    self.next = next
                                                    self.random = random
                                            """
    
                                            class Solution:
                                                def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
                                                    # 1 Initialize a hash table where each node of the orginal list 
                                                    # will be a key to each node in the copied list
    
                                                    oldToCopy = {None : None}
    
                                                    # 2 Iterate over the list and create a copy of each node with the 
                                                    # same value 
    
                                                    cur = head 
                                                    while cur:
                                                        copy = Node(cur.val)
                                                        oldToCopy[cur] = copy
                                                        cur = cur.next
    
                                                    # 3 Iterate once again and add the next and random references
    
                                                    cur = head
                                                    while cur:
                                                        copy = oldToCopy[cur]
                                                        copy.next = oldToCopy[cur.next]
                                                        copy.random = oldToCopy[cur.random]
                                                        cur = cur.next
                                                    
                                                    # 4 Return the head of the copied linked list
    
                                                    return oldToCopy[head]
                                                    
                                         
                                    
    2. Add Two Numbers
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
                                                    # 1 Initialize the sum variable that will retain the sum of the digits
                                                    sum = 0
                                                    # 2 Initialize the head of the sum linked list 
                                                    # and also the last node of this list
    
                                                    l3 = last = None
    
                                                    # 3 Iterate over the l1 and l2 and add the digits to l3 
    
                                                    while l1 and l2:
                                                        sum += l1.val + l2.val
                                                        if l3 == None:
                                                            l3 = ListNode(sum % 10)
                                                            last = l3 
                                                        else:
                                                            last.next = ListNode(sum % 10)
                                                            last = last.next
                                                        sum = sum // 10
                                                        l1 = l1.next 
                                                        l2 = l2.next
                                                    # 4 Iterate over both lists until the finish node
    
                                                    while l1:
                                                        sum += l1.val
                                                        last.next = ListNode(sum % 10)
                                                        last = last.next
                                                        sum = sum // 10
                                                        l1 = l1.next
                                                        
                                                    while l2:
                                                        sum += l2.val
                                                        last.next = ListNode(sum % 10)
                                                        last = last.next
                                                        sum = sum // 10
                                                        l2 = l2.next
                                                    
                                                    # 5 If there is 1 digit remained in the sum 
                                                    # add it to the sum list
    
                                                    if sum > 0:
                                                        last.next = ListNode(sum % 10)
                                                        last = last.next
                                                        sum = sum // 10
                                                    
                                                    # 6 Return the sum as a linked list
    
                                                    return l3
                                         
                                    
    141. Linked List Cycle FIRST APPROACH O(n) memory
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, x):
                                            #         self.val = x
                                            #         self.next = None
    
                                            class Solution:
                                                def hasCycle(self, head: ListNode) -> bool:
                                                    # 1 Create a hash table in order to retain all the nodes in the 
                                                    # linked list 
    
                                                    copy = {}
    
                                                    # 2 Iterate over all the nodes in the list 
                                                    # If the same node is reached twice, then we have a cycle
                                                    # otherwise not
    
                                                    cur = head 
    
                                                    while cur:
                                                        if cur in copy:
                                                            return True
                                                        else:
                                                            copy[cur] = True
                                                        cur = cur.next
    
                                                    return False 
                                         
                                    
    SECOND APPROACH TWO POINTERS : FLOYD'S TURTOISE AND HARE
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, x):
                                            #         self.val = x
                                            #         self.next = None
    
                                            class Solution:
                                                def hasCycle(self, head: ListNode) -> bool:
                                                    # 1 Initialize two pointers at the head 
                                                    slow = fast = head
    
                                                    # 2 Iterate the pointers over the list 
                                                    # fast pointer will be iterated twice as fast as 
                                                    # the slow pointer
    
                                                    # 3 If there is a cycle in the list, then they 
                                                    # will meet at the same position because 
                                                    # the difference between them will be decremented 
                                                    # by one with each iteration when they 
                                                    # are both in the cycle
    
                                                    while fast and fast.next:
                                                        slow = slow.next
                                                        fast = fast.next.next
                                                        if slow == fast:
                                                            return True
                                                    return False
            
    
                                        
                                    
    287. Find the Duplicate Number
                                        
                                            class Solution:
                                            def findDuplicate(self, nums: List[int]) -> int:
                                                # 1 Initialize two pointers slow and fast
                                                slow = fast = 0
                                        
                                                # 2 Iterate the fast pointer twice as fast as the slow pointer
                                                # and break when they meet each other 
                                        
                                                while True:
                                                    slow = nums[slow]
                                                    fast = nums[nums[fast]]
                                                    if slow == fast:
                                                        break
                                        
                                                # 3 Initialize a new pointer at the start
                                                slow2 = 0
                                        
                                                # 4 Iterate slow2 and slow until they meet at the start 
                                                # of the cycle which is the duplicate number
                                        
                                                while True:
                                                    slow2 = nums[slow2]
                                                    slow = nums[slow]
                                                    if slow == slow2:
                                                        return slow               
                                        
                                    
    146. LRU Cache
                                        
                                            # Use a doubly linked list that will store at the left side 
                                            # the Least Recently Used key 
                                            # and at the right side the most recently used key
    
                                            class Node:
                                                def __init__(self, key, value):
                                                    self.key = key
                                                    self.value = value
                                                    self.next = None
                                                    self.prev = None
                                                
                                            class LRUCache:
    
                                                def __init__(self, capacity: int):
                                                    self.cap = capacity
                                                    self.cache = {}
                                                    
                                                    self.left = None
                                                    self.right = None
                                                
                                                def insert(self, node : Node):
                                                    if self.left == None:
                                                        self.left = node
                                                    if self.right == None:
                                                        self.right = node
                                                    else:
                                                        self.right.next = node
                                                        node.prev = self.right
                                                        self.right = node
                                                
                                                def remove(self, node : Node):
                                                    if self.right != node and self.left != node:
                                                        node.prev.next = node.next
                                                        node.next.prev = node.prev
                                                    if self.left == node:
                                                        if node.next: 
                                                            node.next.prev = None
                                                        self.left = self.left.next
                                                    if self.right == node:
                                                        if node.prev: 
                                                            node.prev.next = None
                                                        self.right = node.prev
    
    
                                                def get(self, key: int) -> int:
                                                    if key not in self.cache:
                                                        return -1
                                                    node = self.cache[key]
                                                    self.remove(node)
                                                    self.insert(node)
                                                    return node.value
    
                                                def put(self, key: int, value: int) -> None:
                                                    if key in self.cache:
                                                        node = self.cache[key]
                                                        node.value = value
                                                        self.remove(node)
                                                        node.next = None
                                                        self.insert(node)
                                                    else:         
                                                        self.cap = self.cap - 1
                                                        node = Node(key, value)
                                                        self.insert(node)
                                                        self.cache[key] = node
                                                    if self.cap < 0:
                                                        del self.cache[self.left.key]
                                                        self.remove(self.left)
                                                        self.cap += 1
                                         
                                    
    23. Merge k Sorted Lists
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
                                                    # 1 Iterate the current node on each k linked lists 
                                                    # and find the node with the minimum value 
                                                    # and iterate the list with the minimum value node 
    
                                                    res = None
                                                    last = None
                                                    while True:
                                                        min_node = None
                                                        minimum = float("inf")
                                                        it = -1
                                                        for i  in range(0, len(lists)):
                                                            x = lists[i]
                                                            if x is None:
                                                                continue
                                                            if minimum > x.val:
                                                                min_node = x
                                                                minimum = x.val
                                                                it = i
                                                        # if all the lists are finished, 
                                                        # then stop the search
                                                        if min_node == None:  
                                                            break
                                                        if res == None:
                                                            res = min_node
                                                            last = res
                                                        else:
                                                            last.next = min_node
                                                            last = last.next
                                                        lists[it] = lists[it].next
                                                    return res
                                         
                                    
    25. Reverse Nodes in k-Group FIRST APPROACH O(n) Time, O(k) Memory
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
                                                    # 1 Traverse the linked list and split the list at every k nodes
                                                    # and retain the heads of the segments in an array
                                                    seg = []
                                                    cur = head 
                                                    n = 0
                                                    while cur:
                                                        hs = cur
                                                        n = k - 1
                                                        seg.append(hs)
                                                        while n > 0 and cur:
                                                            cur = cur.next
                                                            n = n - 1
                                                        if cur:
                                                            nxt = cur.next
                                                            cur.next = None
                                                            cur = nxt
    
                                                    # 2 Check if the last segment has k nodes
    
                                                    cnt = 0
                                                    cur = seg[len(seg) - 1]
                                                    while cur:
                                                        cnt = cnt + 1
                                                        cur = cur.next
                                                    r_l = False
                                                    if cnt == k:
                                                        r_l = True
                                                    
                                                    # 3 Reverse the segements with k nodes
                                                    
                                                    for i in range(0, len(seg)):
                                                        x = seg[i]
                                                        if (i == (len(seg) - 1) and r_l) or i < (len(seg) - 1):
                                                            cur = x
                                                            prev = None
                                                            while cur:
                                                                nxt = cur.next
                                                                cur.next = prev
                                                                prev = cur
                                                                cur = nxt
                                                            seg[i] = prev
                                                            
                                                    # 4 Connect the reversed segments toghether
    
                                                    for i in range(0, len(seg) - 1):
                                                        cur = seg[i]
                                                        while cur and cur.next:
                                                            cur = cur.next
                                                        print("CUR" , cur.val, seg[i + 1].val)
                                                        cur.next = seg[i + 1]
                                                    
    
                                                    return seg[0]
    
                                         
                                    
    SECOND APPROACH O(n) Time, O(1) Memory
                                        
                                            # Definition for singly-linked list.
                                            # class ListNode:
                                            #     def __init__(self, val=0, next=None):
                                            #         self.val = val
                                            #         self.next = next
                                            class Solution:
                                                def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
                                                    # 1 Traverse the list and reverse the k group nodes
                                                    head_prev = ListNode(0, head)
                                                    group_prev = head_prev
    
                                                    while True:
                                                        kth = self.get_kth(group_prev, k)
                                                        # 2 If we are in the last group, and it contains less than k nodes
                                                        if not kth:
                                                            break
                                                        group_next = kth.next
                                                        # 3 Reverse the cur group
    
                                                        prev = kth.next
                                                        cur = group_prev.next
                                                        while cur != group_next:
                                                            nxt = cur.next
                                                            cur.next = prev
                                                            prev = cur
                                                            cur = nxt
                                                        
                                                        tmp = group_prev.next
                                                        group_prev.next = kth
                                                        group_prev = tmp
    
                                                    return head_prev.next 
                                                def get_kth(self, cur, k):
                                                    while cur and k > 0:
                                                        cur = cur.next
                                                        k = k - 1
                                                    return cur
                                         
                                    
    226. Invert Binary Tree
                                        
                                            # 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:
                                                """ Traverse the binary search tree and reverse 
                                                the left and the right subtree of each node """
                                                def invertTreeMet(self, node: TreeNode):
                                                    if node:
                                                        aux = node.left
                                                        node.left = node.right
                                                        node.right = aux
                                                        if node.left:
                                                            self.invertTree(node.left)
                                                        if node.right:
                                                            self.invertTree(node.right)
    
                                                def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
                                                    self.invertTreeMet(node=root)
                                                    return root
                                         
                                    
    104. Maximum Depth of Binary Tree
                                        
                                            # 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:
                                                """ Traverse the list and retain the max stack level, 
                                                which is going to  be the maximum depth of the binary tree """
                                                def __init__(self):
                                                    self.st = 0
                                                    self.max = -float("inf")
                                                def maxDepth(self, root: Optional[TreeNode]) -> int:
                                                    if root is None:
                                                        return 0;
                                                    self.st = self.st + 1
    
                                                    if self.max < self.st:
                                                        self.max = self.st 
                                                    if root.left:
                                                        self.maxDepth(root=root.left)
    
                                                    if root.right:
                                                        self.maxDepth(root=root.right)
    
                                                    self.st = self.st - 1
    
                                                    if self.st == 0:
                                                        return self.max
    
                                        
                                    
    543. Diameter of Binary Tree
                                        
                                            # 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:
                                                """ Traverse each node of the binary tree 
                                                and the max diameter is going to be 
                                                the max depth of the left subtree + 
                                                the max depth of the right subtree of the cur node"""
                                            
                                                def __init__(self):
                                                    self.diameter = 0
                                                    self.max_depth = -float("inf")
                                            
                                                def dfs(self, node: TreeNode):
                                                    if node == None:
                                                        return 0
                                                    left = self.dfs(node=node.left)
                                                    right = self.dfs(node=node.right)
                                                    if self.diameter < (left + right):
                                                        self.diameter = (left + right)
                                                    return 1 + max(left, right)
                                            
                                                def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
                                                    self.dfs(node=root)
                                                    return self.diameter
                                         
                                    
    110. Balanced Binary Tree
                                        
                                            # 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:
                                                """ Traverse the binary tree and for each node 
                                                check if the difference between the height of the left subtree and 
                                                the right subtree is greater than 1, in which case the binary 
                                                tree is not balanced """
                                                def __init__(self):
                                                    self.is_balanced = True
                                                
                                                def dfs(self, node: TreeNode):
                                                    if node is None: 
                                                        return 0
    
                                                    left = self.dfs(node.left)
                                                    right = self.dfs(node.right)
    
                                                    if abs(left - right) > 1:
                                                        self.is_balanced = False
                                                    return 1 + max(left, right)
                                                
                                                def isBalanced(self, root: Optional[TreeNode]) -> bool:
                                                    self.dfs(node=root)
                                                    return self.is_balanced
                                        
                                    
    100. Same Tree
                                        
                                            # 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:
                                                """ Traverse both trees at the same time and check if they are the same """
                                                def __init__(self):
                                                    self.same = True
    
                                                def dfs(self, p: TreeNode, q : TreeNode): 
                                                    if (p == None) != (q == None):
                                                        self.same = False
                                                        return 
                                                    if p == None:
                                                        return 
                                                    if p.val != q.val:
                                                        self.same = False
                                                        return 
    
                                                    self.dfs(p.left, q.left)
                                                    self.dfs(p.right, q.right)
                                                    
                                                def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
                                                    self.dfs(p, q)
                                                    return self.same
                                         
                                    
    572. Subtree of Another Tree
                                        
                                            # 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:
                                                """ Traverse each node of the root binary tree and check 
                                                if the subtree which has the root as the cur node is identical 
                                                with the subRoot tree """
                                                def __init__(self):
                                                    self.same = True
                                                    self.found = False
    
    
                                                def is_same_tree(self, p : TreeNode, q : TreeNode):
                                                    if (p == None) != (q == None):
                                                        self.same = False
                                                        return 
                                                    if p == None:
                                                        return
                                                    if p.val != q.val:
                                                        self.same = False
                                                        return 
                                                    
                                                    self.is_same_tree(p.left, q.left)
                                                    self.is_same_tree(p.right, q.right)
    
                                                def dfs(self, node: TreeNode, subRoot: TreeNode):
                                                    if node == None:
                                                        return 
                                                    self.same = True
                                                    self.is_same_tree(node, subRoot)
    
                                                    if self.same == True:
                                                        self.found = True
    
                                                    self.dfs(node=node.left, subRoot=subRoot)
                                                    self.dfs(node=node.right, subRoot=subRoot)
                                                def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
                                                    self.dfs(node=root, subRoot=subRoot)
                                                    return self.found
                                         
                                    
    235. Lowest Common Ancestor of a Binary Search Tree
                                        
                                            # Definition for a binary tree node.
                                            # class TreeNode:
                                            #     def __init__(self, x):
                                            #         self.val = x
                                            #         self.left = None
                                            #         self.right = None
    
                                            class Solution:
                                                """ Traverse the bst with from the root
                                                if both p and q are greater than root then go to the right
                                                if both p and q are lower than root than go to the left
                                                else the current node is the lca """
                                                def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
                                                    while True:
                                                        if p.val == root.val or q.val == root.val:
                                                            break
                                                        if p.val > root.val and q.val > root.val:
                                                            root = root.right
                                                        elif p.val < root.val and q.val < root.val:
                                                            root = root.left
                                                        else:
                                                            break
                                                    return root
            
                                         
                                    
    102. Binary Tree Level Order Traversal
                                        
                                            # 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:
                                                """ Traverse the list and retain a hash table with a key for each level
                                                which is going to have an arr with all the node values , 
                                                then combine the res into a single list"""
                                                def __init__(self):
                                                    self.st = 0
                                                    self.max_level = 0
                                                    self.levels = {}
                                                
                                                def dfs(self, node : TreeNode):
                                                    if not node:
                                                        return 
                                                    self.st = self.st + 1
                                                    self.max_level = max(self.max_level, self.st)
                                                    if self.st not in  self.levels:
                                                        self.levels[self.st] = []
                                                    
                                                    self.levels[self.st].append(node.val)
                                                    self.dfs(node.left)
                                                    self.dfs(node.right)
    
                                                    self.st = self.st - 1
    
                                                def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
                                                    self.dfs(root)
                                                    res = []
                                                    for i in range(1, self.max_level + 1):
                                                        res.append(self.levels[i])
                                                    return res
    
                                        
                                    
    199. Binary Tree Right Side View
                                        
                                            # 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:
                                                """ Traverse the list and append to the res arr the right most node 
                                                for each level """
                                                def __init__(self):
                                                    self.res = []
                                                def dfs(self,node: TreeNode, depth: int):
                                                    if not node:
                                                        return 
                                                    if len(self.res) == depth:
                                                        self.res.append([])
                                                    self.res[depth] = node.val
    
                                                    self.dfs(node.left, depth + 1)
                                                    self.dfs(node.right, depth + 1)
    
                                                def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
                                                    self.dfs(node=root, depth=0)
                                                    return self.res
            
                                        
                                    
    1448. Count Good Nodes in Binary Tree
                                        
                                            # 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:
                                                """ Traverse the binary tree and retain a stack with the maximum nodes 
                                                on the current path every time when we add a new item to stack,
                                                increment the number of good nodes"""
    
                                                def __init__(self):
                                                    self.st = []
                                                    self.cnt = 0
                                                def dfs(self, node):
                                                    if not node:
                                                        return
                                                    ok = False
                                                    if len(self.st) == 0 or self.st[-1] <= node.val:
                                                        self.st.append(node.val)
                                                        self.cnt = self.cnt + 1
                                                        ok = True
                                                    self.dfs(node.left)
                                                    self.dfs(node.right)
                                                    if ok:
                                                        self.st.pop()
                                                def goodNodes(self, root: TreeNode) -> int:
                                                    self.dfs(root)
                                                    return self.cnt
                                        
                                    
    98. Validate Binary Search Tree
    FIRST APPROACH O(n^2)
                                        
                                            # 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:
                                                """ Traverse the binary tree and for each node check if
                                                all the nodes in the right subtree are greater than the current node and 
                                                if all the nodes in the left subtree are lower than the current node"""
    
                                                def __init__(self):
                                                    self.val = None
                                                    self.part = ""
                                                    self.res = True
                                                def dfs(self, node : TreeNode):
                                                    if not node:
                                                        return 
                                                    if self.part == "left" and node.val >= self.val:
                                                        self.res = False
                                                    if self.part == "right" and node.val <= self.val:
                                                        self.res = False
                                                    self.dfs(node.left)
                                                    self.dfs(node.right)
    
                                                def traverse_bt(self, node: TreeNode):
                                                    if not node:
                                                        return
                                                    self.val = node.val
                                                    self.part = "left"
                                                    self.dfs(node.left)
                                                    self.part = "right"
                                                    self.dfs(node.right)
                                                    self.traverse_bt(node.left)
                                                    self.traverse_bt(node.right)
                                                
                                                def isValidBST(self, root: Optional[TreeNode]) -> bool:
                                                    self.traverse_bt(root)
                                                    return self.res 
                                         
                                    
    SECOND APPROACH O(n)
                                        
                                            # 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:
                                                """ Traverse the list and keep track of a left boundary and a right 
                                                boundary and check at each iteration if they are in order."""
                                            
                                                def dfs(self, left, node, right):
                                                    if not node:
                                                        return True
                                                    if not (left < node.val < right):
                                                        return False
                                            
                                                    return self.dfs(left,node.left ,node.val) and self.dfs(node.val,node.right,right)
                                            
                                                def isValidBST(self, root: Optional[TreeNode]) -> bool:
                                                    return self.dfs(float("-inf"), root, float("inf"))                                        
                                         
                                    
    230. Kth Smallest Element in a BST
    APPROACH O(n)
                                        
                                            # 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:
                                                """ Traverse the bst and keep track of a stack that will contain the
                                                smallest values. When this stack has a size of k, then return
                                                the top"""
                                                
                                                def __init__(self):
                                                    self.st = []
                                                    self.res = None
                                                
                                                def dfs(self, node: TreeNode, k : int):
                                                    if node == None or self.res != None:
                                                        return 
                                                    self.dfs(node.left, k)
                                                    self.st.append(node.val)
                                                    if len(self.st) == k and self.res == None:
                                                        self.res = self.st[-1]
                                                    self.dfs(node.right, k )
    
                                                def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
                                                    self.dfs(root, k)
                                                    return self.res
                                         
                                    
    105. Construct Binary Tree from Preorder and Inorder Traversal
                                        
                                            # 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:
                                                """ Recursive approach:
                                                base case: if preorder or inorder arr are empty, then return None,
                                                recursive case : The root is going to be pre[0], 
                                                mid is going to be inorder index of pre[0].
                                                The right side until mid in the inorder arr is going to be the left subtree
                                                and the left side, the left subtree."""
                                                def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
                                                    if not preorder or not inorder:
                                                        return None
                                                    
                                                    root = TreeNode(preorder[0])
                                                    mid = inorder.index(preorder[0])
    
                                                    root.left = self.buildTree(preorder[1: mid + 1], inorder[:mid])
                                                    root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
    
                                                    return root
                                         
                                    
    124. Binary Tree Maximum Path Sum
                                        
                                            # 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:
                                                """ Recursive approach: 
                                                Base case: if node is None then return 0
                                                Recursive case either: 
                                                root or root + left subtree or root + right subtree or 
                                                root + left + right subtrees"""
    
                                                def __init__(self):
                                                    self.max_path_sum = - float("inf")
                                                
                                                def dfs(self, node: TreeNode) -> int:
                                                    if not node:
                                                        return 0
                                                    l = self.dfs(node.left) 
                                                    r = self.dfs(node.right) 
                                                    
                                                    self.max_path_sum = max(self.max_path_sum, node.val, node.val + l, node.val + r, node.val + l + r)
                                                    
                                                    return max(node.val, node.val + l, node.val + r)
    
                                                def maxPathSum(self, root: Optional[TreeNode]) -> int:
                                                    print(self.dfs(root))
                                                    return self.max_path_sum
                                         
                                    
    297. Serialize and Deserialize Binary Tree
                                        
                                            # Definition for a binary tree node.
                                            # class TreeNode(object):
                                            #     def __init__(self, x):
                                            #         self.val = x
                                            #         self.left = None
                                            #         self.right = None
    
                                            class Codec:
                                                """Make a preorder traversal and create a string with the node values
                                                Then iterate that string and recreate the binary tree!"""
                                                def __init__(self):
                                                    self.res = ""
                                                    self.index = 0
                                                    
                                                def dfs(self, node: TreeNode):
                                                    if len(self.res) > 0:
                                                        self.res += ","
                                                    if not node:
                                                        self.res += "N"
                                                        return 
                                                    self.res += str(node.val)
                                                    self.dfs(node.left)
                                                    self.dfs(node.right)
                                                
    
                                                def serialize(self, root):
                                                    """Encodes a tree to a single string.
                                                    
                                                    :type root: TreeNode
                                                    :rtype: str
                                                    """
                                                    self.dfs(root)
                                                    print(self.res)
                                                    return self.res
                                                
                                                def des(self, data):
                                                    if data[self.index] == "N":
                                                        return None
                                                    root = TreeNode(int(data[self.index]))
                                                    self.index = self.index + 1
                                                    root.left = self.des(data)
                                                    self.index = self.index + 1
                                                    root.right = self.des(data)
                                                    return root
    
                                                def deserialize(self, data):
                                                    """Decodes your encoded data to tree.
                                                    
                                                    :type data: str
                                                    :rtype: TreeNode
                                                    """
                                                    data = data.split(",")
                                                
                                                    return self.des(data)
    
                                                    
    
                                            # Your Codec object will be instantiated and called as such:
                                            # ser = Codec()
                                            # deser = Codec()
                                            # ans = deser.deserialize(ser.serialize(root))
                                         
                                    
    208. Implement Trie (Prefix Tree)
                                        
                                            class TrieNode:
                                                def __init__(self):
                                                    self.child = [None] * 26
                                                    self.word_end = False
                                            class Trie:
                                                """Start wirh an empty root node which is going to have 
                                                26 None values and a word_end value which is going 
                                                to represent the end of a word in this Trie"""  
                                                def __init__(self):
                                                    self.root = TrieNode()
    
                                                def insert(self, word: str) -> None:
                                                    cur = self.root
                                                    for c in word:
                                                        index = ord(c) - ord('a')
                                                        if cur.child[index] is None:
                                                            new_node = TrieNode()
                                                            cur.child[index] = new_node
                                                        cur = cur.child[index]
                                                    cur.word_end = True
    
                                                def search(self, word: str) -> bool:
                                                    cur = self.root
                                                    for c in word:
                                                        index = ord(c) - ord('a')
                                                        if cur.child[index] is None:
                                                            return False
                                                        cur = cur.child[index]
                                                    return cur.word_end
    
                                                def startsWith(self, prefix: str) -> bool:
                                                    cur = self.root
                                                    for c in prefix:
                                                        index = ord(c) - ord('a')
                                                        if cur.child[index] is None:
                                                            return False
                                                        cur = cur.child[index]
                                                    return True
    
    
                                            # Your Trie object will be instantiated and called as such:
                                            # obj = Trie()
                                            # obj.insert(word)
                                            # param_2 = obj.search(word)
                                            # param_3 = obj.startsWith(prefix)
                                         
                                    
    211. Design Add and Search Words Data Structure
                                        
                                            class TrieNode:
                                                def __init__(self):
                                                    self.child = {}
                                                    self.word_end = False
    
                                            class WordDictionary:
                                                """Use a Trie (Prefix Tree) 
                                                and for search create a dfs"""
                                                def __init__(self):
                                                    self.root = TrieNode()
    
                                                def addWord(self, word: str) -> None:
                                                    print("WORD : " ,word)
                                                    cur = self.root
                                                    for c in word:
                                                        if c not in cur.child:
                                                            cur.child[c] = TrieNode()
                                                        cur = cur.child.get(c)
                                                    cur.word_end = True
                                                        
                                                def dfs(self, node, index, word):
                                                    if index == len(word) and node.word_end == False:
                                                        return False
                                                    elif index == len(word) and node.word_end == True:
                                                        return True 
    
                                                    c = word[index]
                                                    if c == ".":
                                                        for v in node.child.values():
                                                            if self.dfs(v, index + 1, word):
                                                                return True
                                                        return False
                                                    elif c in node.child:
                                                        return self.dfs(node.child.get(c), index + 1, word)
                                                    return False
    
                                                def search(self, word: str) -> bool:
                                                    res =  self.dfs(self.root, 0, word)
                                                    return res
    
    
    
                                            # Your WordDictionary object will be instantiated and called as such:
                                            # obj = WordDictionary()
                                            # obj.addWord(word)
                                            # param_2 = obj.search(word)
                                         
                                    
    212. Word Search II
                                        
                                            class TrieNode:
                                                def __init__(self):
                                                    self.children = {}
                                                    self.is_word = False
    
                                                def add_word(self, word):
                                                    cur = self
                                                    for c in word:
                                                        if c not in cur.children:
                                                            cur.children[c] = TrieNode()
                                                        cur = cur.children[c]
                                                    cur.is_word = True
    
                                                
                                            class Solution:
                                                """Create a trie with all the words in words list
                                                Start a dfs from each cell of the board and check if 
                                                the cur word exists in the trie!"""
                                                def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
                                                    root = TrieNode()
                                                    for w in words:
                                                        root.add_word(w)
                                                    
                                                    ROWS = len(board)
                                                    COLS = len(board[0])
    
                                                    res = set()
                                                    vis = set()
    
                                                    def dfs(r, c, node, word):
                                                        if r < 0 or c < 0 or r == ROWS or c == COLS or (r, c) in vis or board[r][c] not in node.children:
                                                            return 
                                                        vis.add((r, c))
                                                        node = node.children[board[r][c]]
                                                        word += board[r][c]
    
                                                        if node.is_word == True:
                                                            res.add(word)
                                                        
                                                        dfs(r - 1, c, node, word)
                                                        dfs(r + 1, c, node, word)
                                                        dfs(r, c - 1, node, word)
                                                        dfs(r, c + 1, node, word)
    
                                                        vis.remove((r,c))
    
                                                    for r in range(ROWS):
                                                        for c in range(COLS):
                                                            dfs(r, c, root, "")
                                                        
                                                    return list(res)
    
                                        
                                    
    973. K Closest Points to Origin
                                        
                                            from heapq import heapify, heappush, heappop, nlargest
    
                                            class KthLargest:
                                                """Retain k elements in the min heap"""
                                                def __init__(self, k: int, nums: List[int]):
                                                    self.min_heap, self.k = nums, k
                                                    heapq.heapify(self.min_heap)
                                                    while len(self.min_heap) > k:
                                                        heapq.heappop(self.min_heap)
    
                                                def add(self, val: int) -> int:
                                                    heapq.heappush(self.min_heap, val)
                                                    if len(self.min_heap) > self.k:
                                                        heapq.heappop(self.min_heap)
                                                    return self.min_heap[0]
    
    
                                            # Your KthLargest object will be instantiated and called as such:
                                            # obj = KthLargest(k, nums)
                                            # param_1 = obj.add(val)
                                         
                                    
    1046. Last Stone Weight
                                        
                                            from heapq import heapify, heappush, heappop
    
                                            class Solution:
                                                """Create a max heap and while this heap has at least 2 values
                                                smash the heaviest two stones """
                                                def lastStoneWeight(self, stones: List[int]) -> int:
                                                    heap = []
                                                    heapify(heap)
                                                    for x in stones:
                                                        heappush(heap, -x)
                                                    while len(heap) > 1:
                                                        y = - heappop(heap)
                                                        x = - heappop(heap)
                                                        if x != y:
                                                            heappush(heap, -(y - x))
                                                    res = 0
                                                    while len(heap) > 0:
                                                        res = - heappop(heap)
                                                    
                                                    return res
                                        
                                    
    1046. Last Stone Weight
                                        
                                            from heapq import heapify, heappush, nsmallest
                                            class Solution:
                                                """Create a small heap with tuples where the first element in the tuple
                                                is the dist from a point to the origin and the second element is 
                                                the index in points arr, then get the k smallest elements in that heap"""
                                                def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
                                                    heap = []
                                                    res = []
                                                    heapify(heap)
                                                    for i in range(0, len(points)):
                                                        p = points[i]
                                                        x = p[0]
                                                        y = p[1]
                                                        distance = sqrt(pow(abs(x - 0), 2) + pow(abs(y - 0), 2))
                                                        heappush(heap, (distance, i))
                                                    k_smallest = nsmallest(k, heap)
                                                    for i in k_smallest:
                                                        res.append(points[i[1]])
                                                    return res
    
                                        
                                    
    215. Kth Largest Element in an Array
                                        
                                            from heapq import heapify, heappush, heappop, nlargest
                                            class Solution:
                                                """Create a min heap and return the k_largest element from that heap"""
                                                def findKthLargest(self, nums: List[int], k: int) -> int:
                                                    heap = nums
                                                    heapify(heap)
                                                    k_largest = nlargest(k, heap)
                                                    return k_largest[-1]
                                        
                                    
    621. Task Scheduler
                                        
                                            class Solution:
                                            """Retain a max heap of the frequencies and deque of the idle times"""
                                            def leastInterval(self, tasks: List[str], n: int) -> int:
                                                count = Counter(tasks)
                                                max_heap = [-cnt for cnt in count.values()]
                                                heapq.heapify(max_heap)
    
                                                time = 0
                                                q = deque()
    
                                                while max_heap or q:
                                                    time += 1
                                                    if max_heap:
                                                        cnt = 1 + heapq.heappop(max_heap)
                                                        if cnt:
                                                            q.append([cnt, time + n])
                                                    if q and q[0][1] == time:
                                                        heapq.heappush(max_heap, q.popleft()[0])
                                                    
                                                return time
                                        
                                    
    355. Design Twitter
                                        
                                            from collections import defaultdict, deque
    
                                            class Twitter:
    
                                                def __init__(self):
                                                    self.follows = defaultdict(set)
                                                    self.feed = deque()
    
                                                def postTweet(self, userId: int, tweetId: int) -> None:
                                                    self.feed.appendleft((userId, tweetId))
    
                                                def getNewsFeed(self, userId: int) -> List[int]:
                                                    return [tweetId for user, tweetId in self.feed if userId == user or user in self.follows[userId]][:10]
    
                                                def follow(self, followerId: int, followeeId: int) -> None:
                                                    self.follows[followerId].add(followeeId)
    
                                                def unfollow(self, followerId: int, followeeId: int) -> None:
                                                    self.follows[followerId].discard(followeeId)
    
    
                                            # Your Twitter object will be instantiated and called as such:
                                            # obj = Twitter()
                                            # obj.postTweet(userId,tweetId)
                                            # param_2 = obj.getNewsFeed(userId)
                                            # obj.follow(followerId,followeeId)
                                            # obj.unfollow(followerId,followeeId)
                                        
                                    
    295. Find Median from Data Stream
    FIRST APPROACH : Sorting O(m∗nlogn)
                                        
                                            class MedianFinder:
                                            """"Store numbers in an arr on addNum
                                            and on findMedian sort the arr and find the median"""
                                            def __init__(self):
                                                self.arr = []
    
                                            def addNum(self, num: int) -> None:
                                                self.arr.append(num)
    
                                            def findMedian(self) -> float:
                                                self.arr.sort()
                                                if len(self.arr) % 2 == 0:
                                                    return (self.arr[len(self.arr) // 2] + self.arr[len(self.arr) // 2 - 1]) / 2
                                                return self.arr[len(self.arr) // 2]
    
    
    
                                        # Your MedianFinder object will be instantiated and called as such:
                                        # obj = MedianFinder()
                                        # obj.addNum(num)
                                        # param_2 = obj.findMedian()
                                        
                                    

    SECOND APPROACH: Heaps O(m * logn)
                                        
                                            class MedianFinder:
    
                                            def __init__(self):
                                                """Using two heaps, which should be aproximately equal in size"""
                                                self.small = [] 
                                                self.large = [] 
                                        
                                            def addNum(self, num: int) -> None:
                                                if self.large and num > self.large[0]:
                                                    heapq.heappush(self.large, num)
                                                else:
                                                    heapq.heappush(self.small, -num)
                                        
                                                if len(self.small) > len(self.large) + 1:
                                                    val = - heapq.heappop(self.small)
                                                    heapq.heappush(self.large, val)
                                        
                                                if len(self.large) > len(self.small) + 1:
                                                    val = heapq.heappop(self.large)
                                                    heapq.heappush(self.small, -val)
                                        
                                            def findMedian(self) -> float:
                                                if len(self.small) > len(self.large):
                                                    return -1 * self.small[0]
                                                elif len(self.large) > len(self.small):
                                                    return self.large[0]
                                                return (-self.small[0] + self.large[0]) / 2
                                        
                                        
                                            # Your MedianFinder object will be instantiated and called as such:
                                            # obj = MedianFinder()
                                            # obj.addNum(num)
                                            # param_2 = obj.findMedian()
                                        
                                    
    78. Subsets
                                        
                                            class Solution:
                                                """Add an element to the curr path with each iteration"""
                                                def subsets(self, nums: List[int]) -> List[List[int]]:
                                                    res = []
    
                                                    def bkt(start, path):
                                                        res.append(path)
                                                        for i in range(start, len(nums)):
                                                            bkt(i + 1, path + [nums[i]])
                                                    bkt(0, [])
                                                    return res  
                                        
                                    
    39. Combination Sum
    FIRST APPROACH
                                        
                                            class Solution:
                                            """Add an element to the curr path with each iteration"""
                                            def subsets(self, nums: List[int]) -> List[List[int]]:
                                                res = []
    
                                                def bkt(start, path):
                                                    res.append(path)
                                                    for i in range(start, len(nums)):
                                                        bkt(i + 1, path + [nums[i]])
                                                bkt(0, [])
                                                return res
                                         
                                    

    SECOND APPROACH
                                        
                                            class Solution:
                                                """Using dfs with two branches"""
                                                def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
                                                    res = []
                                                    def dfs(i, cur, total): 
                                                        if total == target:
                                                            res.append(cur[:])
                                                            return
                                                        if i >= len(candidates) or total > target:
                                                            return
                                                        cur.append(candidates[i])
                                                        dfs(i, cur, total + candidates[i]) 
                                                        cur.pop()
                                                        dfs(i + 1, cur, total)
    
                                                    dfs(0, [], 0) 
                                                    return res
                        
                                         
                                    
    46. Permutations
                                        
                                            class Solution:
                                                """A simple bkt solution, 
                                                recursive case if v doesn't appear in the cur solution
                                                base case: if len(sol) = len(nums)"""
                                                def permute(self, nums: List[int]) -> List[List[int]]:
                                                    res = []
                                                    path = []
    
                                                    def ok(v):
                                                        for val in path:
                                                            if v == val:
                                                                return False
                                                        return True
                                                    def bkt():
                                                        if len(path) == len(nums):
                                                            print(path)
                                                            res.append(path[:])
                                                        if len(path) >= len(nums):
                                                            return 
                                                        for v in nums:
                                                            if ok(v):
                                                                path.append(v)
                                                                bkt()
                                                                path.pop()
                                                    bkt()
                                                    return res
                                        
                                    
    90. Subsets II
    FIRST APPROACH: Hash Set
                                        
                                            class Solution:
                                                """Backtracking solution with a hash set"""
                                                def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
                                                    res = []
                                                    path = []
                                                    hash_set = set()
                                                    nums.sort()
                                                    def bkt(i):
                                                        if tuple(path) not in hash_set:
                                                            hash_set.add(tuple(path))
                                                            res.append(path[:])
    
                                                        if len(path) >= len(nums):
                                                            return
    
                                                        for idx in range(i, len(nums)): 
                                                            path.append(nums[idx])
                                                            bkt(idx + 1)
                                                            path.pop()
                                                            bkt(idx + 1)
                                                    bkt(0)
                                                    return res
                                         
                                    
    40. Combination Sum II
                                        
                                            class Solution:
                                                """Backtracking solution, base case: if s == target:
                                                recursive case, if I pass duplicated values and the s is not greater than the target"""
                                                def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
                                                    res = []
                                                    path = []
                                                    candidates.sort()
                                                    s = 0
    
                                                    def bkt(i, s):
                                                        if s == target:
                                                            res.append(path[:])
                                                            return 
    
                                                        for idx in range(i, len(candidates)):
                                                            if idx > i and candidates[idx] == candidates[idx - 1]:
                                                                continue
                                                            if (s + candidates[idx] ) > target:
                                                                break
                                                            path.append(candidates[idx])
                                                            s += candidates[idx]
                                                            bkt(idx + 1, s)
                                                            path.pop()
                                                            s -= candidates[idx]
                                                    
                                                    bkt(0, 0)
    
                                                    return res
                                        
                                    
    79. Word Search
                                        
                                            class Solution:
                                                """Backtracking in plane approach with a set for visited indices"""
                                                def exist(self, board: List[List[str]], word: str) -> bool:
                                                    m = len(board)
                                                    n = len(board[0])
                                                    vis = set()
                                                    def bkt(i, j, idx):
                                                        if idx == len(word):
                                                            return True
    
                                                        if i < 0 or j < 0 or i == m or j == n:
                                                            return False
                                                        
                                                        if board[i][j] != word[idx] or (i, j) in vis:
                                                            return False
    
                                                        vis.add((i, j))
    
                                                        found =  bkt(i - 1, j, idx + 1) or bkt(i + 1, j, idx + 1) or bkt(i, j + 1, idx + 1) or bkt(i, j - 1, idx + 1)
                                                        
                                                        vis.remove((i, j))
    
                                                        return found
    
                                                    for i in range(0, m):
                                                        for j in range(0, n):
                                                            if bkt(i, j, 0):
                                                                return True
                                                            vis.clear()
                                                    return False
                                         
                                    
    131. Palindrome Partitioning
                                        
                                            class Solution:
                                                """Backtraking approach:
                                                base case : idx == len(s)
                                                recursive case : sub is a palindrome"""
                                                def partition(self, s: str) -> List[List[str]]:
                                                    res = []
                                                    p = []
                                                    def bkt(idx):
                                                        if idx == len(s):
                                                            res.append(p[:])
                                                            return 
                                                        sub = ""
                                                        for i in range(idx, len(s)):
                                                            c = s[i]
                                                            sub += c
                                                            if sub == sub[::-1]:
                                                                p.append(sub)
                                                                bkt(i + 1)
                                                                p.pop()
                                                    bkt(0)
                                                    return res
                                        
                                    
    17. Letter Combinations of a Phone Number
                                        
                                            class Solution:
                                                """Backtraking recursive function:
                                                Retain in a dict all the posible letters for each digit
                                                Create a board with all the possible letters for each digit
                                                Run a bkt for each row in the board:
                                                Base case : when current row == rows in the board:
                                                Recursive case: add each cell of the curr row to the current comb"""
                                                def letterCombinations(self, digits: str) -> List[str]:
                                                    if len(digits) == 0:
                                                        return []
    
                                                    d = {
                                                        2: ['a', 'b', 'c'],
                                                        3: ['d', 'e', 'f'],
                                                        4: ['g', 'h', 'i'],
                                                        5: ['j', 'k', 'l'],
                                                        6: ['m', 'n', 'o'],
                                                        7: ['p', 'q', 'r', 's'],
                                                        8: ['t', 'u', 'v'],
                                                        9: ['w', 'x', 'y', 'z']
                                                    }
                                                    
                                                    b = []
    
                                                    for digit in digits:
                                                        b.append(d.get(int(digit)))
    
                                                    res = []
                                                    comb = []
                                                    ROWS = len(b)
                                                    COLS = len(b[0])
    
                                                    def bkt(r):
                                                        if r == ROWS:
                                                            res.append("".join(comb))
                                                            return 
                                                        for c in b[r]:
                                                            comb.append(c)
                                                            bkt(r + 1)
                                                            comb.pop()
    
                                                    bkt(0)
    
                                                    return res
                                        
                                    
    51. N-Queens
                                        
                                            class Solution:
                                                """Backtraking recursive function:
                                                base case: if r == n
                                                recursive case: Try to add a Q to each column of the current row and 
                                                move to the next row"""
                                                def solveNQueens(self, n: int):
                                                    res = []
                                                    board = [["."] * n for i in range(n)]
    
                                                    def bkt(r):
                                                        if r == n:
                                                            copy = ["".join(row) for row in board]
                                                            res.append(copy)
                                                            return
                                                        for c in range(n):
                                                            if self.isSafe(r, c, board):
                                                                board[r][c] = "Q"
                                                                bkt(r + 1)
                                                                board[r][c] = "."
    
                                                    bkt(0)
                                                    return res
    
                                                def isSafe(self, r: int, c: int, board):
                                                    row = r - 1
                                                    while row >= 0:
                                                        if board[row][c] == "Q":
                                                            return False
                                                        row -= 1
                                                        
                                                    row, col = r - 1, c - 1
                                                    while row >= 0 and col >= 0:
                                                        if board[row][col] == "Q":
                                                            return False
                                                        row -= 1
                                                        col -= 1
    
                                                    row, col = r - 1, c + 1
                                                    while row >= 0 and col < len(board):
                                                        if board[row][col] == "Q":
                                                            return False
                                                        row -= 1
                                                        col += 1
                                                    return True
                                         
                                    
    200. Number of Islands
                                        
                                            class Solution:
                                                """Backtraking in plane:
                                                Base case: if indices are in the grid, are not visitedm and the grid[i][j] is a part 
                                                of an island
                                                Recursive case: go in all directions"""
                                                def numIslands(self, grid: List[List[str]]) -> int:
                                                    m = len(grid)
                                                    n = len(grid[0])
                                                    cnt = 0
                                                    vis = set()
    
                                                    def dfs(i, j):
                                                        if i < 0 or j < 0 or i == m or j == n or (i, j) in vis or grid[i][j] == "0":
                                                            return 
    
                                                        vis.add((i, j))
    
                                                        dfs(i - 1, j)
                                                        dfs(i + 1, j)
                                                        dfs(i, j + 1)
                                                        dfs(i, j - 1)
                                                
                                                    for i in range(m):
                                                        for j in range(n):
                                                            if grid[i][j] == "1" and (i,j) not in vis:
                                                                dfs(i, j)
                                                                cnt += 1
                                                    return cnt
                                        
                                    
    695. Max Area of Island
                                        
                                            class Solution:
                                                """Backtraking in plane:
                                                Base case: if indices are in the grid and represent a part of an island which 
                                                was not visited yet.
                                                Recursive case: Go in all directions and return the sum"""
                                                def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
                                                    m = len(grid)
                                                    n = len(grid[0])
                                                    max_cells = 0
                                                    vis = set()
    
                                                    def bkt(i, j):
                                                        if i < 0 or i == m or j < 0 or j == n or (i, j) in vis or grid[i][j] == 0:
                                                            return 0
                                                        vis.add((i, j))
    
                                                        return 1 + bkt(i - 1, j) + bkt(i + 1, j) + bkt(i, j + 1) + bkt(i, j - 1)
    
                                                    for i in range(m):
                                                        for j in range(n):
                                                            if grid[i][j] == 1 and (i, j) not in vis:
                                                                max_cells = max(max_cells, bkt(i, j))
                                                    return max_cells
    
                                         
                                    
    133. Clone Graph
                                        
                                            """
                                            # Definition for a Node.
                                            class Node:
                                                def __init__(self, val = 0, neighbors = None):
                                                    self.val = val
                                                    self.neighbors = neighbors if neighbors is not None else []
                                            """
    
                                            from typing import Optional
                                            class Solution:
                                                """Use a hash table in order to store the copy for each node
                                                and call a dfs with the starting node"""
                                                def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
                                                    if not node:
                                                        return None
    
                                                    oldToNew = {}
    
                                                    def dfs(node):
                                                        if node in oldToNew:
                                                            return oldToNew[node]
    
                                                        copy = Node(node.val)
                                                        oldToNew[node] = copy
    
                                                        for n in node.neighbors:
                                                            copy.neighbors.append(dfs(n))
                                                        return copy
    
                                                    return dfs(node)
    
                                         
                                    
    994. Rotting Oranges
                                        
                                            from collections import deque
                                            class Solution:
                                                """Run a bfs from each rotten orange, if there are oranges which are not visited then return -1"""
                                                def orangesRotting(self, grid: List[List[int]]) -> int:
                                                    ROWS = len(grid)
                                                    COLS = len(grid[0])
                                                    vis = set()
                                                    di = [-1, 0, 1, 0]
                                                    dj = [0, 1, 0, -1]
                                                    q = deque()
                                                    
                                                    for i in range(ROWS):
                                                        for j in range(COLS):
                                                            if grid[i][j] == 2:
                                                                grid[i][j] = -2
                                                                q.append((i, j, 0))
                                                            elif grid[i][j] == 1:
                                                                grid[i][j] = float("inf")
    
                                                    while q:
                                                        i, j, time = q.popleft()
                                                        grid[i][j] = min(grid[i][j], time)
                                                        for k in range(4):
                                                            iv = i + di[k]
                                                            jv = j + dj[k]
                                                            if iv < 0 or jv < 0 or iv == ROWS or jv == COLS or grid[iv][jv] <= 0 or (iv, jv) in vis:
                                                                continue
                                                            q.append((iv, jv, time + 1))
                                                            vis.add((i, j))
                                                    
                                                    res = 0
    
                                                    for i in range(ROWS):
                                                        print(grid[i])
                                                        for j in range(COLS):
                                                            if grid[i][j] == float("inf"):
                                                                return -1
                                                            res = max(res, grid[i][j])
    
                                                    return res
    
                                         
                                    
    417. Pacific Atlantic Water Flow
                                        
                                            class Solution:
                                                """Use two sets for pacific and atlantic oceans
                                                Run a dfs for both sets from each cell of the border
                                                The pairs of indices which appear on both sets are 
                                                those who reach both pacific and atlantic"""
                                                def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
                                                    ROWS = len(heights)
                                                    COLS = len(heights[0])
    
                                                    pac = set()
                                                    atl = set()
    
                                                    def dfs(r, c, visit, prev_height):
                                                        if (r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prev_height:
                                                            return
                                                        visit.add((r, c))
    
                                                        dfs(r - 1, c, visit, heights[r][c])
                                                        dfs(r + 1, c, visit, heights[r][c])
                                                        dfs(r, c - 1, visit, heights[r][c])
                                                        dfs(r, c + 1, visit, heights[r][c])
                                                    
                                                    for c in range(COLS):
                                                        dfs(0, c, pac, heights[0][c])
                                                        dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
    
                                                    for r in range(ROWS):
                                                        dfs(r, 0, pac, heights[r][0])
                                                        dfs(r, COLS - 1, atl, heights[r][COLS - 1])
                                                    
                                                    res = []
    
                                                    for r in range(ROWS):
                                                        for c in range(COLS):
                                                            if (r,c) in pac and (r,c) in atl:
                                                                res.append([r,c])
                                                    return res
    
                                        
                                    
    130. Surrounded Regions
                                        
                                            class Solution:
                                                def solve(self, board: List[List[str]]) -> None:
                                                    """
                                                    Run a DFS from each of the edges which contains an O and change that to an Y
                                                    Run a DFS from each O which is not on the edge and change the region to X
                                                    Change the Y's with O's
                                                    """
    
                                                    ROWS = len(board)
                                                    COLS = len(board[0])
                                                    vis = set()
    
                                                    def bkt(i, j, c):
                                                        if i < 0 or j < 0 or i == ROWS or j == COLS or board[i][j] == 'X' or (i,j) in vis:
                                                            return 
                                                        vis.add((i,j))
                                                        board[i][j] = c
                                                        bkt(i + 1, j, c)
                                                        bkt(i - 1, j, c)
                                                        bkt(i, j + 1, c)
                                                        bkt(i, j - 1, c)
                                                    
                                                    for j in range(COLS):
                                                        if board[0][j] == 'O':
                                                            bkt(0, j, 'Y')
                                                        if board[ROWS - 1][j] == 'O':
                                                            bkt(ROWS - 1, j, 'Y')
                                                    
                                                    for i in range(ROWS):
                                                        if board[i][0] == 'O':
                                                            bkt(i, 0, 'Y')
                                                        if board[i][COLS - 1] == 'O':
                                                            bkt(i, COLS - 1, 'Y')
                                                    
                                                    for i in range(1, ROWS - 1):
                                                        for j in range(1, COLS - 1):
                                                            if board[i][j] == 'O':
                                                                bkt(i, j, 'X')
    
                                                    for i in range(ROWS):
                                                        for j in range(COLS):
                                                            if board[i][j] == 'Y':
                                                                board[i][j] = 'O'
                                         
                                    
    1346. Check If N and Its Double Exist FIRST APPROACH
                                        
                                            class Solution:
                                                """"
                                                Brute Force solution 
                                                Test for each pair of indices if the condition applies
                                                Time: O(n^2)
                                                Space: O(1)
                                                """"
                                                def checkIfExist(self, arr: List[int]) -> bool:
                                                    arr.sort()
                                                    for i in range(0, len(arr)):
                                                        for j in range(0, len(arr)):
                                                            if i != j and arr[i] == (2 * arr[j]):
                                                                return True
                                                    return False
                                        
                                    

    SECOND APPROACH
                                        
                                            class Solution:
                                                """
                                                Use a hash table to keep track of all the numbers visited
                                                If for the current number, the half or the double of it exxists in the 
                                                hash, then return True
                                                Time: O(n)
                                                Space: O(n)
                                                """
                                                def checkIfExist(self, arr: List[int]) -> bool:
                                                    seen = set()
                                                    for n in arr:
                                                        if (n * 2) in seen or n / 2 in seen:
                                                            return True
                                                        seen.add(n)
                                                    return False
                                        
                                    
    286. Walls And Gates - Explanation
                                        
                                            from collections import deque
                                            class Solution:
                                                """
                                                Run a bfs from each tresure chest and update the neighbouring land cells
                                                Time: O(m * n)
                                                Space: O(m * n)
                                                """
                                                def islandsAndTreasure(self, grid: List[List[int]]) -> None:
                                                    ROWS = len(grid)
                                                    COLS = len(grid[0])
                                                    q = deque()
                                                    for i in range(ROWS):
                                                        for j in range(COLS):
                                                            if grid[i][j] == 0:
                                                                q.append((i,j))
                                                    di = [-1, 0, 1, 0]
                                                    dj = [0, 1, 0, -1]
                                                    while q:
                                                        i,j = q.popleft()
                                                        for k in range(4):
                                                            iv = i + di[k]
                                                            jv = j + dj[k]
                                                            if iv < 0 or jv < 0 or iv == ROWS or jv == COLS \
                                                            or grid[iv][jv] == -1 or grid[iv][jv] <= grid[i][j] + 1:
                                                                continue
                                                            grid[iv][jv] = grid[i][j] + 1
                                                            q.append((iv,jv))
                                         
                                    
    207. Course Schedule
                                        
                                            from collections import defaultdict
                                            class Solution:
                                                """
                                                Run through all the prerequisites courses and construct a directed graph
                                                If a cycle exists in that graph, that means we can't take all the courses, 
                                                otherwise we can
                                                Time: O(V + E)
                                                Space: O(V + E)
                                                """
                                                def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
                                                    seen = set()
                                                    st = []
                                                    gr = defaultdict(list)
                                                    for a, b in prerequisites:
                                                        gr[b].append(a)
    
                                                    def dfs(v):
                                                        st.append(v)
                                                        seen.add(v)
                                                        for n in gr[v]:
                                                            if n in seen and n in st:
                                                                return False
                                                            if n not in seen:
                                                                if not dfs(n):
                                                                    return False
                                                        st.pop()
                                                        return True
    
                                                    for v in range(numCourses):
                                                        if v not in seen:
                                                            if not dfs(v):
                                                                return False
    
                                                    return True
                                        
                                    
    210. Course Schedule II
                                        
                                            from collections import deque, defaultdict
                                            class Solution:
                                                """
                                                Create a driected graph from the prerequisites,
                                                Run Khan's Algorithm for finding the topological sort
                                                If we have all the vertices in the result that means we have a solution,
                                                otherwise not.
                                                Time: O(V + E)
                                                Space: O(V + E)
                                                """
                                                def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
                                                    result = []
                                                    q = deque()
                                                    indegree = defaultdict(int)
                                                    gr = defaultdict(list)
    
                                                    for a, b in prerequisites:
                                                        gr[b].append(a)
                                                        indegree[a] += 1
                                                    
                                                    for v in range(numCourses):
                                                        if indegree[v] == 0:
                                                            q.append(v)
                                                    
                                                    while q:
                                                        v = q.popleft()
                                                        result.append(v)
                                                        for n in gr[v]:
                                                            indegree[n] -= 1
                                                            if indegree[n] == 0:
                                                                q.append(n)
                                                    if len(result) != numCourses:
                                                        return []
                                                    return result
                                         
                                    
    261. Graph Valid Tree
                                        
                                            from collections import defaultdict
                                            class Solution:
                                                """
                                                Check if all vertices are part of the same connected component
                                                and all vertices are visited during DFS and we don't have any  cycles
                                                Time: O(V + E)
                                                Space: O(V + E)
                                                """
                                                def validTree(self, n: int, edges: List[List[int]]) -> bool:
                                                    if len(edges) == 0:
                                                        return True
                                                    gr = defaultdict(list)
                                                    for a, b in edges:
                                                        gr[a].append(b)
                                                        gr[b].append(a)
    
                                                    seen = set()
                                                    st = []
    
                                                    def dfs(v, p):
                                                        seen.add(v)
                                                        st.append(v)
                                                        for n in gr[v]:
                                                            if n not in seen:
                                                                if not dfs(n, v):
                                                                    return False
                                                            elif n in seen and n in st and n != p:
                                                                return False
                                                        st.pop()
                                                        return True
                                                    cycle = dfs(0, -1)
                                                    for v in range(n):
                                                        if v not in seen:
                                                            return False
                                                    return cycle
                                         
                                    
    323. Number of Connected Components In An Undirected Graph
                                        
                                            from collections import defaultdict
                                            class Solution:
                                                """
                                                Run a dfs for each unvisited vertex and increment the 
                                                number of connected components
                                                Time: O(V + E)
                                                Space: O(V + E)
                                                """
                                                def countComponents(self, n: int, edges: List[List[int]]) -> int:
                                                    gr = defaultdict(list)
                                                    for a, b in edges:
                                                        gr[a].append(b)
                                                        gr[b].append(a)
    
                                                    seen = set()
                                                    cnt = 0
    
                                                    def dfs(v):
                                                        seen.add(v)
                                                        for n in gr[v]:
                                                            if n not in seen:
                                                                dfs(n)
                                                    for v in range(n):
                                                        if v not in seen:
                                                            cnt += 1
                                                            dfs(v)
                                                    return cnt
                                         
                                    
    684. Redundant Connection FIRST APPROACH NAIVE DFS
                                        
                                            from collections import defaultdict
                                            class Solution:
                                                """
                                                Naive approach: remove every single edge from the end to the beggining
                                                of edges and check if the graph is still connected in that case return
                                                the removed edge
                                                Time: O(E * (V + E))
                                                Space: O(V + E)
                                                """
                                                def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
                                                    gr = defaultdict(list)
                                                    n = len(edges)
                                                    seen = set()
                                                    for a, b in edges:
                                                        gr[a].append(b)
                                                        gr[b].append(a)
    
                                                    def dfs(v):
                                                        seen.add(v)
                                                        for n in gr[v]:
                                                            if n not in seen:
                                                                dfs(n)
                                                    
                                                    for i in range(n - 1, -1, -1):
                                                        seen.clear()
                                                        a, b = edges[i]
                                                        gr[a].remove(b)
                                                        gr[b].remove(a)
                                                        dfs(1)
                                                        if len(seen) == n:
                                                            return [a,b] 
                                                        gr[a].append(b)
                                                        gr[b].append(a)
                                         
                                    
    SECOND APPROACH OPTIMAL DFS
                                        
                                            from collections import defaultdict
                                            class Solution:
                                                """
                                                Optimal Approach: Run a DFS from the first node 
                                                If the node is visited, then it represents the start of a cycle
                                                Otherwise run through all the neightbours and keep a hash with
                                                all the vertices which are part of a cycle.
                                                Traverse edges in reversed order, if the nodes of the current 
                                                edge are both part of a cycle then return the current edge
                                                Time: O(V + E)
                                                Space: O(V + E)
                                                """
                                                def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
                                                    n = len(edges)
                                                    gr = defaultdict(list)
                                                    for a, b in edges:
                                                        gr[a].append(b)
                                                        gr[b].append(a)
    
                                                    seen = set()
                                                    cycle = set() 
                                                    cycle_start = -1
    
                                                    def dfs(v, p):
                                                        nonlocal cycle_start
                                                        if v in seen:
                                                            cycle_start = v
                                                            return True
    
                                                        seen.add(v)
                                                        for n in gr[v]:
                                                            if n == p:
                                                                continue
                                                            if dfs(n, v):
                                                                if cycle_start != -1:
                                                                    cycle.add(v)
                                                                if cycle_start == v:
                                                                    cycle_start = -1
                                                                return True
                                                        return False
    
                                                    dfs(1, -1)
    
                                                    for a, b in reversed(edges):
                                                        print(a, b, a in cycle, b in cycle)
                                                        if a in cycle and b in cycle:
                                                            return [a,b]
                                                    return []
                                        
                                    
    127. Word Ladder FIRST APPROACH NAIVE BFS
                                        
                                            from collections import defaultdict, deque
                                            class Solution:
                                                """
                                                BFS
                                                """
                                                def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
                                                    gr = defaultdict(list)
                                                    for i in range(len(wordList)):
                                                        cnt_diff = 0
                                                        for j in range(len(beginWord)):
                                                            if beginWord[j] != wordList[i][j]:
                                                                cnt_diff += 1
                                                        if cnt_diff == 1:
                                                            gr[0].append(i + 1)
                                                            gr[i + 1].append(0)
    
                                                    source = 0
                                                    dest = -1
    
                                                    for i in range(len(wordList)):
                                                        if wordList[i] == endWord:
                                                            dest = i + 1
                                                        for j in range(len(wordList)):
                                                            if i != j:
                                                                cnt_diff = 0
                                                                for z in range(len(wordList[i])):
                                                                    if wordList[i][z] != wordList[j][z]:
                                                                        cnt_diff += 1
                                                                if cnt_diff == 1:
                                                                    gr[i + 1].append(j + 1)
                                                                    gr[j + 1].append(i + 1)
                                                    if dest == -1:
                                                        return 0
                                                    
                                                    q = deque()
                                                    q.append(source)
                                                    n = len(gr.keys())
                                                    if dest == -1 or n == 0:
                                                        return 0
                                                    seen = [0] * 5005
                                                    seen[source] = 1
    
                                                    while q:
                                                        v = q.popleft()
                                                        for ng in gr[v]:
                                                            if seen[ng] == 0:
                                                                seen[ng] = seen[v] + 1
                                                                q.append(ng)
    
                                                    if dest < len(seen):
                                                        return seen[dest]
                                                    return 0