def checkValidString(s: str) -> bool:
    low = high = 0  # low: min open count, high: max open count
    
    for char in s:
        if char == '(':
            low += 1
            high += 1
        elif char == ')':
            low = max(0, low - 1)  # Decrease open count but not below zero
            high -= 1
        else:  # '*'
            low = max(0, low - 1)  # Treat '*' as ')'
            high += 1  # Treat '*' as '('
        
        if high < 0:  # Too many ')', invalid
            return False
    
    return low == 0  # If low is zero, valid parentheses

# Test cases
print(checkValidString("()"))     # True
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True

▎Explanation

We keep track of the possible range of open parentheses using low and high:  

• low (minimum open count) decreases when ')' appears but never goes below 0.  

• high (maximum open count) increases when '(' or '*' (treated as '(') appears.  

• If high becomes negative at any point, the string is invalid.  

• Finally, if low == 0, the string is valid.  

🚀 Time Complexity: O(n)  
🔹 Space Complexity: O(1)

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