switch.

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

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        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 setZeroes(self, matrix: List[List[int]]) -> None:
        rows = len(matrix)
        cols = len(matrix[0])

        first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
        first_col_zero = any(matrix[i][0] == 0 for i in range(rows))

        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        for i in range(1, rows):
            for j in range(1, cols):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if first_row_zero:
            for j in range(cols):
                matrix[0][j] = 0

        if first_col_zero:
            for i in range(rows):
                matrix[i][0] = 0

from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: list[str]) -> list[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count

        if len(s) < total_len:
            return []

        need = Counter(words)
        ans = []
        for offset in range(word_len):
            left = offset
            right = offset
            count = 0
            window = Counter()

            while right + word_len <= len(s):
                word = s[right:right + word_len]
                right += word_len
                if word not in need:
                    window.clear()
                    count = 0
                    left = right
                    continue

                window[word] += 1
                count += 1

                while window[word] > need[word]:
                    removed = s[left:left + word_len]
                    window[removed] -= 1
                    left += word_len
                    count -= 1

                if count == word_count:
                    ans.append(left)

                    removed = s[left:left + word_len]
                    window[removed] -= 1
                    left += word_len
                    count -= 1

        return ans

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        
        n = len(matrix)
        
        #transpose
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
                
        #rev
        for i in range(n):
            matrix[i].reverse()

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == '.':
                    continue

                box_idx = (r // 3) * 3 + (c // 3)
                
                # dup check
                if val in rows[r] or val in cols[c] or val in boxes[box_idx]:
                    return False
                
                rows[r].add(val)
                cols[c].add(val)
                boxes[box_idx].add(val)
                
        return True

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        max_len = 0
        seen = set()

        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1

            seen.add(s[right])
            max_len = max(max_len, right - left + 1)

        return max_len

class Solution:
    def minSubArrayLen(self, target, nums):
        left = 0
        current_sum = 0
        min_length = float('inf')

        for right in range(len(nums)):
            current_sum += nums[right]

            while current_sum >= target:
                min_length = min(min_length, right - left + 1)
                current_sum -= nums[left]
                left += 1

        return 0 if min_length == float('inf') else min_length

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0

        while i < len(words):
            j = i
            line_length = 0

            while j < len(words):
                needed = line_length + len(words[j]) + (j - i)

                if needed > maxWidth:
                    break

                line_length += len(words[j])
                j += 1

            line_words = words[i:j]
            gaps = len(line_words) - 1

            if j == len(words) or gaps == 0:
                line = " ".join(line_words)
                line += " " * (maxWidth - len(line))

            else:
                total_spaces = maxWidth - line_length
                spaces_each = total_spaces // gaps
                extra = total_spaces % gaps

                line = ""

                for k in range(gaps):
                    line += line_words[k]
                    line += " " * spaces_each

                    if k < extra:
                        line += " "

                line += line_words[-1]

            result.append(line)
            i = j

        return result

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    left += 1
                    right -= 1

                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                elif total < 0:
                    left += 1

                else:
                    right -= 1

        return result

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0

        while left < right:
            width = right - left
            current_height = min(height[left], height[right])

            max_area = max(max_area, width * current_height)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]

            if total == target:
                return [left + 1, right + 1]

            if total < target:
                left += 1
            else:
                right -= 1

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0

        for char in t:
            if i < len(s) and s[i] == char:
                i += 1

        return i == len(s)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1

            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)

        for i in range(n - m + 1):
            if haystack[i:i + m] == needle:
                return i

        return -1

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s

        rows = [""] * numRows
        row = 0
        direction = 1

        for ch in s:
            rows[row] += ch

            if row == 0:
                direction = 1
            elif row == numRows - 1:
                direction = -1

            row += direction

        return "".join(rows)

class Solution:
    def reverseWords(self, s: str) -> str:
        slist=s.split()
        return " ".join(slist[::-1])
        

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]

        for i in range(len(first)):
            char = first[i]

            for s in strs[1:]:
                if i >= len(s) or s[i] != char:
                    return first[:i]

        return first

class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans=""
        v=sorted(v)
        first=v[0]
        last=v[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans 

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        # lststr=s.split()
        # return len(lststr[-1])
        i = len(s) - 1

        while i >= 0 and s[i] == " ":
            i -= 1

        length = 0

        while i >= 0 and s[i] != " ":
            length += 1
            i -= 1

        return length



        

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        words = s.strip().split()
        
        if not words:
            return 0
        
        return len(words[-1])

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [
            (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
            (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
            (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
        ]

        result = []

        for value, symbol in values:
            count, num = divmod(num, value)
            result.append(symbol * count)

        return "".join(result)

class Solution:
    def intToRoman(self, num: int) -> str:
        roman_dict = {1: "I",5: "V",4: "IV",10: "X",   9: "IX",50: "L",   40: "XL",100: "C",  90: "XC",500: "D",  400: "CD",1000: "M", 900: "CM"}
        out = ""
        for n in [1000,900,500,400,100,90,50,40,10,9,5,4,1]:
            while num >= n:
                out += roman_dict[n]
                num -= n
        return out

class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1,"V": 5,"X": 10,"L": 50,"C": 100,"D": 500,"M": 1000}

        total = 0

        for i in range(len(s)):
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]

        return total

class Solution:
    def romanToInt(self, s: str) -> int:
        m = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        
        ans = 0
        
        for i in range(len(s)):
            if i < len(s) - 1 and m[s[i]] < m[s[i+1]]:
                ans -= m[s[i]]
            else:
                ans += m[s[i]]
        
        return ans

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        start = 0
        tank = 0

        for i in range(len(gas)):
            tank += gas[i] - cost[i]

            if tank < 0:
                start = i + 1
                tank = 0

        return start

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # [x,y,z]
        # [y*z,x*z, x*y]
        ans=[1]*len(nums)

        # forward pass 
        front=1
        for i in range(len(nums)):
            ans[i]=front
            front*=nums[i]
        
        # backward pass
        back=1
        for i in range(len(nums)-1, -1, -1):
            ans[i]*=back
            back*=nums[i]
        
        return ans

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums) 
        prefix = 1
        for i in range(len(nums)):
            result[i] = prefix
            prefix *= nums[i]

            
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            result[i] *= postfix
            postfix *= nums[i]
        return result
            

import random

class RandomizedSet:

    def __init__(self):
        self.arr = []
        self.pos = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False

        self.pos[val] = len(self.arr)
        self.arr.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False

        index = self.pos[val]
        last = self.arr[-1]

        self.arr[index] = last
        self.pos[last] = index

        self.arr.pop()
        del self.pos[val]

        return True

    def getRandom(self) -> int:
        return random.choice(self.arr)

import random

class RandomizedSet:

    def __init__(self):
        self.lst = []
        self.idx_map = {}

    def search(self, val):
        return val in self.idx_map

    def insert(self, val):
        if self.search(val):
            return False

        self.lst.append(val)
        self.idx_map[val] = len(self.lst) - 1
        return True

    def remove(self, val):
        if not self.search(val):
            return False

        idx = self.idx_map[val]
        self.lst[idx] = self.lst[-1]
        self.idx_map[self.lst[-1]] = idx
        self.lst.pop()
        del self.idx_map[val]
        return True

    def getRandom(self):
        return random.choice(self.lst)

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # max of x such that x is atleast n with x citation
        citations.sort(reverse=True)
        h=0
        for i in range(0,len(citations)):
            if citations[i]>=i+1:
                h=i+1
            else:
                break
        return h

            

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        curr_end=0
        far=0
        jumps=0

        for i in range(len(nums)-1):
            far=max(far,nums[i]+i)

            if i==curr_end:
                jumps+=1
                curr_end=far
        return jumps

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0

        for i in range(len(nums)):
            if i > farthest:
                return False

            farthest = max(farthest, i + nums[i])

            if farthest >= len(nums) - 1:
                return True

        return True

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit=0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                max_profit+=prices[i]- prices[i-1]
        
        return max_profit 
        

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max = 0
        start = prices[0]
        len1 = len(prices)
        for i in range(0 , len1):
            if start < prices[i]: 
                max += prices[i] - start
            start = prices[i]
        return max
        

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit=0
        # profit=buytoday-cheapestsofar
        min_price=prices[0]
        for price in prices:
            min_price=min(price, min_price)
            max_profit=max(max_profit,price - min_price)
        return max_profit


        

class Solution(object):
    def maxProfit(self, prices):
        profit = 0
        buy = prices[0]
        for sell in prices[1:]:
            if sell > buy:
                profit = max(profit, sell - buy)
            else:
                buy = sell
        
        return profit

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def rev(left, right):
            while left< right:
                nums[left], nums[right]= nums[right], nums[left]
                left+=1
                right-=1
        
        n=len(nums)
        k=k%n
        rev(0,n-1)
        rev(0,k-1)
        rev(k,n-1)


        

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k=k%len(nums)
        if k!=0:
            nums[:k],nums[k:]=nums[-k:],nums[:-k]

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        major=None 
        count =0
        for num in nums:
            if count==0:
                major=num

            if num==major:
                count+=1
            else:
                count-=1
        return major
        


        
        

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand=nums[0]
        candiscore=0
        for i in nums:
            if candiscore==0:
                cand=i
            if i==cand:
                candiscore+=1

            else:
                candiscore-=1
               
                
        return cand

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k=0
        for n in nums:
            if k<2 or n!=nums[k-2]:
                nums[k]=n
                k+=1
        return k
            
                

        

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i=0
        for k in nums:

            if i<2 or k!=nums[i-2]:
                nums[i]=k
                i+=1
        return i


        

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k=1
        for i in range(1, len(nums)):
            if nums[i]!=nums[k-1]:
                nums[k]=nums[i]
                k+=1
        return k

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        uni=0
        for i in range(len(nums)):
            if i==0 or nums[i]!=nums[i-1]:
                nums[uni]=nums[i]
                uni+=1
            else:
                pass
        return uni
                    

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        k=0
        past=None
        for i in nums:
            if past==None:
                nums[0]=i
                k+=1
                past=nums[0]

            if past!=i:
                nums[k]=i
                past=i
                k+=1
            else:
                pass
        return k

        

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k=0
        for i in nums:
            if i != val:
                nums[k]=i 
                k+=1
        return k

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        uni=0
        for i in range(len(nums)):
            if nums[i]!=val:
                nums[uni]=nums[i]
                uni+=1
            else:
                pass
        return uni
        

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k=0
        for i in nums:
            if i!=val:
                nums[k]=i
                k+=1
        return k

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        """
        Do not return anything, modify nums1 in-place instead.
        """
        last = m+n-1
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[last]=nums1[m-1]
                m-=1
                last-=1
            else:
                nums1[last]=nums2[n-1]
                n-=1
                last-=1
            
        while n>0:
            nums1[last]=nums2[n-1]
            n-=1
            last-=1

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i=m-1
        j=n-1
        k=m+n-1
        while j>=0:
            if i>=0 and nums1[i]>nums2[j]:
                nums1[k]=nums1[i]
                k-=1
                i-=1
            else:
                nums1[k]=nums2[j]
                j-=1
                k-=1

        

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m] + nums2[:n])

class Solution(object):
    def lemonadeChange(self, bills):
        if bills[0] != 5:
            return False
        
        five_dollers = 0
        ten_dollers = 0

        for x in bills:
            if x == 5:
                five_dollers += 1
            elif x == 10:
                if five_dollers > 0:
                    five_dollers -= 1
                else:
                    return False
                ten_dollers += 1
            else:
                if five_dollers > 0 and ten_dollers > 0:
                    five_dollers -= 1
                    ten_dollers -= 1
                elif five_dollers > 2 :
                    five_dollers -= 3
                else:
                    return False
            print(five_dollers, ten_dollers)
        return True

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:

        if (digits[len(digits)-1]+1) <= 9:
            digits[len(digits)-1]+=1
            return digits
        else:
            digits[len(digits)-1]+=1

        for i in range(len(digits)-1,-1,-1):
            if digits[i] <= 9:
                return digits
            else:
                digits[i]=0
                if i!=0:
                    digits[i-1]+=1
                else:
                    digits.insert(0,1)
                    return digits

        

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dict={}
        for i in nums:
            if i not in dict:
                dict[i]=nums.count(i)
        for i,j in dict.items():
            if j==1:
                return i
            
        

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        l=[]
        for i in nums:
            if nums.count(i)==1:
                l.append(i)
            if len(l)==2:
                break

        return l
        

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans =[]
        n=len(nums)
        for x in nums:
            x = abs(x)
            if nums[x-1]<0:
                ans.append(x)
            nums[x-1] *= -1
        return ans

class Solution(object):
    def mergeAlternately(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: str
        """

        results=""
        for i in range(min(len(word1),len(word2))):
            results+=word1[i]
            results+=word2[i]
            
            
        if min(len(word1),len(word2))==len(word1):
            results+=word2[len(word1):]
            return results
        results+=word1[len(word2):]
        return results

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        if sum(nums)%2==1:
            return False
        
        target=sum(nums)//2
        dp=set()

        if target in nums:
            return True
        
        dp.add(0)
        for i in range(len(nums)-1,-1,-1):
            newDP=set()
            for t in dp:
                if (t+nums[i]==target):
                    return True
                newDP.add(t+nums[i])
                newDP.add(t)
            dp=newDP
        if target in dp:
            return True
        else:
            return False
        

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0:
            return 0
        dp=[0]* (n+1)
        dp[0]=0
        dp[1]=1

        for i in range(2, n+1):
            dp[i]=dp[i-1]+dp[i-2]
        
        return dp[n]

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[0]* (len(nums))
        if len(nums)==1:
            return nums[0]
        dp[0]=nums[0]
        dp[1]=max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i]=max(dp[i-1], dp[i-2]+nums[i])

        return dp[len(nums)-1]

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0 or n==1:
            return 1
        dp=[0]* (n+1)

        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]

        return dp[n]