Complexity Analysis

def find_max(arr):
    mx = arr[0]
    for x in arr:
        if x > mx:
            mx = x
    return mx

def sum_and_product(arr):
    total = 0
    for x in arr:
        total += x
    product = 1
    for x in arr:
        product *= x
    return total, product

def count_pairs(arr, target):
    count = 0
    seen = set()
    for x in arr:
        if target - x in seen:
            count += 1
        seen.add(x)
    return count

def all_pairs(arr):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(n):
            pairs.append((arr[i], arr[j]))
    return pairs

def print_upper_triangle(n):
    for i in range(n):
        for j in range(i, n):
            print(i, j)

def process(a, b):
    for x in a:
        print(x)
    for y in b:
        print(y)

def nested_different(a, b):
    for x in a:
        for y in b:
            print(x, y)

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def count_digits(n):
    count = 0
    while n > 0:
        count += 1
        n //= 10
    return count

def powers_of_two(n):
    result = []
    x = 1
    while x < n:
        result.append(x)
        x *= 2
    return result

def power(base, exp):
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

def tree_height(node):
    if node is None:
        return 0
    left = tree_height(node.left)
    right = tree_height(node.right)
    return 1 + max(left, right)

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

def group_anagrams(words):
    groups = {}
    for w in words:
        key = tuple(sorted(w))
        groups.setdefault(key, []).append(w)
    return list(groups.values())

def first_unique(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    for c in s:
        if freq[c] == 1:
            return c
    return None

def bfs(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
    while queue:
        node = queue.pop(0)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

def rotate_matrix(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

def longest_common_subseq(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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 coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def find_duplicates(arr):
    arr.sort()
    dupes = []
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            dupes.append(arr[i])
    return dupes

def kth_largest(arr, k):
    arr.sort(reverse=True)
    return arr[k - 1]

def build_string(words):
    result = ""
    for w in words:
        result += w
    return result

def has_common(a, b):
    for x in a:
        if x in b:
            return True
    return False

def nested_with_break(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            if arr[j] == arr[i]:
                break

def remove_all(arr, val):
    while val in arr:
        arr.remove(val)
    return arr

def subsets(nums):
    result = [[]]
    for x in nums:
        result += [s + [x] for s in result]
    return result

def permutations(arr, path=[]):
    if not arr:
        return [path]
    result = []
    for i in range(len(arr)):
        result += permutations(
            arr[:i] + arr[i+1:],
            path + [arr[i]]
        )
    return result