class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # {num: index}にする
        num_to_index = {num: idx for idx, num in enumerate(nums)}

        # (target - その数値)がnum_to_indexに存在し、当該数値でもないなら2つのインデックスを返す
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_to_index and num_to_index[complement] != i:
                return [i, num_to_index[complement]]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 再帰関数を定義
        def helper(l1, l2, carry):
            # l1とl2がNoneで、carryが0なら終了する
            if not l1 and not l2 and carry == 0:
                return None

            # 現在のノードの合計値を計算する
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            # 1の位のみにしてノードを作成する
            node = ListNode(total % 10)

            # 10の位を繰り上げとして、次の桁を再帰する
            node.next = helper(l1, l2, total // 10)

            return node

        # 最初の再帰呼び出し
        return helper(l1, l2, 0)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # スタート位置と最大長を保存する変数
        start = 0
        max_len = 0
        # 使用済み文字とその位置を保存する辞書
        used_chars = {}

        # sに対してループする
        for i, char in enumerate(s):
            # もし文字が以前に現れていて、その位置がstartよりも後であれば
            if char in used_chars and used_chars[char] >= start:
                # start位置を次の位置に移動
                start = used_chars[char] + 1
            # 現在の位置を辞書に保存する
            used_chars[char] = i
            # 最大値を更新する
            max_len = max(max_len, i - start + 1)
        return max_len

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # numRowsが1の場合、あるいはsの長さ以上の場合はs自体を返す
        if numRows == 1 or numRows >= len(s):
            return s

        # 行ごとに文字を保持するリストを作成
        rows = [''] * numRows
        # indexは現在の行、stepは進行方向とする
        index, step = 0, 1

        # sをループして配置
        for char in s:
            rows[index] += char
            
            # indexが最上段または最下段なら、step（進行方向）を変更する
            if index == 0:
                step = 1
            elif index == numRows - 1:
                step = -1

            # 行を進める
            index += step

        # すべての行を連結して結果の文字列を作成
        return ''.join(rows)

class Solution:
    def myAtoi(self, s: str) -> int:
        # 文字列から空白を削除
        s = s.lstrip()

        # resultを0で初期化
        result = 0

        # 正負のフラグをTrueで初期化
        is_positive = True

        # 先頭が-あるいは+の場合、フラグを更新して先頭文字をスキップする
        if s and (s[0] == '+' or s[0] == '-'):
            is_positive = s[0] != '-'
            s = s[1:]
        
        # sをループ
        for char in s:
            # charが数値なら位を上げながら数値化し、resultに入れていく
            if char.isdigit():
                result = result * 10 + int(char)
            else:
                # 数値でなければ以降は無視する
                break

        # resultを正負で更新する
        result = result if is_positive else -result

        # 32ビットの範囲内に収める
        result = max(min(result, 2**31 - 1), -2**31)

        return result

class Solution:
    def isValid(self, s: str) -> bool:
        # スタックを用意する
        stack = []

        # かっこのペアを辞書として持つ
        mapping = {')': '(', '}': '{', ']': '['}

        # sをループする
        for char in s:
            # 文字が閉じかっこなら、スタックの最後の要素がペアと合っているか判定する
            if char in mapping:
                # スタックから最後の要素を取り出す、空ならダミーとして#を入れる
                top_element = stack.pop() if stack else '#'

                # 最後の要素がペアではない場合、Falseを返す
                if top_element != mapping[char]:
                    return False
            else:
                # 開きかっこの場合、スタックに追加する
                stack.append(char)

        # スタックが空になればTrue、そうでなければFalseを返す
        return not stack

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 再帰的に組み合わせを生成する内部関数を定義
        def generate(partial, left, right):
            # left: 残りの左かっこの数, right: 残りの右かっこの数

            # 基底ケース: どちらもかっこの残りがない場合、partialを結果リストに追加
            if left == 0 and right == 0:
                return [partial]

            # resultを初期化
            result = []

            # 左かっこがまだ残っている場合、partialに追加し-1て再帰する
            if left > 0:
                result += generate(partial + "(", left - 1, right)

            # 左かっこの数が右かっこより少ない場合は、右かっこを追加し-1して再帰する
            if left < right:
                result += generate(partial + ")", left, right - 1)
            
            return result

        # 上記の内部関数を呼びだす
        return generate("", n, n)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 配列を逆から探索して、非増加となるインデックスiを探す
        i = next((i for i in range(len(nums) - 1, 0, -1) if nums[i-1] < nums[i]) ,None)

        # 非増加のiがない場合はnumsが最大の順列のため、最小である照準に並べ替える
        if i is None:
            nums[:] = reversed(nums)
            return 

        # 配列を逆順に探索して、nums[i-1]より大きい初めての数のインデックスjを探す
        j = next(j for j in range(len(nums) - 1, i - 1, -1) if nums[j] > nums[i-1])

        # nums[i-1]とnums[j]を入れ替える
        nums[i-1], nums[j] = nums[j], nums[i-1]

        # iから最後までの部分を昇順にする
        nums[i:] = reversed(nums[i:])

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 再帰関数の定義
        def binary_search(left: int, right: int) -> int:
            # base case
            if left > right:
                return -1

            # midを探す
            mid = (left + right) // 2
            
            # midの値が目的の値と一致すればそのインデックスを返す
            if nums[mid] == target:
                return mid

            # midの値が左端の値よりも大きい場合（midは左側の昇順中にあるので、midより左はソート済）
            if nums[mid] >= nums[left]:
                # 目的の値が左側の範囲にある場合
                if nums[left] <= target < nums[mid]:
                    return binary_search(left, mid - 1)
                # 左側の範囲にない場合
                else:
                    return binary_search(mid + 1, right)
            # midの値が左端の値よりも小さい場合（midは右側の昇順中にあるので、midより右はソート済）
            else:
                # 目的の値が右側の範囲にある場合
                if nums[mid] < target <= nums[right]:
                    return binary_search(mid + 1, right)
                # 右側の範囲にない場合
                else:
                    return binary_search(left, mid - 1)
        
        # rightをlen(nums)-1して再帰関数を実行する
        return binary_search(0, len(nums) - 1)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 再帰関数を定義
        def binary_search(left: int, right: int) -> int:
            # ベースケース： leftがrightより大きい場合はleftを返す
            if left > right:
                return left

            # midを探す
            mid = (left + right) // 2

            # targetがmidと同じならmidを返す
            if nums[mid] == target:
                return mid

            # targetがmidの値より小さい場合、左側を再帰して探索する
            if target < nums[mid]:
                return binary_search(left, mid - 1)
            # targetがmidより大きい場合、右側を再帰して探索する
            else:
                return binary_search(mid + 1, right)

        # 0からlen(nums)-1の範囲で再帰関数を実行する
        return binary_search(0, len(nums) - 1)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 再帰関数を定義
        def depth_first_search(candidates, target, start, path):
            # ベースケース: targetが0より小さくなった場合、空のリストを返す
            if target < 0:
                return []
            
            # targetが0の場合、その組み合わせを返す
            if target == 0:
                return [path]
            
            # resの初期化
            res = []

            # start位置から終わりまでのcandidatesの各要素に対して探索する
            for i in range(start, len(candidates)):
                # 現在の要素を使用して、新しいtargetとpathで再帰的に探索する
                res += depth_first_search(candidates, target-candidates[i], i, path+[candidates[i]])
            # 探索結果を返す
            return res

        # 初期状態から深さ優先探索を開始
        return depth_first_search(candidates, target, 0, [])

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 再帰関数を定義
        def helper(nums: List[int]) -> List[List[int]]:
            # base case: numsが空の場合[[]]を返す
            if not nums:
                return [[]]

            # 順列を生成する
            return [[n] + p for i, n in enumerate(nums) for p in helper(nums[:i] + nums[i+1:])]

        # hepler関数を実行
        return helper(nums)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # アナグラムごとにグループ化するための辞書を作成
        grouped = defaultdict(list)

        # 各文字列をソートしてキーに入れ、元の文字列を辞書に追加
        [grouped["".join(sorted(s))].append(s) for s in strs]

        # 辞書のvaluesをリスト化して返す
        return list(grouped.values())

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # nが0の場合はn^0なので1.0を返す
        if n == 0:
            return 1.0

        # nが負の場合、xを逆数に変更し、nの符号を反転
        if n < 0:
            x = 1 / x
            n = -n

        # xのn乗を計算する再帰関数
        def helper(x: float, n: int) -> float:
            # ベースケース： nが0乗の場合は1.0を返す
            if n == 0:
                return 1.0

            # xのn/2乗を再帰的に計算
            half = helper(x, n // 2)

            # nが偶数の場合、答えはhalf * half
            if n % 2 == 0:
                return half * half
            # nが奇数の場合、xを1つ追加して掛け算する
            else:
                return half * half * x

        # 再帰関数を呼び出す
        return helper(x, n)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 現在の部分配列の和を保持
        current_sum = 0

        # 最大部分配列の和を保持（初期値は負の無限大）
        max_sum = float('-inf')

        # numsの各要素に対してループ
        for x in nums:
            # 現在の要素xと、current_sum + xの大きい方をcurrent_sumに代入
            current_sum = max(x, current_sum + x)

            # これまでの最大和と現在の部分配列の和の大きい方をmax_sumに代入
            max_sum = max(max_sum, current_sum)

        # 最大部分配列の和を返す
        return max_sum  

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 階乗の計算
        def factorial(num: int) -> int:
            result = 1
            for i in range(1, num + 1):
                result *= i
            return result
        
        # m + n - 2回の移動からm - 1回の下への移動を選ぶ組み合わせの数を計算
        return factorial(m + n - 2) // (factorial(m - 1) * factorial(n - 1)) 
        # これは、m+n-2個からm-1個を選ぶ組み合わせの数を返す

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # mは行数、nは列数
        m, n = len(obstacleGrid), len(obstacleGrid[0])

        # 左上が障害物なら0を返す（スタート地点がふさがっているため）
        if obstacleGrid[0][0] == 1:
            return 0

        # dp配列をすべて0で初期化
        dp = [[0] * n for _ in range(m)]

        # スタート位置の初期化（最初のセルに到達する経路は1通り）
        dp[0][0] = 1

        # グリッドを上から下、左から右へと走査
        for i in range(m):
            for j in range(n):
                # 上から下へ移動（最初の行以外）
                if i > 0:
                    dp[i][j] += dp[i-1][j] * (1 - obstacleGrid[i-1][j])
                # 左から右への移動（最初の行以外）
                if j > 0:
                    dp[i][j] += dp[i][j-1] * (1 - obstacleGrid[i][j-1])
                # 現在のセルが障害物なら経路数をリセット（障害物の場所へは移動できないため）
                dp[i][j] *= (1 - obstacleGrid[i][j])

        # グリッド右下のセルの値が全体の経路数
        return dp[-1][-1]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 再帰関数を定義
        def helper(subset: List[int], remaining: List[int]) -> List[List[int]]:
            # ベースケース: 残りの要素がなくなったら、現在の部分集合を返す
            if not remaining:
                return [subset]

            # 最初の要素を部分集合に追加するかしないかの2択で再帰する
            return helper(subset + [remaining[0]], remaining[1:]) + helper(subset, remaining[1:])

        # 再帰関数を実行
        return helper([], nums)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # ベースケース: ノードが存在しないか、次のノードが存在しない場合（リストの末尾）に達した場合、現在のノードをそのまま返す
        if not head or not head.next: return head

        # 次のノードと値が同じかを確認
        if head.val == head.next.val:
            # 重複する値をスキップ: 次のノードが存在し、値が同じ場合、ノードを進める
            while head.next and head.val == head.next.val:
                head = head.next
            # 重複が終わったところから再帰して、その結果を返す
            return self.deleteDuplicates(head.next)

        # 重複がない場合、次のノードに対して再帰を行い、現在のノードに結果をつなげて返す
        head.next = self.deleteDuplicates(head.next)
        return head

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 前のノードの値を記録する
        self.prev = None

        # 中間順序探索のヘルパー関数
        def in_order(node):
            # ノードが空ならTrueを返す
            if not node:
                return True

            # 左の部分木を探索
            if not in_order(node.left):
                return False

            # 前のノードの値が現在のノードの値以上ならFalse
            if self.prev is not None and self.prev >= node.val:
                return False

            # 現在のノードの値を記録
            self.prev = node.val

            # 右の部分木を探索
            return in_order(node.right)

        # ルートから探索を開始
        return in_order(root)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 再帰関数を定義
        def bfs(nodes: List[Optional[TreeNode]], result: List[List[int]]) -> List[List[int]]:
            # 空のノードの場合、resultを返す
            if not nodes:
                return result

            # 現在のレベルのノードの値を取得
            current_level_values = [node.val for node in nodes if node]

            # 次のレベルのノードを取得
            next_level_nodes = [child for node in nodes if node for child in (node.left, node.right) if child]

            # 現在のレベルの値があればresultに追加し、再帰する
            return bfs(next_level_nodes, result + [current_level_values]) if current_level_values else result

        # ルートから再帰する
        return bfs([root], []) if root else []

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 再帰関数を定義
        def bfs(nodes: List[Optional[TreeNode]], result: List[List[int]], is_even_level: bool) -> List[List[int]]:
            # 空のノードの場合、resultを返す
            if not nodes:
                return result

            # 現在のレベルのノードの値を取得
            current_level_values = [node.val for node in nodes if node]

            # ジグザグの順序のため、奇数レベルでは値を逆順にする
            if not is_even_level:
                current_level_values = current_level_values[::-1]

            # 次のレベルのノードを取得
            next_level_nodes = [child for node in nodes if node for child in (node.left, node.right) if child]

            # 現在のレベルの値があればresultに追加し、再帰する
            return bfs(next_level_nodes, result + [current_level_values], not is_even_level) if current_level_values else result

        # ルートから再帰する（最初のレベルは偶数とする）
        return bfs([root], [], True) if root else []

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # inorderの各値のインデックスを保存しておく（検索を高速化）
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        
        # 再帰関数の定義
        def helper(pre_start: int, in_start: int, in_end: int) -> Optional[TreeNode]:
            # ベースケース：範囲が無効な場合はNoneを返す
            if pre_start >= len(preorder) or in_start > in_end:
                return None
            
            # preorderから現在の根の値を取得
            root_val = preorder[pre_start]
            # 根のノードを作成
            root = TreeNode(root_val)
            # inorderの中で根の位置を取得
            root_idx = idx_map[root_val]
            # 左部分木を構築
            root.left = helper(pre_start + 1, in_start, root_idx - 1)
            # 右部分木を構築
            root.right = helper(pre_start + (root_idx - in_start) + 1, root_idx + 1, in_end)
            
            return root

        return helper(0, 0, len(inorder) - 1)