Top 100 Python Coding Interview Questions

def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i

def containsDuplicate(nums):
    return len(set(nums)) != len(nums)

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups[tuple(sorted(s))].append(s)
    return list(groups.values())

from collections import Counter

def topKFrequent(nums, k):
    return [n for n, _ in Counter(nums).most_common(k)]

def productExceptSelf(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

def isValidSudoku(board):
    seen = set()
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == '.':
                continue
            for k in ((r, v), (v, c), (r // 3, c // 3, v)):
                if k in seen:
                    return False
                seen.add(k)
    return True

class Codec:
    def encode(self, strs):
        return ''.join(f'{len(s)}#{s}' for s in strs)

    def decode(self, s):
        out, i = [], 0
        while i < len(s):
            j = s.index('#', i)
            n = int(s[i:j])
            out.append(s[j + 1:j + 1 + n])
            i = j + 1 + n
        return out

def longestConsecutive(nums):
    s = set(nums)
    best = 0
    for n in s:
        if n - 1 not in s:
            cur = n
            while cur + 1 in s:
                cur += 1
            best = max(best, cur - n + 1)
    return best

def maxProfit(prices):
    low, profit = float('inf'), 0
    for p in prices:
        low = min(low, p)
        profit = max(profit, p - low)
    return profit

def isPalindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

def twoSum(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l + 1, r + 1]
        if s < target:
            l += 1
        else:
            r -= 1

def threeSum(nums):
    nums.sort()
    res = []
    for i, a in enumerate(nums):
        if i and a == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = a + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([a, nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
    return res

def maxArea(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(h[l], h[r]))
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best

def trap(h):
    l, r = 0, len(h) - 1
    lmax = rmax = total = 0
    while l < r:
        if h[l] < h[r]:
            lmax = max(lmax, h[l])
            total += lmax - h[l]
            l += 1
        else:
            rmax = max(rmax, h[r])
            total += rmax - h[r]
            r -= 1
    return total

def maxProfit(prices):
    return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))

def lengthOfLongestSubstring(s):
    seen = {}
    l = best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= l:
            l = seen[c] + 1
        seen[c] = r
        best = max(best, r - l + 1)
    return best

from collections import Counter

def characterReplacement(s, k):
    cnt = Counter()
    l = best = top = 0
    for r, c in enumerate(s):
        cnt[c] += 1
        top = max(top, cnt[c])
        if r - l + 1 - top > k:
            cnt[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

from collections import Counter

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    need = Counter(s1)
    have = Counter(s2[:len(s1)])
    if have == need:
        return True
    for i in range(len(s1), len(s2)):
        have[s2[i]] += 1
        have[s2[i - len(s1)]] -= 1
        if have[s2[i - len(s1)]] == 0:
            del have[s2[i - len(s1)]]
        if have == need:
            return True
    return False

from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    missing = len(t)
    l = best_l = 0
    best = ''
    for r, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        if missing == 0:
            while need[s[l]] < 0:
                need[s[l]] += 1
                l += 1
            if not best or r - l + 1 < len(best):
                best = s[l:r + 1]
            need[s[l]] += 1
            missing += 1
            l += 1
    return best

from collections import deque

def maxSlidingWindow(nums, k):
    dq, out = deque(), []
    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

def isValid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, v):
        m = v if not self.stack else min(v, self.stack[-1][1])
        self.stack.append((v, m))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

def evalRPN(tokens):
    stack = []
    for t in tokens:
        if t in {'+', '-', '*', '/'}:
            b, a = stack.pop(), stack.pop()
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[0]

def generateParenthesis(n):
    out = []
    def bt(s, o, c):
        if len(s) == 2 * n:
            out.append(s)
            return
        if o < n: bt(s + '(', o + 1, c)
        if c < o: bt(s + ')', o, c + 1)
    bt('', 0, 0)
    return out

def dailyTemperatures(t):
    out = [0] * len(t)
    stack = []
    for i, v in enumerate(t):
        while stack and t[stack[-1]] < v:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out

def carFleet(target, position, speed):
    pairs = sorted(zip(position, speed), reverse=True)
    fleets, last = 0, 0
    for p, s in pairs:
        t = (target - p) / s
        if t > last:
            last = t
            fleets += 1
    return fleets

def largestRectangleArea(h):
    stack, best = [], 0
    for i, v in enumerate(h + [0]):
        start = i
        while stack and stack[-1][1] > v:
            j, hh = stack.pop()
            best = max(best, hh * (i - j))
            start = j
        stack.append((start, v))
    return best

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target:
            return m
        if nums[m] < target:
            l = m + 1
        else:
            r = m - 1
    return -1

def searchMatrix(m, target):
    rows, cols = len(m), len(m[0])
    l, r = 0, rows * cols - 1
    while l <= r:
        mid = (l + r) // 2
        v = m[mid // cols][mid % cols]
        if v == target:
            return True
        if v < target:
            l = mid + 1
        else:
            r = mid - 1
    return False

from math import ceil

def minEatingSpeed(piles, h):
    l, r = 1, max(piles)
    while l < r:
        m = (l + r) // 2
        if sum(ceil(p / m) for p in piles) <= h:
            r = m
        else:
            l = m + 1
    return l

def findMin(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r) // 2
        if nums[m] > nums[r]:
            l = m + 1
        else:
            r = m
    return nums[l]

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target:
            return m
        if nums[l] <= nums[m]:
            if nums[l] <= target < nums[m]:
                r = m - 1
            else:
                l = m + 1
        else:
            if nums[m] < target <= nums[r]:
                l = m + 1
            else:
                r = m - 1
    return -1

from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.data = defaultdict(list)

    def set(self, k, v, t):
        self.data[k].append((t, v))

    def get(self, k, t):
        arr = self.data[k]
        l, r, res = 0, len(arr) - 1, ''
        while l <= r:
            m = (l + r) // 2
            if arr[m][0] <= t:
                res = arr[m][1]
                l = m + 1
            else:
                r = m - 1
        return res

def findMedianSortedArrays(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    l, r = 0, m
    while l <= r:
        i = (l + r) // 2
        j = half - i
        al = a[i - 1] if i else -float('inf')
        ar = a[i] if i < m else float('inf')
        bl = b[j - 1] if j else -float('inf')
        br = b[j] if j < n else float('inf')
        if al <= br and bl <= ar:
            if (m + n) % 2:
                return max(al, bl)
            return (max(al, bl) + min(ar, br)) / 2
        if al > br:
            r = i - 1
        else:
            l = i + 1

def reverseList(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def mergeTwoLists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val < b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

def reorderList(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev, cur = None, slow.next
    slow.next = None
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    a, b = head, prev
    while b:
        a_nxt, b_nxt = a.next, b.next
        a.next = b
        b.next = a_nxt
        a, b = a_nxt, b_nxt

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next
    return dummy.next

def copyRandomList(head):
    mp = {None: None}
    cur = head
    while cur:
        mp[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        mp[cur].next = mp[cur.next]
        mp[cur].random = mp[cur.random]
        cur = cur.next
    return mp[head]

def addTwoNumbers(a, b):
    dummy = tail = ListNode()
    carry = 0
    while a or b or carry:
        v = (a.val if a else 0) + (b.val if b else 0) + carry
        carry, v = divmod(v, 10)
        tail.next = ListNode(v)
        tail = tail.next
        if a: a = a.next
        if b: b = b.next
    return dummy.next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

def findDuplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow2 = nums[0]
    while slow != slow2:
        slow, slow2 = nums[slow], nums[slow2]
    return slow

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

import heapq

def mergeKLists(lists):
    pq = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(pq, (lst.val, i, lst))
    dummy = tail = ListNode()
    while pq:
        _, i, node = heapq.heappop(pq)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(pq, (node.next.val, i, node.next))
    return dummy.next

def invertTree(root):
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

def diameterOfBinaryTree(root):
    best = 0
    def depth(n):
        nonlocal best
        if not n:
            return 0
        l, r = depth(n.left), depth(n.right)
        best = max(best, l + r)
        return 1 + max(l, r)
    depth(root)
    return best

def isBalanced(root):
    def height(n):
        if not n:
            return 0
        l = height(n.left)
        if l == -1: return -1
        r = height(n.right)
        if r == -1 or abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return height(root) != -1

def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

def isSubtree(s, t):
    if not s:
        return False
    return isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

from collections import deque

def levelOrder(root):
    if not root: return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out

from collections import deque

def rightSideView(root):
    if not root: return []
    q, out = deque([root]), []
    while q:
        out.append(q[-1].val)
        for _ in range(len(q)):
            n = q.popleft()
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
    return out

def goodNodes(root):
    def dfs(n, mx):
        if not n:
            return 0
        good = 1 if n.val >= mx else 0
        mx = max(mx, n.val)
        return good + dfs(n.left, mx) + dfs(n.right, mx)
    return dfs(root, root.val)

def isValidBST(root):
    def dfs(n, lo, hi):
        if not n:
            return True
        if not (lo < n.val < hi):
            return False
        return dfs(n.left, lo, n.val) and dfs(n.right, n.val, hi)
    return dfs(root, -float('inf'), float('inf'))

def kthSmallest(root, k):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

def buildTree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    pre = iter(preorder)
    def build(l, r):
        if l > r:
            return None
        v = next(pre)
        node = TreeNode(v)
        node.left = build(l, idx[v] - 1)
        node.right = build(idx[v] + 1, r)
        return node
    return build(0, len(inorder) - 1)

def maxPathSum(root):
    best = -float('inf')
    def dfs(n):
        nonlocal best
        if not n:
            return 0
        l = max(dfs(n.left), 0)
        r = max(dfs(n.right), 0)
        best = max(best, n.val + l + r)
        return n.val + max(l, r)
    dfs(root)
    return best

class Codec:
    def serialize(self, root):
        vals = []
        def dfs(n):
            if not n:
                vals.append('#'); return
            vals.append(str(n.val))
            dfs(n.left); dfs(n.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        it = iter(data.split(','))
        def dfs():
            v = next(it)
            if v == '#': return None
            n = TreeNode(int(v))
            n.left, n.right = dfs(), dfs()
            return n
        return dfs()

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False

    def insert(self, w):
        cur = self
        for c in w:
            cur = cur.children.setdefault(c, Trie())
        cur.end = True

    def search(self, w):
        cur = self._walk(w)
        return bool(cur) and cur.end

    def startsWith(self, p):
        return self._walk(p) is not None

    def _walk(self, w):
        cur = self
        for c in w:
            if c not in cur.children:
                return None
            cur = cur.children[c]
        return cur

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, w):
        cur = self.root
        for c in w:
            cur = cur.setdefault(c, {})
        cur['$'] = True

    def search(self, w):
        def dfs(node, i):
            if i == len(w):
                return node.get('$', False)
            c = w[i]
            if c == '.':
                return any(dfs(child, i + 1) for k, child in node.items() if k != '$')
            return c in node and dfs(node[c], i + 1)
        return dfs(self.root, 0)

def findWords(board, words):
    root = {}
    for w in words:
        cur = root
        for c in w:
            cur = cur.setdefault(c, {})
        cur['$'] = w
    rows, cols = len(board), len(board[0])
    out = []
    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node:
            return
        nxt = node[ch]
        if '$' in nxt:
            out.append(nxt.pop('$'))
        board[r][c] = '#'
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                dfs(nr, nc, nxt)
        board[r][c] = ch
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return out

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.h = nums
        heapq.heapify(self.h)
        while len(self.h) > k:
            heapq.heappop(self.h)

    def add(self, v):
        heapq.heappush(self.h, v)
        if len(self.h) > self.k:
            heapq.heappop(self.h)
        return self.h[0]

import heapq

def lastStoneWeight(stones):
    h = [-s for s in stones]
    heapq.heapify(h)
    while len(h) > 1:
        a, b = -heapq.heappop(h), -heapq.heappop(h)
        if a != b:
            heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

import heapq

def kClosest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

import heapq

def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

from collections import Counter

def leastInterval(tasks, n):
    cnt = Counter(tasks)
    mx = max(cnt.values())
    most = sum(1 for v in cnt.values() if v == mx)
    return max(len(tasks), (mx - 1) * (n + 1) + most)

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated)
        self.hi = []  # min-heap

    def addNum(self, n):
        heapq.heappush(self.lo, -n)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

def subsets(nums):
    out = [[]]
    for n in nums:
        out += [s + [n] for s in out]
    return out

def combinationSum(candidates, target):
    out = []
    def bt(start, remain, path):
        if remain == 0:
            out.append(path[:]); return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c <= remain:
                path.append(c)
                bt(i, remain - c, path)
                path.pop()
    bt(0, target, [])
    return out

def permute(nums):
    out = []
    def bt(path, used):
        if len(path) == len(nums):
            out.append(path[:]); return
        for i, n in enumerate(nums):
            if not used[i]:
                used[i] = True
                path.append(n)
                bt(path, used)
                path.pop()
                used[i] = False
    bt([], [False] * len(nums))
    return out

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
            return False
        tmp, board[r][c] = board[r][c], '#'
        ok = any(dfs(r + dr, c + dc, i + 1)
                 for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = tmp
        return ok
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

def solveNQueens(n):
    out = []
    cols, d1, d2 = set(), set(), set()
    board = [['.'] * n for _ in range(n)]
    def bt(r):
        if r == n:
            out.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or r + c in d1 or r - c in d2:
                continue
            cols.add(c); d1.add(r + c); d2.add(r - c)
            board[r][c] = 'Q'
            bt(r + 1)
            board[r][c] = '.'
            cols.remove(c); d1.remove(r + c); d2.remove(r - c)
    bt(0)
    return out

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(r + dr, c + dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
    return max((dfs(r, c) for r in range(rows) for c in range(cols)), default=0)

def cloneGraph(node):
    if not node:
        return None
    mp = {}
    def dfs(n):
        if n in mp:
            return mp[n]
        clone = Node(n.val)
        mp[n] = clone
        for nb in n.neighbors:
            clone.neighbors.append(dfs(nb))
        return clone
    return dfs(node)

from collections import deque
INF = 2147483647

def wallsAndGates(rooms):
    rows, cols = len(rooms), len(rooms[0])
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque(); fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r, c, 0))
            elif grid[r][c] == 1: fresh += 1
    minutes = 0
    while q:
        r, c, t = q.popleft()
        minutes = t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2; fresh -= 1
                q.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

def pacificAtlantic(h):
    rows, cols = len(h), len(h[0])
    pac, atl = set(), set()
    def dfs(r, c, visited, prev):
        if (r, c) in visited or r < 0 or c < 0 or r >= rows or c >= cols or h[r][c] < prev:
            return
        visited.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(r + dr, c + dc, visited, h[r][c])
    for c in range(cols):
        dfs(0, c, pac, h[0][c])
        dfs(rows - 1, c, atl, h[rows - 1][c])
    for r in range(rows):
        dfs(r, 0, pac, h[r][0])
        dfs(r, cols - 1, atl, h[r][cols - 1])
    return list(pac & atl)

def solve(board):
    if not board:
        return
    rows, cols = len(board), len(board[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'S'
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(r + dr, c + dc)
    for r in range(rows):
        dfs(r, 0); dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c); dfs(rows - 1, c)
    for r in range(rows):
        for c in range(cols):
            board[r][c] = 'O' if board[r][c] == 'S' else 'X'

from collections import defaultdict, deque

def canFinish(n, prerequisites):
    graph = defaultdict(list)
    indeg = [0] * n
    for a, b in prerequisites:
        graph[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        c = q.popleft(); done += 1
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return done == n

from collections import defaultdict, deque

def findOrder(n, prerequisites):
    graph = defaultdict(list)
    indeg = [0] * n
    for a, b in prerequisites:
        graph[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        c = q.popleft(); order.append(c)
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []

def findRedundantConnection(edges):
    parent = list(range(len(edges) + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]
        parent[ru] = rv

def countComponents(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    comp = n
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            comp -= 1
    return comp

from collections import defaultdict, deque

def ladderLength(begin, end, wordList):
    if end not in wordList:
        return 0
    L = len(begin)
    pat = defaultdict(list)
    for w in wordList:
        for i in range(L):
            pat[w[:i] + '*' + w[i + 1:]].append(w)
    q = deque([(begin, 1)]); seen = {begin}
    while q:
        w, d = q.popleft()
        for i in range(L):
            key = w[:i] + '*' + w[i + 1:]
            for nb in pat[key]:
                if nb == end: return d + 1
                if nb not in seen:
                    seen.add(nb)
                    q.append((nb, d + 1))
    return 0

def climbStairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def minCostClimbingStairs(cost):
    a, b = 0, 0
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i - 1], a + cost[i - 2])
    return b

def rob(nums):
    a, b = 0, 0
    for n in nums:
        a, b = b, max(b, a + n)
    return b

def rob(nums):
    if len(nums) == 1:
        return nums[0]
    def line(arr):
        a, b = 0, 0
        for n in arr:
            a, b = b, max(b, a + n)
        return b
    return max(line(nums[1:]), line(nums[:-1]))

def longestPalindrome(s):
    best = ''
    for i in range(len(s)):
        for l, r in ((i, i), (i, i + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(best):
                    best = s[l:r + 1]
                l -= 1; r += 1
    return best

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    a, b = 1, 1
    for i in range(1, len(s)):
        cur = 0
        if s[i] != '0':
            cur += b
        two = int(s[i - 1:i + 1])
        if 10 <= two <= 26:
            cur += a
        a, b = b, cur
    return b

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] <= amount else -1

def maxProduct(nums):
    res = lo = hi = nums[0]
    for n in nums[1:]:
        a, b = n * lo, n * hi
        lo, hi = min(n, a, b), max(n, a, b)
        res = max(res, hi)
    return res

def wordBreak(s, wordDict):
    words = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

import bisect

def lengthOfLIS(nums):
    tails = []
    for n in nums:
        i = bisect.bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n
    return len(tails)

def uniquePaths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[-1]

def longestCommonSubsequence(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

def minDistance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

def maxProfit(prices):
    hold, sold, rest = -float('inf'), 0, 0
    for p in prices:
        prev_hold = hold
        hold = max(hold, rest - p)
        rest = max(rest, sold)
        sold = prev_hold + p
    return max(sold, rest)