Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        table = dict()
        for i, num in enumerate(nums):
            if target - num in table.keys():
                return [i, table[target-num]]
            table[num] = i
        return []

# 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]:
        # get numbers out:
        head = l1
        l1_nums = [] # [2,4,3]
        while head:
            l1_nums.append(head.val)
            head = head.next
        print("l1_nums:", l1_nums)
        head = l2
        l2_nums = [] # [5,6,4]
        while head:
            l2_nums.append(head.val)
            head = head.next
        print("l2_nums:", l2_nums)
        # reverse the lists and turn them into ints:
        if l1_nums is not None:
            l1_nums = list(reversed(l1_nums))
        if l2_nums is not None:
            l2_nums = list(reversed(l2_nums))
        l1_num = int(''.join(map(str, l1_nums))) #342
        l2_num = int(''.join(map(str, l2_nums))) #465
        sum = l1_num + l2_num
        sum_list = list(map(int, str(sum)))      # [8, 0, 7]
        #if sum_list is not None:
        #    sum_list = list(reversed(sum_list))  # [7, 0, 8]
        print(sum_list)

        # LN(7) <- LN(0) <- LN(8)

        tail = None
        for i in range(len(sum_list)):
            next = ListNode(sum_list[i], tail)
            i = i + 1
            tail = next

        return tail

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = r = 0
        longest_length = r - l
        counts = collections.defaultdict(int)
        while r < len(s):
            if counts[s[r]] == 0:
                counts[s[r]] += 1
                r += 1
            else:
                counts[s[l]] = 0
                l += 1
            longest_length = max(r - l, longest_length)

        return longest_length

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int totalSize = nums1Size + nums2Size;
    int merged[totalSize];
    int i = 0, j = 0, k = 0;

    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }

    while (i < nums1Size) {
        merged[k++] = nums1[i++];
    }

    while (j < nums2Size) {
        merged[k++] = nums2[j++];
    }

    if (totalSize % 2 == 0) {
        return (double)(merged[totalSize/2] + merged[totalSize/2 - 1])/2;
    } else {
        return (double)merged[totalSize/2];
    }
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        sorted_indices = sorted(range(len(height)),
                                key=lambda index: height[index], reverse=True)
        maxArea = 0
        print(sorted_indices)
        for i, s in enumerate(sorted_indices):
            for j, t in enumerate(sorted_indices):
                if j >= i:
                    container_height = min(height[s],height[t])
                    area = abs(s-t) * container_height
                    if area > maxArea:
                        maxArea = area

        return maxArea

        # Time Limit Exceeded | 54/65 testcases passed
        """
        # two pointer approach
        maxArea = 0
        leftPointer = 0
        rightPointer = len(height)-1
        while leftPointer != rightPointer:
            area = min(height[leftPointer],height[rightPointer]) * abs(leftPointer - rightPointer)
            if area > maxArea:
                maxArea = area
            if height[leftPointer] < height[rightPointer]:
                leftPointer += 1
            else:
                rightPointer -= 1

        return maxArea

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

        romans = list(zip(values, symbols))
        num_as_str = str(num)
        digits = len(num_as_str)

        result = ""

        for val, sym in romans:
            multiplier = num // val
            if multiplier:
                result += sym * multiplier
                num %= val

        return result

#from itertools import combinations
"""
class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def twoSum(numbers: List[int], target: int) -> List[List[int]]:
            res = []
            if not numbers:
                return []
            leftPointer, rightPointer = 0, len(numbers) - 1
            while leftPointer < rightPointer:
                status = numbers[leftPointer] + numbers[rightPointer]
                if status < target:
                    leftPointer += 1
                elif status > target:
                    rightPointer -= 1
                else:
                    res.append([leftPointer + 1, rightPointer + 1])

                    # skip duplicates on BOTH sides
                    lv, rv = numbers[leftPointer], numbers[rightPointer]
                    while leftPointer < rightPointer and numbers[leftPointer] == lv:
                        leftPointer += 1
                    while leftPointer < rightPointer and numbers[rightPointer] == rv:
                        rightPointer -= 1

            return res
        #combinations_of_3 = list(combinations(nums,3))
        #print(len(combinations_of_3))
        #out = []
        #for c in combinations_of_3:
        #    if sum(c) == 0:
        #        if sorted(c) not in out:
        #            out.append(sorted(c))
        #
        #return out

        nums.sort()
        out = []
        for i,n in enumerate(nums):
            if n>0:
                break # sorted, so a positive number means we can never get to 0
            if i>0 and n == nums[i-1]: # skip if same as previous
                continue
            print(nums[i+1:])
            idxs = twoSum(nums[i+1:], 0-n)
            if idxs:
                for idx in idxs:
                    out.append([n, nums[i+idx[0]], nums[i+idx[1]]])

        return out
"""

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def twoSum(numbers: List[int], target: int) -> List[List[int]]:
            res: List[List[int]] = []
            if not numbers:
                return res
            leftPointer, rightPointer = 0, len(numbers) - 1

            while leftPointer < rightPointer:
                status = numbers[leftPointer] + numbers[rightPointer]
                if status < target:
                    leftPointer += 1
                elif status > target:
                    rightPointer -= 1
                else:
                    # record (keeping your 1-based indexing)
                    res.append([leftPointer + 1, rightPointer + 1])

                    # skip duplicates on BOTH sides
                    lv, rv = numbers[leftPointer], numbers[rightPointer]
                    while leftPointer < rightPointer and numbers[leftPointer] == lv:
                        leftPointer += 1
                    while leftPointer < rightPointer and numbers[rightPointer] == rv:
                        rightPointer -= 1
            return res

        nums.sort()
        out: List[List[int]] = []

        for i, n in enumerate(nums):
            if n > 0:
                break  # remaining numbers are positive → no more triplets
            if i > 0 and n == nums[i - 1]:
                continue  # skip duplicate anchors

            idxs = twoSum(nums[i + 1:], -n)  # search suffix
            for l1, r1 in idxs:               # l1/r1 are 1-based within the suffix
                out.append([n, nums[i + l1], nums[i + r1]])

        return out

class Solution:

    def threeSumClosest(self, nums: List[int], target: int) -> int:

        nums = sorted(nums)

        n = len(nums)
        closest_sum = 9999999

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

            lo, hi = i + 1, n - 1

            while lo < hi:
                cur_sum = nums[i] + nums[lo] + nums[hi]

                if abs(cur_sum - target) < abs(closest_sum - target):
                    closest_sum = cur_sum

                if cur_sum == target:
                    return cur_sum
                elif cur_sum < target:
                    lo += 1
                else:
                    hi -= 1

        return closest_sum

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        hashMap = {
            ')': '(',
            '}': '{',
            ']': '['
        }
        for element in s:
            if stack and (element in hashMap and stack[-1] == hashMap[element]):
                stack.pop()
            else:
                stack.append(element)
        return not stack

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        if list2.val < list1.val:
            start, other = list2, list1
        else:
            start, other = list1, list2

        curr = start
        while curr and other:
            if curr.next is None or curr.next.val > other.val:
                other_next = other.next
                other.next = curr.next
                curr.next = other
                other = other_next
                curr = curr.next
            else:
                curr = curr.next
        return start

def checkGroup(group: List[str]) -> bool:
    print(group)
    uniques = list(set(group))
    counts = {s: group.count(s) for s in uniques}
    del counts['.']
    print(counts.values())
    if any(value > 1 for value in counts.values()):
        print("tripped")
        return False
    if any(int(key) > 9 or int(key) < 1 for key in counts.keys()):
        return False
    return True
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # check rows:
        n = len(board)
        for row in board:
            if not checkGroup(row):
                return False
        # check columns:
        for i in range(n):
            col = [row[i] for row in board]
            if not checkGroup(col):
                return False
        # check grids:
        for row_offset in range(0,n,3):
            for col_offset in range(0,n,3):
                subgrid = []
                for r in range(row_offset, row_offset + 3):
                    for c in range(col_offset, col_offset + 3):
                        subgrid.append(board[r][c])
                if not checkGroup(subgrid):
                    return False
        return True

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        N = len(board)
        empties = []

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

        def find_empties():
            for i, row in enumerate(board):
                for j, val in enumerate(row):
                    if val == '.':
                        empties.append((i, j))
                    else:
                        rows[i].add(val)
                        cols[j].add(val)
                        boxes[(i // 3) * 3 + (j // 3)].add(val)

        def validMove(pos):
            r, c = pos
            b = (r // 3) * 3 + (c // 3)
            valid_moves = []
            for d in "123456789":
                if d not in rows[r] and d not in cols[c] and d not in boxes[b]:
                    valid_moves.append(d)
            return valid_moves

        def dfs_rec(idx):
            if idx == len(empties):
                return True
            r, c = empties[idx]
            b = (r // 3) * 3 + (c // 3)
            for move in validMove((r, c)):
                board[r][c] = move
                rows[r].add(move)
                cols[c].add(move)
                boxes[b].add(move)
                if dfs_rec(idx + 1):
                    return True
                board[r][c] = '.'
                rows[r].remove(move)
                cols[c].remove(move)
                boxes[b].remove(move)
            return False

        find_empties()
        dfs_rec(0)

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """shockingly this code is accepted despite the O(nlogn) tc and O(n) sc
        # will remove this assumption later:
        nums = sorted(list(set(nums)))

        one = False
        location = 0
        for i, num in enumerate(nums):
            if num == 1:
                one = True
                location = i

        if one == False:
            return 1

        # check subsequent:
        j = location
        spi = 1
        while j < len(nums):
            if nums[j] == spi:
                spi += 1
                j += 1
                continue
            return spi
        return spi
        """

        # cyclic sort:
        n = len(nums)

        # place each positive integer at the respective index within nums
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] -1], nums[i] = nums[i], nums[nums[i] -1] # swap

        # linear search for first discrepancy
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1 # returns discrep

        # or returns n + 1
        return n + 1

class Solution:
    def trap(self, height: List[int]) -> int:
        l_wall = r_wall = 0
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n

        for i in range(n):
            j = -i - 1
            max_left[i] = l_wall
            max_right[j] = r_wall
            l_wall = max(l_wall, height[i])
            r_wall = max(r_wall, height[j])

        summ = 0
        for i in range(n):
            pot = min(max_left[i], max_right[i])
            summ += max(0, pot - height[i])

        return summ

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, end):
            if start == end:
                result.append(nums[:])
                return
            for i in range(start, end):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1, end)
                nums[start], nums[i] = nums[i], nums[start]
        result = []
        backtrack(0, len(nums))
        return result

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        #O(mnlogn) sorting bruteforce
        print(strs)
        base = []
        for string in strs:
            base.append("".join((sorted(string))))

        print(base)
        # find indices that are all the same
        idxs = []
        marked = []
        for i, word1 in enumerate(base):
            i_likes = []
            for j, word2 in enumerate(base):
                if word1 == word2 and i <= j and j not in marked:
                    marked.append(j)
                    i_likes.append(j)
            if i_likes:
                idxs.append(i_likes)


        print(idxs)
        # replace indices with words:
        ans = []
        for tup in idxs:
            sublist = []
            for idx in tup:
                sublist.append(strs[idx])
            ans.append(sublist)

        return ans
        """

        # hashmap: O(m*n)
        hash = {}
        for s in strs:

            count = [0] * 26
            for c in s:
                count[ord(c)-ord("a")] += 1

            key = tuple(count)
            if key in hash:
                hash[key].append(s)
            else:
                hash[key] = [s]

        return list(hash.values())

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        for i, n in enumerate(nums):
            dp[i] = max(n, dp[i-1] + n)
        return max(dp)

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        while matrix:
            ret += (matrix.pop(0))
            if matrix and matrix[0]:
                for row in matrix:
                    ret.append(row.pop())
            if matrix:
                ret += (matrix.pop()[::-1])
            if matrix and matrix[0]:
                for row in matrix[::-1]:
                    ret.append(row.pop(0))
        return ret

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        return merged

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2

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

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(start, path):
            if len(path) == k:
                result.append(path[:])
                return
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1, path)
                path.pop()
        result = []
        backtrack(1, [])
        return result

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, path):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()
        result = []
        backtrack(0, [])
        return result

// function to insert value m at position n in array a by shifting the array
void insert(int *a, int m, int n, int l) {
    printf("debug %d %d %d\n", m, n, l);
    int temp = a[l-1];
    for(int i=l-1; i>n; i--) {
        a[i] = a[i-1];
    }
    a[0] = temp;
    a[n] = m;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int p1 = m - 1;
    int p2 = n - 1;

    for (int p = m + n - 1; p >= 0; p--) {
        if (p2 < 0) {break;}
        else {
            nums1[p] = (p1 >= 0 && nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
        }

    }
}

/*
    int offset = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0 + offset; j < n; j++) {
            // if less than first element
            if (i == 0 && nums1[i] >= nums2[j]) {
                printf("insert start\n");
                insert(nums1, nums2[j], i, m + n);
                offset++;
                break;
            }
            // if greater than last element
            else if (i == m - 1 && nums1[i] <= nums2[j]) {
                printf("insert end\n");
                insert(nums1, nums2[j], i, m + n);
                offset++;
                break;
            }
            else if (nums1[i] <= nums2[j] && (i + 1 < m && nums1[i+1] >= nums2[j])){ // belongs in middle
                printf("insert middle\n");
                insert(nums1, nums2[j], i+1, m + n);
                offset++;
                break;
            }
        }
    }
}
*/

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head

        dummy = ListNode(0, head)
        leftprev = dummy

        curr = head
        for _ in range(left - 1):
            leftprev = curr
            curr = curr.next

        prev = None
        tail = curr
        for _ in range(right - left + 1):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        leftprev.next = prev
        tail.next = curr
        return dummy.next

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        stack = [(p, q)]

        while stack:
            node1, node2 = stack.pop()

            if not node1 and not node2:
                continue

            elif None in [node1, node2] or node1.val != node2.val:
                return False

            stack.append((node1.left, node2.left))
            stack.append((node1.right, node2.right))

        return True

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = deque([root])
        result = []

        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def convert(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            node.left = convert(left, mid - 1)
            node.right = convert(mid + 1, right)
            return node
        return convert(0, len(nums) - 1)

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([(root, 1)])

        while queue:
            node, level = queue.popleft()

            if not node.left and not node.right:
                return level

            if node.left:
                queue.append((node.left, level + 1))

            if node.right:
                queue.append((node.right, level + 1))

        return 0

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        stack = [(root, root.val)]

        while stack:
            node, val = stack.pop()

            if not node.left and not node.right and val == targetSum:
                return True

            if node.right:
                stack.append((node.right, val + node.right.val))
            if node.left:
                stack.append((node.left, val + node.left.val))

        return False

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        maxP = 0

        while r != len(prices):
            if prices[l] < prices[r]:
                prof = prices[r] - prices[l]
                maxP = max(maxP, prof)
            else:
                l = r
            r += 1

        return maxP

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)  # O(n) average time, O(n) space
        longest = 0
        for n in numSet:  # ← iterate uniques to avoid duplicate re-walks
            # check if it is the start of the sequence
            if (n - 1) not in numSet:
                length = 0
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        queue = deque([node])
        clones = {node.val: Node(node.val)}

        while queue:
            curr = queue.popleft()
            curr_clone = clones[curr.val]

            for neighbor in curr.neighbors:
                if neighbor.val not in clones:
                    clones[neighbor.val] = Node(neighbor.val)
                    queue.append(neighbor)
                curr_clone.neighbors.append(clones[neighbor.val])
        return clones[node.val]

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor ^= num
        return xor

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        curr = head
        visited = set()
        while curr:
            if curr not in visited:
                visited.add(curr)
            else:
                return True
            curr = curr.next
        return False

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+', '-', '*', '/'}:
                stack.append(int(token))
            else:
                op1 = stack.pop()
                op2 = stack.pop()
                if token == '+':
                    stack.append(op2 + op1)
                elif token == '*':
                    stack.append(op2 * op1)
                elif token == '/':
                    stack.append(int(op2 / op1))
                elif token == '-':
                    stack.append(op2 - op1)
        return stack.pop()

import re
class Solution:
    def reverseWords(self, s: str) -> str:
        splt = re.split('\\s+',s)
        splt.reverse()
        return " ".join(splt).strip()

class MinStack:

    def __init__(self):
        self.data = []

    def push(self, val: int) -> None:
        self.data.append(val)

    def pop(self) -> None:
        self.data.pop()

    def top(self) -> int:
        return self.data[-1]

    def getMin(self) -> int:
        return min(self.data)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        leftPointer, rightPointer = 0, len(numbers) - 1
        while leftPointer != rightPointer:
            status = numbers[leftPointer] + numbers[rightPointer]
            if status < target:
                leftPointer += 1
            elif status > target:
                rightPointer -= 1
            else:
                return [leftPointer+1, rightPointer+1]


        return []

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """my naive soln
            d = {x:nums.count(x) for x in nums}
            a, b = d.keys(), d.values()
            max_value = max(b)
            max_index = list(b).index(max_value)
            return (list(a)[max_index])

            # o(n^2) because we run o(n) count on each x
        """

        """
        candidate = 0
        count = 0
        # phase 1: find candidate
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate
        """
        count = {} # dictionary.
        res, maxCount = 0, 0

        for n in nums:
            count[n] = 1 + count.get(n, 0)
            res = n if count[n] > maxCount else res
            maxCount = max(count[n], maxCount)

        return res