class QuadTreeNode:
    def __init__(self, color=None, children=None):
        self.color = color  # 'black', 'white', or None
        self.children = children  # List of 4 children (top-left, top-right, bottom-left, bottom-right)


def black_area(node, size=1.0):
    if node.color == 'black':
        return size * size
    if node.color == 'white':
        return 0

    # If not leaf node, recursively calculate area for each child
    area = 0
    for child in node.children:
        area += black_area(child, size / 2)
    return area


# Example Usage:
# Creating a simple quadtree structure:
# Root node is gray (has children), divided into four quadrants.
# Top-left quadrant is completely black.
# Top-right quadrant is completely white.
# Bottom-left quadrant is divided further into four, with one black child.
# Bottom-right quadrant is white.

root = QuadTreeNode(children=[
    QuadTreeNode(color='black'),  # Top-left quadrant
    QuadTreeNode(color='white'),  # Top-right quadrant
    QuadTreeNode(children=[       # Bottom-left quadrant
        QuadTreeNode(color='black'),
        QuadTreeNode(color='white'),
        QuadTreeNode(color='white'),
        QuadTreeNode(color='white')
    ]),
    QuadTreeNode(color='white')   # Bottom-right quadrant
])

# Calculate black area
print("Black Area:", black_area(root))

from typing import List, Set

class Router:
  def __init__(self, name, x, y):
    self.name=name
    self.x=x
    self.y=y

    
def distance(router1: Router, router2: Router) -> float:
    pass
   
def can_broadcast(routers: List[Router], source: str, destination: str, range: int) -> bool:
   ''' Docstring '''
    # edge cases
    if len(ronters) < 2:
        raise ValueError('The num of routers has to be at least 2')
    if not isinstance(source, str) or not isinstance(destination, str):
        raise ValueError('Source and destination should be of type string')
    if not isinstance(range, int):
        raise ValueError('Range should be of type integet')
    if source not in [item.name for item in routers] or destination not in [item.name for item in routers]:
        raise ValueError('The names of routers should be in the list')
   
    # map to facilitate iteration
    router_map = {router.name: router for router in routers}
   
    def dfs(current_router: Router, visited: Set[Router]) -> bool:
        ''' Docstring'''
        if current_router.name == destination:
            return True
     
        # mark current router as bisited
        visited.add(current_router.name)

        # iterate over other routers
        for router in routers:
        if router.name not in visited:
            if dfs(router, visited) and distance(current_router, router) <= range:
                return True

        return False     
     
    return dfs(router_map[source], set())
 
can_broadcat([Router('A', 0, 1), Router('B', 5, 10)], 'A', ' B', 10)

# time c. O(n), space c. O(1)
def maxArea(height):
        res = 0
        l = 0
        r = len(height) - 1
        while l < r:
            res = max(res, min(height[l], height[r])*(r-l))
            if height[l] <= height[r]:
                l += 1
            else:
                r -= 1
        return res
        
height = [1,8,6,2,5,4,8,3,8]
maxArea(height)

# easy solution (passed). Time / space c. O(n+m)
def backspaceCompare(s, t):

    if not s and not t:
        return True

    def mod_str(string):
        stack = []
        for c in string:
            if not c == '#':
                stack.append(c)
            else:
                if stack:
                    stack.pop()
        return stack

    return mod_str(s) == mod_str(t)


strings = [ ("ab#c", "ad#c"), ("ab##", "c#d#"), ("a#c","b"),]
for s, t in strings:
    print( backspaceCompare(s, t) )    # True, True, False

# Leetcode solution: they claim it's space c. O(1), but both F(S) and F(T) return a list
import itertools

def backspaceCompare(S, T):
    def F(S):
        skip = 0
        for x in reversed(S):
            if x == '#':
                skip += 1
            elif skip:
                skip -= 1
            else:
                yield x

    return all(x == y for x, y in itertools.zip_longest(F(S), F(T)))

s = "ab#c"
t = "ad#c"
backspaceCompare(s, t)

def threeSum(nums: List[int]) -> List[List[int]]:
    '''
        My accepted solution
        Your runtime beats 93.44% of python3 submissions
        Your memory usage beats 98.69 % of python3 submissions
    '''
    if not isinstance(nums, list):
        return None
    n = len(nums)
    if n < 3:
        return []
    nums.sort()        
    res = set()                                               # helps avoid duplicates and decrease scpace complexity

    for i in range( n-1 ):
                
        # If current value > 0, break as the sum > 0
        if nums[i] > 0:
            break
        # It's a duplicate; helps reduce complexity
        if i > 0 and nums[i] == nums[i-1]:    
            continue
                        
        l = i+1
        r = n-1

        while l < r:
            sum_ = nums[i] + nums[l] + nums[r]
            if sum_ < 0:
                l += 1
            elif sum_ > 0:
                r -= 1
            else:             
                res.add( (nums[i], nums[l], nums[r]) )
                l += 1
                r -= 1
                
            # Skip duplicates for the second and third elements
            while l < r and nums[l] == nums[l - 1]:
                l += 1
            while l < r and nums[r] == nums[r + 1]:
                r -= 1

    return list(res)


a1 = [-1, 0, 1, 2, -1, -4]
a2 = []
a3 = [0]

for a in [a1, a2, a3]:
    print( threeSum(a) )

def lengthOfLongestSubstring(s: str) -> int:
    ''' My Solution (Accepted)
        Iterate over each char in string with some logic    
    '''    
    
    curr, max_ = '', ''
    for idx, c in enumerate(s):
        if not curr:                             # add current char if curr is empty
            curr = c                        
        elif curr and c not in curr:             # add current char if it's not in curr
            curr += c
        elif curr and curr[-1] == c:             # reset curr if current char is also the last one in curr
            curr = c
        else:                                    # current char in curr, but not the last one - find its index in s,
            temp_idx = idx - 1                   # but not in curr(!) because curr may be shorter. Make curr include 
            while s[temp_idx] != c:              # everyting after (because there is no c) + c at current idx
                temp_idx -= 1
            curr = s[temp_idx+1 : idx+1]

        max_ = max(curr, max_, key=len)
                
    return len(max_)


def lengthOfLongestSubstring2(s: str) -> int:
    '''LeetCode solution beautified by me
       We use HashSet to store the characters in current window [i,j) (j = i initially).
       Then we slide the index j to the right. If it is not in the HashSet, we slide j further.
       Doing so until s[j] is already in the HashSet. At this point, we found the maximum size
       of substrings without duplicate characters start with index i.
       If we do this for all i, we get our answer
    '''
    mapp = {c:0 for c in s}
    left = 0
    max_len = 0
    for right, c in enumerate(s):
        mapp[c] += 1
        while mapp[c] > 1:
            mapp[ s[left] ] -= 1                 # first this, then l += 1
            left += 1
        max_len = max(max_len, right - left + 1)

    return max_len

    
s1 = 'abcbacbb'
s2 = 'bbbbb'
s3 = 'pwwkew'
s4 = ''

# 3,1,3,0
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring(s), end=', ' )
    
print()    
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring2(s), end=', ' )

def nextPermutation(nums: List[int]) -> None:
    '''
        Runtime: 32 ms, faster than 98.61% of Python3 online submissions for Next Permutation
        Memory Usage: 14.3 MB, less than 19.08% of Python3 submissions - IN PLACE, WHAT MEMORY USAGE?
    '''    
    i = len(nums)-2
    while i >= 0 and nums[i+1] <= nums[i]:      # find first nums[i] from right that's > than its right neighbor
        i -= 1
    
    if i >= 0:
        j = len(nums)-1                         # find first nums[j] from right that's > than nums[i]
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]     # swap them
    
    reverse(nums, i+1)                          # all nums to right of nums[i] are in non-incresing oder -
                                                # reverse them for next lexicographical permutation

def reverse( nums: List[int], start: int) -> None:
        
    i, j = start, len(nums)-1
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1
        
a1 = [1,2,3]
a2 = [3,2,1]
a3 = [1,1,5]
a4 = [1]

for a in [a1, a2, a3, a4]:
    nextPermutation(a)
    print(a)

# My solution (no Leetcode solution).
# Time c. O(len(s)) + O(len(w1) + len(w2) +... + len(unique(w1)) + len(unique(w2)) + ...)) = linear?
# Space c. O(sum of len of unique chars in each word) = linear
def expressiveWords(s, words):

    def unique_chars(string):
        chars = []
        for c in string:
            if not chars:
                chars.append([c, 1])
            elif c == chars[-1][0]:
                chars[-1][1] += 1
            else:
                chars.append([c, 1])
        return chars

    res = 0
    chars_s = unique_chars(s)
    for w in words:
        chars_w = unique_chars(w)
        if [i[0] for i in chars_s] == [j[0] for j in chars_w]:
            include = True
            for k in range(len(chars_s)):
                if chars_s[k][1]<3 and chars_s[k][1] != chars_w[k][1]:    # can't make a stretchy word in this case
                    include = False
                    break
                if chars_s[k][1] < chars_w[k][1]:                # can't make a stretchy word in this case
                    include = False
                    break
            if include:
                res += 1

    return res

s = "heeellooo"
words = ["hello", "hi", "helo"]
expressiveWords(s, words)

# Time c. O(n), space c. O(1)
# At most k distinct characters
def LongestSubstring(s, k):
    n = len(s)
    if n*k==0:
        return 0
    l, r = 0, 0
    mapp = dict()
    max_len = 2
    for c in s:
        mapp[ s[r] ] = r
        r += 1
        if len(mapp) == k+1:
            del_idx = min(mapp.values())
            del mapp[ s[del_idx] ]
            l = del_idx + 1
        max_len = max(max_len, r - l)
    return max_len


strings = ["ccaabbb", "eceba", 'ababababab', 'abababacbab']
for s in strings:
    print(LongestSubstring(s, 2))     # 5, 3

# My solution using two pointers
def lengthOfLongestSubstringTwoDistinct2(s: str, k: int=2) -> int:
        
    n = len(s)
    # edge cases
    if n < 3:
        return n
    
    # initiate variables
    l,r = 0,0
    max_len = 0
    mapp = dict()
        
    # two pointers approac
    while r < n and l <= r:
        mapp[s[r]] = mapp.get(s[r], 0) + 1
        if len(mapp) > k:
            mapp[ s[l] ] -= 1
            if mapp[ s[l] ] == 0:
                del mapp[ s[l] ]
            l += 1
        else:
            max_len = max(max_len, len(s[l:r+1]))         # r-l+1  equals  len(s[l:r+1]))
            r += 1
    return max_len


strings = ["ccaabbb", "eceba", 'ababababab', 'abababacbab']
for s in strings:
    print(lengthOfLongestSubstringTwoDistinct2(s))     # 5, 3

# greedy solution #1 OR Approach 4: Greedy (Leetcode)
# time O(n), space O(1)
def canJump(nums):
    lastPos = len(nums) - 1
    for i in range (len(nums)-1, -1, -1):
        if i + nums[i] >= lastPos:
            lastPos = i
    
    return lastPos == 0
    
nums = [2,3,1,1,4]        # True
#nums = [3,2,1,0,4]        # False
canJump(nums)

# greedy solution #2 (from comments) - LESS INTUITIVE THAN greedy solution #1
# time O(n), space O(1)
def canJump(nums):
    
    if not nums:
        return False
    i = 0
    max_index = nums[i]
    while i < len(nums) and i <= max_index:
        new_index = i + nums[i]
        max_index = max(max_index, new_index)
        i += 1
                
    return True if i==len(nums) else False
    
nums = [2,3,1,1,4]        # True
#nums = [3,2,1,0,4]        # False
canJump(nums)

# MY OWN RECURSIVE SOLUTION WITH MEMOIZATION!
# Time n**2, space O(n)
def canJump(nums):

    def cj_rec(curr_idx):

        if curr_idx == len(nums)-1:
            return True
        elif nums[ curr_idx ] == 0:
            return False
        res = []

        for j in range(1, nums[ curr_idx ]+1):
            new_idx = curr_idx+j
            if new_idx < len(nums):
                if not new_idx in memo:
                    memo[ new_idx ] = cj_rec( new_idx )                    
                res.append(memo[ new_idx ])

        return sum(res) > 0

    idx = 0
    memo = {}
    return cj_rec(idx)
    
nums = [2,3,1,1,4]         # True
#nums = [3,2,1,0,4]        # False
canJump(nums)

def canJump_rec(nums):
    ''' 
        My other recursive solution
        Time O(2^n) - see explanation above
        Space?
    '''
    print(nums)
    if len(nums) == 1:
        return True
    res = False
    for n in range(1,nums[0]+1):
        res = canJump_rec(nums[n:])
    return res

# Each operation is O(M): time O(2M) -> O(M), space O(1), where M=num cells in matrix or n**2
class Solution(object):
    def rotate(self, matrix):
        self.transpose(matrix)
        self.reflect(matrix)
        
    def transpose(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
                
    def reflect(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(n//2):
                matrix[i][j], matrix[i][-j-1] = matrix[i][-j-1], matrix[i][j]
                
matrix = [[1,2,3],[4,5,6],[7,8,9]]
s = Solution()
s.rotate(matrix)
print(matrix)

# time O(M), space O(1), where M=num cells in matrix or n**2
from typing import List
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix[0])
        for i in range(n // 2 + n % 2):
            for j in range(n // 2):
                tmp = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1]
                matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i]
                matrix[j][n - 1 - i] = matrix[i][j]
                matrix[i][j] = tmp
                
matrix = [[1,2,3],[4,5,6],[7,8,9]]
s = Solution()
s.rotate(matrix)
print(matrix)

# time O(n), space O(1)
def plusOne(digits):

        n = len(digits)
        for i in range(n-1, -1, -1):
            if digits[i] == 9:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
            
        return [1] + digits
    
digits = [9, 9, 9]
plusOne(digits)

# my similar solution
def plusOne2(arr):
    remainder = 1
    i = len(arr) - 1
    while remainder != 0 and i >=0:
        curr_sum = arr[i]+1
        if curr_sum < 10:
            arr[i] = curr_sum
            remainder = 0
        else:
            arr[i] = 0
            remainder = 1
        i -= 1
    if remainder:
        arr = [1] + arr          
    return arr

digits = [9,9,9,9,9]    # [1, 0, 0, 0]
plusOne2(digits)

# My accepted solution (no Leetcode solution)
# time O(n), space - assigning several variables = O(n)
def nextClosestTime1(time):
    '''
        May be incomplete because range(hours+1, 24) doesn't cover everything?
        Or min_option take care of it?
    '''        
    hours, minutes = time.split(':')                                    # O(n) for split()
    options = set(hours + minutes)
    min_option = min(options)                                           # O(n)
    hours, minutes = int(hours), int(minutes)                           # O(n) for int(str)

    for i in range(minutes+1, 60):                                     # max 59 times
        if all(c in options for c in str(i)):                    # 59 * 2 digits * 4 * O(n) for str(int) = O(n)
            minute_part = str(i) if i > 9 else '0'+str(i)        # O(n) for str(i)
            return time[:3] + minute_part

    for i in range(hours+1, 24):
        if all(c in options for c in str(i)):
            hour_part = str(i) if i > 9 else '0'+str(i)
            minute_part = min_option + min_option
            return hour_part + ':' + minute_part

    return min_option + min_option + ':' + min_option + min_option
    
    
# time O(n), space - assigning several variables = O(n)
def nextClosestTime(time):
    '''
        Is this more complete?    
    '''    
    hour, minute = [int(i) for i in time.split(':')]            # O(n) for split()
        
    # special case - minutes within the same hour
    for j in range(minute+1, 60):                               # O(n)
        m = str(j)
        m = '0' + m if len(m) == 1 else m
        if all(c in time for c in list(m)):                     # O(len(m)*n) = O(n)
            return time[:3] + m
    
    # handle other cases - or min_option will suffice?
    found_hour = False
    for i in list(range(hour+1, 24)) + list(range(hour)):       # same as above O(n) estimates
        h = str(i)
        h = '0' + h if len(h) == 1 else h
        if all(c in time for c in list(h)):
            found_hour = True
            res = h + ':'
        if found_hour:
            for j in range(0, 60):
                m = str(j)
                m = '0' + m if len(m) == 1 else m
                if all(c in time for c in list(m)):
                    return res + m
            
    return None    

    
times = ["19:34", "23:59"]
for time in times:
    print(nextClosestTime(time))

# same idea from comments
def nextClosestTime(time):
    digits = [int(y) for x in time.split(':') for y in x]
    h, m = time.split(':')
    while True:
        h, m = (str(int(h)+1), '00') if int(m) == 59 else (h, str(int(m)+1))
        h = '00' if int(h) > 23 else h
        h = '0' + h if len(h) == 1 else h
        m = '0' + m if len(m) == 1 else m
        if all([int(x) in digits for x in h+m]):
            return h + ':' + m
        
times = ["19:34", "23:59"]
for time in times:
    print(nextClosestTime(time))

# My solution: time / space O(n)
def findMissingRanges(nums, lower, upper):
        
    if not nums:
        if lower == upper:
            return [str(upper)]
        else:
            return [str(lower) + '->' + str(upper)]
    elif lower == upper and lower == nums[0]:
        return []

    nums2 = list(range(lower, upper+1))
    for idx, i in enumerate(nums2):
        if i in nums:
            nums2[i] = ':'
    nums2 = ' '.join(map(str, nums2))
    nums2 = [ i.strip() for i in nums2.split(':') if i.strip() ]
    stack = []
    for i in nums2:
        i = i.strip().split()
        if len(i) == 1:
            stack.append(i[0])
        else:
            stack.append(i[0] + '->' + i[-1])    
    return stack


# edge cases on website include empty and one-element arrays, sometimes upper or lower overlap with single elem
nums = [0,1,3,50,75]
lower = 0
upper = 99
findMissingRanges(nums, lower, upper)

# More elegant approach (Leetcode)
def findMissingRanges(nums, lower, upper):
        
        def formatRange(lower, upper):
            if lower == upper:
                return str(lower)
            return str(lower) + "->" + str(upper)

        result = []
        prev = lower - 1
        for i in range(len(nums) + 1):
            curr = nums[i] if i < len(nums) else upper + 1
            if prev + 1 <= curr - 1:
                result.append(formatRange(prev + 1, curr - 1))
            prev = curr
        return result
    
# edge cases on website include empty and one-element arrays, sometimes upper or lower overlap with single elem
nums = [0,1,3,50,75]
lower = 0
upper = 99
findMissingRanges(nums, lower, upper)

# My solution (accepted)
def findReplaceString(s, indices, sources, targets):

    # exclude targets that don't exist in string
    # collect ranges (start, end index) for remaining sources
    to_discard = []
    full_indices = []
    for i, start in enumerate(indices):
        end = start + len(sources[i])
        if not s[start:end] == sources[i]:
            to_discard.append(i)
        else:
            full_indices.append([start, end])                
    if len(to_discard) == len(indices):
        return s
    targets = [elem for idx, elem in enumerate(targets) if idx not in to_discard]

    # merge ranges and target for convenience and sort (indices are unsorted!)
    for i in range(len(full_indices)):
        full_indices[i].append(targets[i])
    full_indices.sort()

    # fill result w/slices of string or targets
    res = []
    if full_indices[0][0] != 0:
        res.append(s[ :full_indices[0][0] ])
    for i in range(1, len(full_indices)):
        res.append( full_indices[i-1][2] )
        res.append(s[ full_indices[i-1][1] : full_indices[i][0] ])
    res.append(full_indices[-1][2])
    if full_indices[-1][1] != len(s):
        res.append(s[ full_indices[-1][1] : ])

    return ''.join(res)

s = "abcd"
indices = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]
findReplaceString(s, indices, sources, targets)

# my more concise solution
# time and space c. O(n)
from typing import List

def findReplaceString2(s: str, indices: List[int], sources: List[str], targets: List[str]):
        
    # edge cases
    if not s:
        return s
    assert len(indices) == len(sources) == len(targets), 'Lengths must be the same'
    if not indices:
        return s
        
    # determine valid indices
    valid_idxs = [i for i in range(len(indices)) if sources[i] in s[ indices[i]: ]]
    
    # remove invalid elements
    indices = [ value for idx, value in enumerate(indices) if idx in valid_idxs ]
    sources = [ value for idx, value in enumerate(sources) if idx in valid_idxs ]
    targets = [ value for idx, value in enumerate(targets) if idx in valid_idxs ]
    
    # get index ranges for valid sources
    ranges = []
    for k in range(len(indices)):
        start = indices[k]
        end   = start + len( sources[k] )
        ranges.append([start, end])
          
    # final result - smart iteration over ranges
    res = []
    for idx, r in enumerate(ranges):
        res.append(targets[idx])
        if idx < len(ranges)-1:
            res.append(s[ r[1]:ranges[idx+1][0] ])
        elif idx == len(ranges)-1 and r[1] != len(s):
            res.append(s[ r[1]:len(s)])
    return ''.join(res)

# shorter solution from comments (accepted)
def findReplaceString3(S, indexes, sources, targets):    
    for i, s, t in sorted(zip(indexes, sources, targets), reverse=True):
        S = S[:i] + t + S[i + len(s):] if S[i:i + len(s)] == s else S
    return S

s = "abcd"
indices = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]
print(findReplaceString(s, indices, sources, targets))    # 'eeebffff'

s = "abcd"
indices = [0, 2]
sources = ["a", "ec"]
targets = ["eee", "ffff"]
print(findReplaceString(s, indices, sources, targets))    # 'eeebcd'

# My solution
import math
from typing import List


def maxDistToClosest(seats: List[int]) -> int:
    max_dist = 0
    persons  = [idx for idx, num in enumerate(seats) if num==1]
    res      = [ math.ceil(abs(persons[i] - persons[i-1])/2) for i in range(1,len(persons)) ]
    if persons[0] != 0:
        res.append(persons[0])        
    if persons[-1] != len(seats)-1:
        res.append(abs(len(seats)-1 - persons[-1]))
    return max(res)


seats_all = [ [1,0,0,0,1,0,1], [1,0,0,0], [0,1] ]
for seats in seats_all:
    print(maxDistToClosest(seats))

def maxDistToClosest(seats):
    people = (i for i, seat in enumerate(seats) if seat)
    prev, future = None, next(people)

    ans = 0
    for i, seat in enumerate(seats):
        if seat:
            prev = i
        else:
            while future is not None and future < i:
                future = next(people, None)

            left = float('inf') if prev is None else i - prev
            right = float('inf') if future is None else future - i
            ans = max(ans, min(left, right))

    return ans

seats_all = [ [1,0,0,0,1,0,1], [1,0,0,0], [0,1] ]
for seats in seats_all:
    print(maxDistToClosest(seats))

# time c. = O(Nlogk), where k = # linked lists. Space c. = O(1)
class Node:
    def __init__(self, data):
        self.val  = data
        self.next = None


# time c. O(Nlogk), k = # lists. Space c. O(1)
def mergeKLists(lists):
    n = len(lists)
    interval = 1
    while interval < n:
        for i in range( 0, n-interval,
                        interval*2 ):
            lists[i] = merge2Lists( lists[i],
                                    lists[i+interval] )
        interval *= 2
    return lists[0] if n > 0 else None

def merge2Lists(l1, l2):
    head = point = Node(0)
    while l1 and l2:
        if l1.val <= l2.val:
            point.next = l1
            l1 = l1.next
        else:
            point.next = l2
            l2 = l1
            l1 = point.next.next
        point = point.next
    if not l1: point.next=l2
    else: point.next=l1
    return head.next


def printList(node):
    while node != None:
        print(node.val, end=" ")
        node = node.next
    print()

N = 3
a = [None] * N
# Linkedlist1
head1 = Node(1)
a[0] = head1
head1.next = Node(3)
head1.next.next = Node(5)
head1.next.next.next = Node(7)
# Limkedlist2
head2 = Node(2)
a[1] = head2
head2.next = Node(4)
head2.next.next = Node(6)
head2.next.next.next = Node(8)
# Linkedlist3
head3 = Node(0)
a[2] = head3
head3.next = Node(9)
head3.next.next = Node(10)
head3.next.next.next = Node(11)
res = mergeKLists(a)
if res != None:
    printList(res)

n = 11
interval = 1
while interval < n:
    for i in range(0, n - interval, interval * 2):
        print(i, interval)
    interval *= 2

# time c. O(kN*Logk) since
# using heap (N*Logk) k times;
# space c. O(N) - output array
from heapq import merge
def mergeK(arr, k):
    l = arr[0]
    for i in range(k-1):
        l = list(merge(l, arr[i + 1]))
    return l


arr =[ [2, 6, 12 ], 
       [ 1, 9 ],
       [23, 34, 90, 2000 ], ]
l = mergeK(arr, len(arr))
printArray(l)

# time = space = O(n) BETTER TO UNDERSTAND
def max_water(height):
    res = 0
    n = len(height)
    left = [0]*n                                   # left[i] = height tallest bar to left of i'th bar incl. self
    right = [0]*n                                  # right[i] = height tallest bar to right of ith bar incl. self
        
    left[0] = height[0]                                                # pre-fill left arr
    for i in range(1, n):
        left[i] = max(left[i-1], height[i])
      
    right[n-1] = height[n-1]                                           # pre-fill right arr
    for i in range(n-2, -1, -1):
        right[i] = max(right[i+1], height[i])    
    
    for i in range(n):                                                 # amount of water accumulated on i'th bar
        res += min(left[i], right[i]) - height[i]
  
    return res

# time = space = O(n)
def max_water2(height):
    stack = []                                                                      # to store indices    
    n = len(height)
    ans = 0  
    for i in range(n):        
        while stack and height[ stack[-1] ] < height[i]:                # remove bars until condition holds    
            pop_height = height[stack.pop()]                                        # store height of top bar
            if(len(stack) == 0):                                      # If no bars or popped bar has no left boundary
                break            
            distance = i - stack[-1] - 1                              # dist. betw. left & right bounds of popped bar
            min_height = min(height[stack[-1]], height[i])-pop_height               # calculate min height  
            ans += distance * min_height  
        
        stack.append(i)                                  # If stack empty or height of current bar <= stack's top bar  
    return ans

numss = [ [0,1,0,2,1,0,1,3,2,1,2,1], [4,2,0,3,2,5] ]
for nums in numss:
    print( max_water(nums) )

# time = O(n), space = O(1)
def findKthLargest(nums, k):
    def partition(left, right, pivot_idx):
        pivot = nums[pivot_idx]
        # 1. move pivot to end
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        # 2. move all smaller elements to the left
        store_idx = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[store_idx], nums[i] = nums[i], nums[store_idx]
                store_idx += 1
        # 3. move pivot to its final place
        nums[right], nums[store_idx] = nums[store_idx], nums[right]
        return store_idx

    def select_rec(left, right, k_smallest):
        if left == right:    # base case - 1 elem
            return nums[left]
        pivot_idx = random.randint(left, right)
        # find pivot pos in sorted list
        pivot_idx = partition(left, right, pivot_idx)
        # if pivot in final sorted position
        if k_smallest == pivot_idx:
             return nums[k_smallest]        
        elif k_smallest < pivot_idx:    # go left
            return select_rec(left, pivot_idx-1, k_smallest)        
        else:                           # go right
            return select_rec(pivot_idx+1, right, k_smallest)
    # kth largest = (n - k)th smallest 
    return select_rec(0, len(nums)-1, len(nums)-k)

# time = O(NlogN), space = O(N)
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        
        # If there are no meetings, we don't need any rooms.
        if not intervals:
            return 0

        used_rooms = 0

        # Separate out the start and the end timings and sort them individually.
        start_timings = sorted([i[0] for i in intervals])
        end_timings = sorted(i[1] for i in intervals)
        L = len(intervals)

        # The two pointers in the algorithm: e_ptr and s_ptr.
        end_pointer = 0
        start_pointer = 0

        # Until all the meetings have been processed
        while start_pointer < L:
            # If there is a meeting that has ended by the time the meeting at `start_pointer` starts
            if start_timings[start_pointer] >= end_timings[end_pointer]:
                # Free up a room and increment the end_pointer.
                used_rooms -= 1
                end_pointer += 1

            # We do this irrespective of whether a room frees up or not.
            # If a room got free, then this used_rooms += 1 wouldn't have any effect. used_rooms would
            # remain the same in that case. If no room was free, then this would increase used_rooms
            used_rooms += 1    
            start_pointer += 1   

        return used_rooms

# time = O(NlogN), space = O(N)
class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        from fractions import Fraction
        workers = sorted((Fraction(w, q), q, w)
                         for q, w in zip(quality, wage))

        ans = float('inf')
        pool = []
        sumq = 0
        for ratio, q, w in workers:
            heapq.heappush(pool, -q)
            sumq += q

            if len(pool) > K:
                sumq += heapq.heappop(pool)

            if len(pool) == K:
                ans = min(ans, ratio * sumq)

        return float(ans)

# time = space = O(N)
class Solution(object):
    def kClosest(self, points, K):
        dist = lambda i: points[i][0]**2 + points[i][1]**2

        def sort(i, j, K):
            # Partially sorts A[i:j+1] so the first K elements are
            # the smallest K elements.
            if i >= j: return

            # Put random element as A[i] - this is the pivot
            k = random.randint(i, j)
            points[i], points[k] = points[k], points[i]

            mid = partition(i, j)
            if K < mid - i + 1:
                sort(i, mid - 1, K)
            elif K > mid - i + 1:
                sort(mid + 1, j, K - (mid - i + 1))

        def partition(i, j):
            # Partition by pivot A[i], returning an index mid
            # such that A[i] <= A[mid] <= A[j] for i < mid < j.
            oi = i
            pivot = dist(i)
            i += 1

            while True:
                while i < j and dist(i) < pivot:
                    i += 1
                while i <= j and dist(j) >= pivot:
                    j -= 1
                if i >= j: break
                points[i], points[j] = points[j], points[i]

            points[oi], points[j] = points[j], points[oi]
            return j

        sort(0, len(points) - 1, K)
        return points[:K]

# time = O(n), space =O(1)
def removeNthFromEnd(head: Node, n: int) -> Node:
    curr = head
    for i in range(n+1):
        if not curr:
            print('List shorter than', n)
        curr = curr.next
    curr2 = head
    while curr:
        curr = curr.next
        curr2 = curr2.next
    to_delete = curr2.next
    curr2.next = curr2.next.next
    to_delete.next = None
    return head

# time c. O(n); posted by one of the users in Solutions
from collections import deque

def ladderLength(beginWord, endWord, wordList):
    
    if endWord not in wordList or not endWord or not beginWord or not wordList:
        return 0

    def construct_dict(word_list):
        d = {}
        for word in word_list:
            for i in range(len(word)):
                s = word[:i] + "_" + word[i+1:]
                d[s] = d.get(s, []) + [word]
        return d

    def bfs_words(begin, end, dict_words):
        queue, visited = deque([(begin, 1)]), set()
        while queue:
            word, steps = queue.popleft()
            if word not in visited:
                visited.add(word)
                if word == end:
                    return steps
                for i in range(len(word)):
                    s = word[:i] + "_" + word[i+1:]
                    neigh_words = dict_words.get(s, [])
                    for neigh in neigh_words:
                        if neigh not in visited:
                            queue.append((neigh, steps + 1))
        return 0

    d = construct_dict( set(wordList) | set([beginWord]))        # beginWord may not be in the wordList
    return bfs_words(beginWord, endWord, d)

# official? looks complicated - the above solution from users' Solutions looks prettier
# time = space = O(M×N), where M = length of words, N = total # words in input
from collections import defaultdict
class Solution(object):
    def __init__(self):
        self.length = 0
        # Dictionary to hold combination of words that can be formed,
        # from any given word. By changing one letter at a time.
        self.all_combo_dict = defaultdict(list)

    def visitWordNode(self, queue, visited, others_visited):
        queue_size = len(queue)
        for _ in range(queue_size):
            current_word = queue.popleft()
            for i in range(self.length):
                # Intermediate words for current word
                intermediate_word = current_word[:i] + "*" + current_word[i+1:]

                # Next states are all the words which share the same intermediate state.
                for word in self.all_combo_dict[intermediate_word]:
                    # If the intermediate state/word has already been visited from the
                    # other parallel traversal this means we have found the answer.
                    if word in others_visited:
                        return visited[current_word] + others_visited[word]
                    if word not in visited:
                        # Save the level as the value of the dictionary, to save number of hops.
                        visited[word] = visited[current_word] + 1
                        queue.append(word)
                        
        return None

    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        # Since all words are of same length.
        self.length = len(beginWord)

        for word in wordList:
            for i in range(self.length):
                # Key is the generic word
                # Value is a list of words which have the same intermediate generic word.
                self.all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)

        # Queues for birdirectional BFS
        queue_begin = collections.deque([beginWord]) # BFS starting from beginWord
        queue_end = collections.deque([endWord]) # BFS starting from endWord

        # Visited to make sure we don't repeat processing same word
        visited_begin = {beginWord : 1}
        visited_end = {endWord : 1}
        ans = None

        # We do a birdirectional search starting one pointer from begin
        # word and one pointer from end word. Hopping one by one.
        while queue_begin and queue_end:
            
            # Progress forward one step from the shorter queue
            if len(queue_begin) <= len(queue_end):
                ans = self.visitWordNode(queue_begin, visited_begin, visited_end)
            else:
                ans = self.visitWordNode(queue_end, visited_end, visited_begin)
            if ans:
                return ans

        return 0

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print( ladderLength(beginWord, endWord, wordList) )

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
print( ladderLength(beginWord, endWord, wordList) )

import collections

s = Solution()
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
print( s.ladderLength(beginWord, endWord, wordList) )

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
print( s.ladderLength(beginWord, endWord, wordList) )

# time = space = O(V+E)
from collections import defaultdict, deque
class Solution:

    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        # Prepare the graph
        adj_list = defaultdict(list)
        indegree = {}
        for dest, src in prerequisites:
            adj_list[src].append(dest)

            # Record each node's in-degree
            indegree[dest] = indegree.get(dest, 0) + 1

        # Queue for maintainig list of nodes that have 0 in-degree
        zero_indegree_queue = deque([k for k in range(numCourses) if k not in indegree])

        topological_sorted_order = []

        # Until there are nodes in the Q
        while zero_indegree_queue:

            # Pop one node with 0 in-degree
            vertex = zero_indegree_queue.popleft()
            topological_sorted_order.append(vertex)

            # Reduce in-degree for all the neighbors
            if vertex in adj_list:
                for neighbor in adj_list[vertex]:
                    indegree[neighbor] -= 1

                    # Add neighbor to Q if in-degree becomes 0
                    if indegree[neighbor] == 0:
                        zero_indegree_queue.append(neighbor)

        return topological_sorted_order if len(topological_sorted_order) == numCourses else []

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
print(findOrder(numCourses, prerequisites))

# time = O(n), space = O(d)=O(logN) to keep the recursion stack, where d is a tree depth
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        return 1 + self.countNodes(root.right) + self.countNodes(root.left) if root else 0

# time = O(d^2)=O((logN)^2), where d is a tree depth, Space = O(1)
class Solution:
    def compute_depth(self, node: TreeNode) -> int:
        """
        Return tree depth in O(d) time.
        """
        d = 0
        while node.left:
            node = node.left
            d += 1
        return d

    def exists(self, idx: int, d: int, node: TreeNode) -> bool:
        """
        Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
        Return True if last level node idx exists. 
        Binary search with O(d) complexity.
        """
        left, right = 0, 2**d - 1
        for _ in range(d):
            pivot = left + (right - left) // 2
            if idx <= pivot:
                node = node.left
                right = pivot
            else:
                node = node.right
                left = pivot + 1
        return node is not None
        
    def countNodes(self, root: TreeNode) -> int:
        # if the tree is empty
        if not root:
            return 0
        
        d = self.compute_depth(root)
        # if the tree contains 1 node
        if d == 0:
            return 1
        
        # Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
        # Perform binary search to check how many nodes exist.
        left, right = 1, 2**d - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if self.exists(pivot, d, root):
                left = pivot + 1
            else:
                right = pivot - 1
        
        # The tree contains 2**d - 1 nodes on the first (d - 1) levels
        # and left nodes on the last level.
        return (2**d - 1) + left