Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def backtrack(comb, remain, curr, counter, results):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for next_curr in range(curr, len(counter)):
                candidate, freq = counter[next_curr]

                if freq <= 0:
                    continue

                comb.append(candidate)
                counter[next_curr] = (candidate, freq - 1)
                backtrack(comb, remain - candidate, next_curr, counter, results)
                counter[next_curr] = (candidate, freq)
                comb.pop()

        results = []
        counter = Counter(candidates)
        counter = [(c, counter[c]) for c in counter]

        backtrack(
            comb=[], remain=target, curr=0, counter=counter, results=results
        )

        return results

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    prefix = ""
    for char in searchWord:
        prefix += char
        suggestions = [product for product in products if product.startswith(prefix)]
        result.append(suggestions[:3])
    return result

Input: n = 27
Output: true
Explanation: 27 = 3^3

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1

Input: root = [4,2,6,1,3]
Output: 1

class Solution:
    def __init__(self):
        self.inorderNodes = []

    def inorderTraversal(self, root):
        if not root:
            return
        
        self.inorderTraversal(root.left)
        self.inorderNodes.append(root.val)
        self.inorderTraversal(root.right)
    
    def minDiffInBST(self, root):
        self.inorderTraversal(root)
        
        minDistance = float('inf')
        for i in range(1, len(self.inorderNodes)):
            minDistance = min(minDistance, self.inorderNodes[i] - self.inorderNodes[i - 1])
        
        return minDistance

Input: nums = [3,6,5,1,8]
Output: 18

def maxSumDivThree(nums):
    total_sum = sum(nums)
    if total_sum % 3 == 0:
        return total_sum
    
    mod1 = [x for x in nums if x % 3 == 1]
    mod2 = [x for x in nums if x % 3 == 2]
    
    mod1.sort()
    mod2.sort()
    
    if total_sum % 3 == 1:
        if len(mod1) >= 1 and len(mod2) >= 2:
            return max(total_sum - mod1[0], total_sum - sum(mod2[:2]))
        if len(mod1) >= 1:
            return total_sum - mod1[0]
        if len(mod2) >= 2:
            return total_sum - sum(mod2[:2])
    
    if total_sum % 3 == 2:
        if len(mod2) >= 1 and len(mod1) >= 2:
            return max(total_sum - mod2[0], total_sum - sum(mod1[:2]))
        if len(mod2) >= 1:
            return total_sum - mod2[0]
        if len(mod1) >= 2:
            return total_sum - sum(mod1[:2])
    
    return 0

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

import heapq

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        ans = []
        visited = set()
        minHeap = [(nums1[0] + nums2[0], 0, 0)]
        visited.add((0, 0))

        while k > 0 and minHeap:
            sum_val, i, j = heapq.heappop(minHeap)
            ans.append([nums1[i], nums2[j]])
            if i + 1 < m and (i + 1, j) not in visited:
                heapq.heappush(minHeap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(minHeap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
            k -= 1

        return ans

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        def dfs(r, c, index):
            ans = 1
            grid[r][c] = index
            for nr, nc in neighbors(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = index
                    ans += dfs(nr, nc, index)
            return ans

        def neighbors(r, c):
            for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N:
                    yield nr, nc

        N = len(grid)
        index = 2
        area = [0] * (N * N + 2)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    area[index] = dfs(r, c, index)
                    index += 1

        ans = max(area)
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
                    ans = max(a

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

class Solution:
    def bitmask(self, word: str) -> int:
        mask = 0
        for letter in word:
            mask |= 1 << (ord(letter) - ord('a'))
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_count = {}
        for word in words:
            mask = self.bitmask(word)
            word_count[mask] = word_count.get(mask, 0) + 1

        result = []
        for puzzle in puzzles:
            first = 1 << (ord(puzzle[0]) - ord('a'))
            count = word_count.get(first, 0)
            mask = self.bitmask(puzzle[1:])
            submask = mask
            while submask > 0:
                count += word_count.get(submask | first, 0)
                submask = (submask - 1) & mask
            result.append(count)
        return result

Input: nums = [1,1,2]  
Output: 2, nums = [1,2,_]  

from typing import List  

class Solution:  
    def removeDuplicates(self, nums: List[int]) -> int:  
        i = 0    
        while i < len(nums) - 1:     
            if nums[i] == nums[i + 1]:  
                nums.pop(i + 1)     
            else:  
                i += 1    

        return len(nums)

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

class Solution:
    def __init__(self):
        self.isTravelNeeded = set()
    
    def solve(self, dp, days, costs, currDay):
        if currDay > days[-1]:
            return 0
        
        if currDay not in self.isTravelNeeded:
            return self.solve(dp, days, costs, currDay + 1)
        
        if dp[currDay] != -1:
            return dp[currDay]
        
        oneDay = costs[0] + self.solve(dp, days, costs, currDay + 1)
        sevenDay = costs[1] + self.solve(dp, days, costs, currDay + 7)
        thirtyDay = costs[2] + self.solve(dp, days, costs, currDay + 30)
        
        dp[currDay] = min(oneDay, min(sevenDay, thirtyDay))
        return dp[currDay]
    
    def mincostTickets(self, days, costs):
        lastDay = days[-1]
        dp = [-1] * (lastDay + 1)
        
        for day in days:
            self.isTravelNeeded.add(day)
        
        return self.solve(dp, days, costs, 1)

Input: root = [1,1,1,1,1,null,1]
Output: true

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        vals = []
        
        def dfs(node):
            if node:
                vals.append(node.val)
                dfs(node.left)
                dfs(node.right)
        
        dfs(root)
        return all(v == vals[0] for v in vals)

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_count = 0
        for i in range(len(nums) - 2):
            sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
        return sum_count

    def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
        sum_count = 0
        for i in range(startIndex, len(nums) - 1):
            j = self.binarySearch(nums, i, target - nums[i])
            sum_count += j - i
        return sum_count

    def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
        left, right = startIndex, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        def f(p, i, m):
            if i == len(piles):
                return 0
            if dp[p][i][m] != -1:
                return dp[p][i][m]
            res = 1000000 if p == 1 else -1
            s = 0
            for x in range(1, min(2 * m, len(piles) - i) + 1):
                s += piles[i + x - 1]
                if p == 0:
                    res = max(res, s + f(1, i + x, max(m, x)))
                else:
                    res = min(res, f(0, i + x, max(m, x)))
            dp[p][i][m] = res
            return res

        dp = [[[-1] * (len(piles) + 1) for _ in range(len(piles) + 1)] for _ in range(2)]
        return f(0, 0, 1)

Input: s = "aacecaaa"
Output: "aaacecaaa"

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        n = len(s)
        rev = s[::-1]
        for i in range(n):
            if s[: n - i] == rev[i:]:
                return rev[:i] + s
        return ""