Constraints

• 0 <= number of list entries <= 10^4
• Node values are 32-bit signed integers
• The input list is a valid level-order encoding of a binary tree
• The tree may be empty and does not need to be balanced

Examples

Solution

def solution(level_order):
    from collections import deque

    if not level_order or level_order[0] is None:
        return []

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

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

    root = TreeNode(level_order[0])
    queue = deque([root])
    i = 1

    while queue and i < len(level_order):
        node = queue.popleft()

        if i < len(level_order):
            left_val = level_order[i]
            i += 1
            if left_val is not None:
                node.left = TreeNode(left_val)
                queue.append(node.left)

        if i < len(level_order):
            right_val = level_order[i]
            i += 1
            if right_val is not None:
                node.right = TreeNode(right_val)
                queue.append(node.right)

    right_view = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        rightmost = None

        for _ in range(level_size):
            node = queue.popleft()
            rightmost = node.val

            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        right_view.append(rightmost)

    return right_view

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

Hints

1. A breadth-first traversal lets you process the tree level by level; the last node you visit in each level is the visible one.
2. An alternative is depth-first search that visits right children before left children and records the first node seen at each depth.

Constraints

• 0 <= n <= 10^5
• Each element of nums is a 32-bit signed integer
• k is a 32-bit signed integer
• An O(n) or near-O(n) solution is expected

Examples

Solution

def solution(nums, k):
    prefix_counts = {0: 1}
    prefix_sum = 0
    total = 0

    for num in nums:
        prefix_sum += num
        total += prefix_counts.get(prefix_sum - k, 0)
        prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1

    return total

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

Hints

1. Track a running prefix sum as you scan the array.
2. If `current_sum - k` has appeared before, then each previous occurrence marks a subarray ending at the current index with sum `k`.