Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9

        rows = [set() for _ in range(N)]
        cols = [set() for _ in range(N)]
        boxes = [set() for _ in range(N)]

        for r in range(N):
            for c in range(N):
                val = board[r][c]
                if val == ".":
                    continue

                if val in rows[r]:
                    return False
                rows[r].add(val)

                if val in cols[c]:
                    return False
                cols[c].add(val)

                idx = (r // 3) * 3 + c // 3
                if val in boxes[idx]:
                    return False
                boxes[idx].add(val)

        return True

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

def findLength(nums1, nums2):
    dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
    max_len = 0
    for i in range(len(nums1) - 1, -1, -1):
        for j in range(len(nums2) - 1, -1, -1):
            if nums1[i] == nums2[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

Input: ransomNote = "a", magazine = "b"
Output: false

import random

class Solution:
    def __init__(self, nums: list[int]):
        self.array = nums[:]
        self.original = nums[:]
    
    def reset(self) -> list[int]:
        self.array = self.original[:]
        return self.original
    
    def shuffle(self) -> list[int]:
        for i in range(len(self.array)):
            rand_index = random.randint(i, len(self.array) - 1)
            self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
        return self.array

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

import collections
from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        adj_list = [[] for _ in range(n)]
        for A, B in edges:
            adj_list[A].append(B)
            adj_list[B].append(A)
        
        parent = {0: -1}
        queue = collections.deque([0])
        
        while queue:
            node = queue.popleft()
            for neighbour in adj_list[node]:
                if neighbour == parent[node]:
                    continue
                if neighbour in parent:
                    return False
                parent[neighbour] = node
                queue.append(neighbour)
        
        return len(parent) == n

Input: n = 2
Output: true

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.sum = 0
        
        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)
            self.sum += node.val
            node.val = self.sum
            reverse_inorder(node.left)
        
        reverse_inorder(root)
        return root

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_less_equal(x):
            count = 0
            for i in range(1, m + 1):
                count += min(x // i, n)
            return count
        
        left, right = 1, m * n
        while left < right:
            mid = (left + right) // 2
            if count_less_equal(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        WORD_KEY = "$"

        trie = {}
        for word in words:
            node = trie
            for letter in word:
                node = node.setdefault(letter, {})
            node[WORD_KEY] = word

        rowNum = len(board)
        colNum = len(board[0])
        matchedWords = []

        def backtracking(row, col, parent):
            letter = board[row][col]
            currNode = parent[letter]

            word_match = currNode.pop(WORD_KEY, False)
            if word_match:
                matchedWords.append(word_match)

            board[row][col] = "#"

            for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                newRow, newCol = row + rowOffset, col + colOffset
                if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
                    continue
                if board[newRow][newCol] not in currNode:
                    continue
                backtracking(newRow, newCol, currNode)

            board[row][col] = letter

            if not currNode:
                parent.pop(letter)

        for row in range(rowNum):
            for col in range(colNum):
                if board[row][col] in trie:
                    backtracking(row, col, trie)

        return matchedWords

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

from collections import deque

def isEscapePossible(blocked, source, target):
    blocked = set(map(tuple, blocked))
    source = tuple(source)
    target = tuple(target)
    
    if source in blocked or target in blocked:
        return False

    def bfs(start, end):
        queue = deque([start])
        visited = set([start])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        max_area = len(blocked) * (len(blocked) - 1) // 2
        
        while queue:
            if len(visited) > max_area:
                return True
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in visited and (nx, ny) not in blocked:
                    if (nx, ny) == end:
                        return True
                    queue.append((nx, ny))
                    visited.add((nx, ny))
        return False
    
    return bfs(source, target) and bfs(target, source)

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        memo = [[None] * n for _ in range(n)]

        def isValidPalindromeHelper(i, j):
            if i == j:
                return 0
            if i == j - 1:
                return 1 if s[i] != s[j] else 0
            if memo[i][j] is not None:
                return memo[i][j]
            if s[i] == s[j]:
                memo[i][j] = isValidPalindromeHelper(i + 1, j - 1)
            else:
                memo[i][j] = 1 + min(isValidPalindromeHelper(i + 1, j), isValidPalindromeHelper(i, j - 1))
            return memo[i][j]

        return isValidPalindromeHelper(0, n - 1) <= k

Input: s = "abccccdd"
Output: 7

def longestPalindrome(s):
    charCount = {}
    for char in s:
        charCount[char] = charCount.get(char, 0) + 1
    length = 0
    oddFound = False
    for count in charCount.values:
        if count % 2 == 0:
            length += count
        else:
            length += count - 1
            oddFound = True
    return length + 1 if oddFound else length

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        n = len(mat1)
        k = len(mat1[0])
        m = len(mat2[0])
        
        ans = [[0] * m for _ in range(n)]
        
        for rowIndex in range(n):
            for elementIndex in range(k):
                if mat1[rowIndex][elementIndex] != 0:
                    for colIndex in range(m):
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
        
        return ans

Input: s = "IDID"
Output: [0,4,1,3,2]

def diStringMatch(s):
    n = len(s)
    low, high = 0, n
    perm = [0] * (n + 1)
    
    for i in range(n):
        if s[i] == 'I':
            perm[i] = low
            low += 1
        else:
            perm[i] = high
            high -= 1
    
    perm[n] = low
    return perm

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

class Solution:
    def binaryGap(self, N: int) -> int:
        A = [i for i in range(32) if (N >> i) & 1]
        return max((A[i + 1] - A[i] for i in range(len(A) - 1)), default=0)