Google Leetcode Study Guide

def romanToInt(s: str) -> int:
    roman_to_int = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
    total = 0
    prev_value = 0
    for char in reversed(s):
        value = roman_to_int[char]
        if value < prev_value:
            total -= value
        else:
            total += value
        prev_value = value
    return total

# Complexity Analysis
# - Time Complexity: O(n), where n is the length of the string.
# - Space Complexity: O(1), constant space usage.

class Logger:
    def __init__(self):
        self.message_timestamp_map = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.message_timestamp_map or timestamp - self.message_timestamp_map[message] >= 10:
            self.message_timestamp_map[message] = timestamp
            return True
        return False

# Complexity Analysis
# - Time Complexity: O(1), average time for dictionary operations.
# - Space Complexity: O(n), where n is the number of unique messages logged.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy_head = ListNode(0)
    current, carry = dummy_head, 0

    while l1 or l2:
        x = l1.val if l1 else 0
        y = l2.val if l2 else 0
        sum = carry + x + y
        carry = sum // 10
        current.next = ListNode(sum % 10)
        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    if carry:
        current.next = ListNode(carry)

    return dummy_head.next

# Complexity Analysis
# - Time Complexity: O(max(m, n)), where m and n are the lengths of the two input lists.
# - Space Complexity: O(max(m, n)), for the linked list storage.

def lengthOfLIS(nums: list[int]) -> int:
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(0, i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# Complexity Analysis
# - Time Complexity: O(n^2), where n is the length of nums, due to nested loops for comparisons.
# - Space Complexity: O(n), for the dp array storing lengths of subsequence up to each element.

def longestPalindrome(s: str) -> str:
    if len(s) < 2:
        return s

    start, max_length = 0, 1

    def expand_from_center(left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    for i in range(len(s)):
        len1 = expand_from_center(i, i)
        len2 = expand_from_center(i, i + 1)
        max_len = max(len1, len2)
        
        if max_len > max_length:
            max_length = max_len
            start = i - (max_len - 1) // 2

    return s[start:start + max_length]

# Complexity Analysis
# - Time Complexity: O(n^2), where n is the length of the string due to expanding around centers.
# - Space Complexity: O(1), no extra space besides variables.

def longestCommonPrefix(strs: list[str]) -> str:
    if not strs:
        return ""
    
    prefix = strs[0]
    for s in strs[1:]:
        while s.find(prefix) != 0:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

# Complexity Analysis
# - Time Complexity: O(n * m), where n is the number of strings and m is the length of the shortest string. 
# - Space Complexity: O(1), constant additional space.

def threeSumClosest(nums: list[int], target: int) -> int:
    nums.sort()
    closest_sum = float('inf')
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return target
    
    return closest_sum

# Complexity Analysis
# - Time Complexity: O(n^2), for sorting and two-pointer approach.
# - Space Complexity: O(1), excluding input space.

def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    first, second = 1, 2
    for _ in range(3, n + 1):
        first, second = second, first + second
    
    return second

# Complexity Analysis
# - Time Complexity: O(n), single pass for step computation.
# - Space Complexity: O(1), only two variables needed.

import functools

def largestNumber(nums: list[int]) -> str:
    str_nums = list(map(str, nums))
    compare = lambda x, y: (1 if x + y < y + x else -1)
    str_nums.sort(key=functools.cmp_to_key(compare))
    largest = ''.join(str_nums).lstrip('0')
    return largest or '0'

# Complexity Analysis
# - Time Complexity: O(n log n), due to sorting.
# - Space Complexity: O(n), for storing string representations.

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) < 3:
        return max(nums)
    
    rob1, rob2 = 0, 0
    for n in nums:
        new_rob = max(rob2, rob1 + n)
        rob1 = rob2
        rob2 = new_rob
    
    return rob2

# Complexity Analysis
# - Time Complexity: O(n), single iteration over house values.
# - Space Complexity: O(1), constant space usage with two variables.

def containsDuplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

# Complexity Analysis
# - Time Complexity: O(n), where n is the number of elements in nums (average case for set operations).
# - Space Complexity: O(n), space needed to store elements in the set.

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

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

# Complexity Analysis
# - Time Complexity: O(H + k), where H is the tree's height.
# - Space Complexity: O(H), stack space required for iterative in-order traversal.

from collections import defaultdict, deque

def findItinerary(tickets: list[list[str]]) -> list[str]:
    graph = defaultdict(deque)
    for src, dst in sorted(tickets):
        graph[src].append(dst)
    
    itinerary = []
    def dfs(airport):
        dests = graph[airport]
        while dests:
            dfs(dests.popleft())
        itinerary.append(airport)
    
    dfs('JFK')
    return itinerary[::-1]

# Complexity Analysis
# - Time Complexity: O(E log E), sorting the tickets and traversing each edge in the graph.
# - Space Complexity: O(E), storing the tickets in a graph.

def checkRecord(n: int) -> int:
    MOD = int(1e9+7)
    # dp[i][a][l] means on the i-th day, with `a` A's and `l` continuous L's
    dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    
    for i in range(1, n + 1):
        for a in range(2):
            for l in range(3):
                dp[i][a][0] = (dp[i][a][0] + dp[i-1][a][l]) % MOD  # P
                if a > 0:
                    dp[i][a][0] = (dp[i][a][0] + sum(dp[i-1][a-1][l] for l in range(3))) % MOD  # A
                if l < 2:
                    dp[i][a][l+1] = (dp[i][a][l+1] + dp[i-1][a][l]) % MOD  # L

    return sum(dp[n][a][l] for a in range(2) for l in range(3)) % MOD

# Complexity Analysis
# - Time Complexity: O(n), need to fill n*2*3 table.
# - Space Complexity: O(n), space for the dp table.

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    if not grid:
        return 0
        
    def dfs(r, c):
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == 0:
            return 0
        grid[r][c] = 0
        return (1 + dfs(r + 1, c) + dfs(r - 1, c) + 
                dfs(r, c + 1) + dfs(r, c - 1))

    max_area = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

    return max_area

# Complexity Analysis
# - Time Complexity: O(m * n), traverse the entire grid.
# - Space Complexity: O(m * n), which is the max size of the recursion stack.

from collections import deque

def racecar(target: int) -> int:
    queue = deque([(0, 0, 1)])  # (steps, position, speed)
    visited = set((0, 1))

    while queue:
        steps, position, speed = queue.popleft()
        
        # Move the car
        new_pos = position + speed
        new_speed = speed * 2
        if new_pos == target:
            return steps + 1
        if (new_pos, new_speed) not in visited:
            queue.append((steps + 1, new_pos, new_speed))
            visited.add((new_pos, new_speed))
        
        # Reverse the car (change direction)
        if (position, -1 if speed > 0 else 1) not in visited:
            queue.append((steps + 1, position, -1 if speed > 0 else 1))
            visited.add((position, -1 if speed > 0 else 1))

# Complexity Analysis
# - Time Complexity: O(T log T), where T is the target.
# - Space Complexity: O(T), due to the queue and visited set.

import random

def findSecretWord(words: list[str], master: 'Master') -> None:
    def match(s1, s2):
        return sum(c1 == c2 for c1, c2 in zip(s1, s2))
    
    for _ in range(10):
        guess = random.choice(words)
        x = master.guess(guess)
        words = [word for word in words if match(guess, word) == x]

# Complexity Analysis
# - Time Complexity: O(n), with n words depending on guess efficiency.
# - Space Complexity: O(n), maintaining lists of words.

def minAreaRect(points: list[list[int]]) -> int:
    points_set = set(map(tuple, points))
    min_area = float('inf')

    for i, p1 in enumerate(points):
        for j in range(i):
            p2 = points[j]
            if (p1[0] != p2[0] and p1[1] != p2[1] and (p1[0], p2[1]) in points_set and (p2[0], p1[1]) in points_set):
                min_area = min(min_area, abs(p1[0] - p2[0]) * abs(p1[1] - p2[1]))
    
    return min_area if min_area != float('inf') else 0

# Complexity Analysis
# - Time Complexity: O(n^2), finding rectangles by point comparison.
# - Space Complexity: O(n), storing points in a set.

def parseBoolExpr(expression: str) -> bool:
    def evaluate(exp):
        if exp == "t":
            return True
        if exp == "f":
            return False
        ops = {
            '|': any,
            '&': all,
            '!': lambda x: not x[0]
        }
        op = exp[0]
        op_func = ops[op]
        inside = []
        bal = 0
        last = 0
        for i, char in enumerate(exp[2:], 2):
            if char == '(':
                bal += 1
            elif char == ')':
                bal -= 1
            if char in "tf&|!," and bal == 0:
                if last != i:
                    res = evaluate(exp[last:i])
                    last = i + 1
                    inside.append(res)
        return op_func(inside)

    return evaluate(expression)

# Complexity Analysis
# - Time Complexity: O(n), processing expression symbols.
# - Space Complexity: O(n), storing intermediate evaluations.

def removeSubfolders(folder: list[str]) -> list[str]:
    folder.sort()
    result = []
    prev = ""

    for f in folder:
        if not prev or not f.startswith(prev + '/'):
            result.append(f)
            prev = f
    
    return result

# Complexity Analysis
# - Time Complexity: O(n log n), for sorting the folders.
# - Space Complexity: O(n), space for the result list.

def minNumberOperations(target: list[int]) -> int:
    operations = target[0]
    for i in range(1, len(target)):
        if target[i] > target[i - 1]:
            operations += target[i] - target[i - 1]
    return operations

# Complexity Analysis
# - Time Complexity: O(n), where n is the number of elements in the target.
# - Space Complexity: O(1), constant space usage.

def mergeAlternately(word1: str, word2: str) -> str:
    merged = []
    i = 0

    while i < len(word1) or i < len(word2):
        if i < len(word1):
            merged.append(word1[i])
        if i < len(word2):
            merged.append(word2[i])
        i += 1

    return ''.join(merged)

# Complexity Analysis
# - Time Complexity: O(n + m), where n and m are lengths of word1 and word2.
# - Space Complexity: O(n + m), space for merged result.

import collections
import sortedcontainers

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.stream = collections.deque()
        self.sorted_window = sortedcontainers.SortedList()

    def addElement(self, num: int) -> None:
        self.stream.append(num)
        if len(self.stream) > self.m:
            oldest = self.stream.popleft()
            self.sorted_window.remove(oldest)
        self.sorted_window.add(num)

    def calculateMKAverage(self) -> int:
        if len(self.sorted_window) < self.m:
            return -1  # Not enough data
        effective_window = self.sorted_window[self.k:self.m - self.k]
        return sum(effective_window) // len(effective_window)

# Complexity Analysis
# - Time Complexity for addElement: O(log m) due to insertion in a sorted list.
# - Time Complexity for calculateMKAverage: O(m) for summing central elements.
# - Space Complexity: O(m), space to store elements in the window.

def createCounter(start: int = 0):
    def counter():
        nonlocal start
        start += 1
        return start
    return counter

# Usage:
# counter_instance = createCounter()
# print(counter_instance())  # 1
# print(counter_instance())  # 2