Constraints

• 0 <= n <= 10^18
• Bulbs are 1-indexed
• A toggle changes off to on, or on to off

Examples

Solution

def solution(n):
    import math
    if n <= 0:
        return 0
    return math.isqrt(n)

Time complexity: O(1). Space complexity: O(1).

Hints

1. A bulb ends up on only if it is toggled an odd number of times.
2. Most divisors come in pairs. Which numbers have an unpaired divisor?

Constraints

• 1 <= len(words) <= 10^5
• 1 <= len(queries) <= 10^5
• Each word is a non-empty string
• Total processing should avoid rescanning the full words array for every query

Examples

Solution

def solution(words, queries):
    positions = {}
    for i, word in enumerate(words):
        positions.setdefault(word, []).append(i)

    cache = {}
    answer = []

    for w1, w2 in queries:
        key = (w1, w2) if w1 <= w2 else (w2, w1)
        if key in cache:
            answer.append(cache[key])
            continue

        if w1 not in positions or w2 not in positions:
            cache[key] = -1
            answer.append(-1)
            continue

        if w1 == w2:
            pos = positions[w1]
            if len(pos) < 2:
                dist = -1
            else:
                dist = min(pos[i] - pos[i - 1] for i in range(1, len(pos)))
            cache[key] = dist
            answer.append(dist)
            continue

        a = positions[w1]
        b = positions[w2]
        i = j = 0
        best = float('inf')

        while i < len(a) and j < len(b):
            best = min(best, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1

        cache[key] = best
        answer.append(best)

    return answer

Time complexity: O(n + sum over uncached queries of (occ(word1) + occ(word2)))). Space complexity: O(n + u).

Hints

1. Store all positions for each distinct word in sorted order as you scan the list once.
2. To compare two sorted position lists efficiently, try a two-pointer walk.

Constraints

• 0 <= number of list entries <= 10^4
• Node values are integers
• If level_order is empty, the tree is empty

Examples

Solution

def solution(level_order):
    if not level_order:
        return []

    class Node:
        __slots__ = ('val', 'left', 'right')

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

    nodes = [None if v is None else Node(v) for v in level_order]

    for i, node in enumerate(nodes):
        if node is None:
            continue
        left_i = 2 * i + 1
        right_i = 2 * i + 2
        if left_i < len(nodes):
            node.left = nodes[left_i]
        if right_i < len(nodes):
            node.right = nodes[right_i]

    root = nodes[0]
    if root is None:
        return []

    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        node.left, node.right = node.right, node.left
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    output = []
    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node is None:
            output.append(None)
            continue
        output.append(node.val)
        queue.append(node.left)
        queue.append(node.right)

    while output and output[-1] is None:
        output.pop()

    return output

Time complexity: O(n). Space complexity: O(n).

Hints

1. Inversion is local: at every node, swap the left and right pointers.
2. A breadth-first traversal is an easy way to process every node iteratively.

Constraints

• 0 <= number of rows <= 300
• 0 <= number of columns <= 300
• All rows have the same length
• Adjacency is only up, down, left, and right

Examples

Solution

def solution(grid):
    if not grid:
        return 0
    rows = len(grid)
    cols = len(grid[0]) if grid[0] else 0
    if cols == 0:
        return 0

    g = [list(row) for row in grid]
    count = 0

    for r in range(rows):
        for c in range(cols):
            if g[r][c] != '1':
                continue

            count += 1
            stack = [(r, c)]
            g[r][c] = '0'

            while stack:
                x, y = stack.pop()

                if x > 0 and g[x - 1][y] == '1':
                    g[x - 1][y] = '0'
                    stack.append((x - 1, y))
                if x + 1 < rows and g[x + 1][y] == '1':
                    g[x + 1][y] = '0'
                    stack.append((x + 1, y))
                if y > 0 and g[x][y - 1] == '1':
                    g[x][y - 1] = '0'
                    stack.append((x, y - 1))
                if y + 1 < cols and g[x][y + 1] == '1':
                    g[x][y + 1] = '0'
                    stack.append((x, y + 1))

    return count

Time complexity: O(m * n). Space complexity: O(m * n) in the worst case due to the exploration stack.

Hints

1. When you find an unvisited land cell, explore its whole component with DFS or BFS.
2. Mark cells as visited so you do not count the same island more than once.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• 0 <= k <= len(nums)
• Each element of nums is either 0 or 1
• The chosen window length cannot exceed len(nums)

Examples

Solution

def solution(nums, k):
    n = len(nums)
    if n == 0:
        return (0, -1)

    left = 0
    zeros = 0
    best_len = 0
    best_start = 0

    for right in range(2 * n):
        if nums[right % n] == 0:
            zeros += 1

        while zeros > k or right - left + 1 > n:
            if nums[left % n] == 0:
                zeros -= 1
            left += 1

        if left < n:
            cur_len = right - left + 1
            if cur_len > best_len or (cur_len == best_len and left < best_start):
                best_len = cur_len
                best_start = left

    return (best_len, best_start)

Time complexity: O(n). Space complexity: O(1).

Hints

1. A standard sliding window works for 'at most k zeros', but circularity suggests looking at a doubled array.
2. Even with doubling, do not allow a window longer than the original array length.

Constraints

• 0 <= number of list entries <= 10^4
• Node values are integers
• The intended solution should run in O(n)

Examples

Solution

def solution(level_order):
    if not level_order:
        return []

    class Node:
        __slots__ = ('val', 'left', 'right')

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

    nodes = [None if v is None else Node(v) for v in level_order]

    for i, node in enumerate(nodes):
        if node is None:
            continue
        left_i = 2 * i + 1
        right_i = 2 * i + 2
        if left_i < len(nodes):
            node.left = nodes[left_i]
        if right_i < len(nodes):
            node.right = nodes[right_i]

    root = nodes[0]
    if root is None:
        return []

    import sys
    sys.setrecursionlimit(1_000_000)

    result = []

    def dfs(node):
        if node is None:
            return -1
        h_left = dfs(node.left)
        h_right = dfs(node.right)
        h = 1 + max(h_left, h_right)
        if h == len(result):
            result.append([])
        result[h].append(node.val)
        return h

    dfs(root)
    return result

Time complexity: O(n). Space complexity: O(n).

Hints

1. Instead of physically removing leaves round by round, compute each node's height from the bottom.
2. All nodes with the same bottom-up height are removed in the same round.