class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0
        miss = 1
        i = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1
        return patches

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # Give every child 1 candy initially

        # Left-to-right pass: if a child has a higher rating than the left neighbor, give one more candy
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Right-to-left pass: if a child has a higher rating than the right neighbor, ensure they have more candy
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:


        def helper(qu):
            if not qu:
                return 

            i = len(qu)
            temp = []
            nextsize = 0
       
            
            while i > 0 :
                poped = qu.popleft()
                temp.append(poped.val)

                if poped.left:
                    qu.append(poped.left)
                    nextsize += 1

                if poped.right:
                    qu.append(poped.right)
                    nextsize += 1
                          

                i -= 1

            ans.append(temp)
            helper(qu)

        if not root:
            return []

        ans =[]
        q = deque()
        q.append(root)
        helper(q)

        return ans

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:

        def helper(qu):
            if not qu:
                return

            i = len(qu)
            leng = len(qu)
            total = 0

            while i > 0:
                poped = qu.popleft()
                total += poped.val

                if poped.left:
                    qu.append(poped.left)
                if poped.right:
                    qu.append(poped.right)            

                i -= 1
            ans.append(total/leng)
            helper(qu)
        qu = deque()
        qu.append(root)
        ans = []

        helper(qu)

        return ans