Stage IV: Hard Questions

def jump(nums: list[int]) -> int:
    jumps = 0
    current_farthest = 0
    next_farthest = 0
for i in range(len(nums) - 1):
    next_farthest = max(next_farthest, i + nums[i])
    
    if i == current_farthest:
        jumps += 1
        current_farthest = next_farthest
        
return jumps

from collections import Counter
def leastInterval(tasks: list[str], n: int) -> int:
    if n == 0:
        return len(tasks)
counts = Counter(tasks)
max_freq = max(counts.values())

# Count how many tasks have the max frequency
num_max_freq_tasks = sum(1 for count in counts.values() if count == max_freq)

# Calculate the number of blocks needed based on the most frequent task
# (max_freq - 1) full blocks, each of size (n + 1)
# plus the number of tasks in the last block
interval_time = (max_freq - 1) * (n + 1) + num_max_freq_tasks

# The result is the max of this calculated time and the actual number of tasks
# (in case there's no idle time needed)
return max(len(tasks), interval_time)

def candy(ratings: list[int]) -> int:
    n = len(ratings)
    candies = [1] * n
# First pass: Left to Right
for i in range(1, n):
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1
        
# Second pass: Right to Left
for i in range(n - 2, -1, -1):
    if ratings[i] > ratings[i+1]:
        candies[i] = max(candies[i], candies[i+1] + 1)
        
return sum(candies)

def solveNQueens(n: int) -> list[list[str]]:
    cols = set()
    pos_diag = set() # (r + c)
    neg_diag = set() # (r - c)
result = []
board = [["."] * n for _ in range(n)]

def backtrack(r):
    if r == n:
        copy = ["".join(row) for row in board]
        result.append(copy)
        return
        
    for c in range(n):
        if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
            continue # Prune this path
        
        # Choose
        cols.add(c)
        pos_diag.add(r + c)
        neg_diag.add(r - c)
        board[r][c] = "Q"
        
        # Explore
        backtrack(r + 1)
        
        # Un-choose
        cols.remove(c)
        pos_diag.remove(r + c)
        neg_diag.remove(r - c)
        board[r][c] = "."
        
backtrack(0)
return result

def solveSudoku(board: list[list[str]]) -> None:
    def is_valid(r, c, digit):
        for i in range(9):
            if board[i][c] == digit: return False # Check column
            if board[r][i] == digit: return False # Check row
            if board[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == digit: return False # Check 3x3 box
        return True
def backtrack(r, c):
    if r == 9: # Reached the end of the board
        return True
    
    # Move to the next row if current column is out of bounds
    next_r, next_c = (r, c + 1) if c < 8 else (r + 1, 0)
    
    if board[r][c] != '.':
        return backtrack(next_r, next_c)
    
    for digit_val in range(1, 10):
        digit_str = str(digit_val)
        if is_valid(r, c, digit_str):
            # Choose
            board[r][c] = digit_str
            # Explore
            if backtrack(next_r, next_c):
                return True
            # Un-choose (backtrack)
            board[r][c] = '.'
    return False

backtrack(0, 0)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
root = TrieNode()
for w in words:
node = root
for c in w:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_word = True
    ROWS, COLS = len(board), len(board[0])
    result, visited = set(), set()
    
    def backtrack(r, c, node, word):
        if (r < 0 or c < 0 or r >= ROWS or c >= COLS or 
                board[r][c] not in node.children or (r, c) in visited):
            return
        
        # Choose
        visited.add((r, c))
        node = node.children[board[r][c]]
        word += board[r][c]
        if node.is_word:
            result.add(word)
        
        # Explore
        backtrack(r + 1, c, node, word)
        backtrack(r - 1, c, node, word)
        backtrack(r, c + 1, node, word)
        backtrack(r, c - 1, node, word)
        
        # Un-choose
        visited.remove((r, c))
        
    for r in range(ROWS):
        for c in range(COLS):
            backtrack(r, c, root, "")
            
    return list(result)

def minDistance(word1: str, word2: str) -> int:
    M, N = len(word1), len(word2)
    dp = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(M + 1): dp[i][N] = M - i
for j in range(N + 1): dp[M][j] = N - j

for i in range(M - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if word1[i] == word2[j]:
            dp[i][j] = dp[i + 1][j + 1]
        else:
            dp[i][j] = 1 + min(dp[i][j + 1], dp[i + 1][j], dp[i + 1][j + 1])
return dp[0][0]

def isMatch(s: str, p: str) -> bool:
    memo = {}
    def dp(i, j):
        if (i, j) in memo: return memo[(i, j)]
        if j == len(p): return i == len(s)
    first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')

    if j + 1 < len(p) and p[j+1] == '*':
        # Two choices for '*': use it zero times, or use it one time
        res = dp(i, j + 2) or (first_match and dp(i + 1, j))
    else:
        res = first_match and dp(i + 1, j + 1)

    memo[(i,j)] = res
    return res
return dp(0,0)

def maxCoins(nums: list[int]) -> int:
    nums = [1] + nums + [1]
    memo = {}
    def dp(l, r):
        if l > r: return 0
        if (l, r) in memo: return memo[(l,r)]
    res = 0
    for i in range(l, r + 1):
        # Assume nums[i] is the last balloon to be burst in (l,r)
        coins = nums[l-1] * nums[i] * nums[r+1]
        coins += dp(l, i - 1) + dp(i + 1, r)
        res = max(res, coins)
    memo[(l,r)] = res
    return res
return dp(1, len(nums) - 2)

def maxProfit(prices: list[int]) -> int:
    # State:
    # t1_cost: min cost of the first transaction's buy
    # t1_profit: max profit of the first transaction's sell
    # t2_cost: min cost of the second transaction's buy
    # t2_profit: max profit of the second transaction's sell
    t1_cost, t2_cost = float('inf'), float('inf')
    t1_profit, t2_profit = 0, 0
for price in prices:
    # For transaction 1
    t1_cost = min(t1_cost, price)
    t1_profit = max(t1_profit, price - t1_cost)
    # For transaction 2
    t2_cost = min(t2_cost, price - t1_profit)
    t2_profit = max(t2_profit, price - t2_cost)

return t2_profit