List Unallocated Experiment Buckets

Problem Statement

In an experimentation platform, user traffic is hashed into total_buckets discrete buckets indexed from 0 to total_buckets - 1. An experiment configuration assigns subsets of these buckets to a control group and one or more enabled_groups (treatment variants).

Due to manual configuration or upstream errors, input allocations may contain:

• Duplicate bucket IDs within the same group or across different groups.
• Out-of-bounds bucket IDs (negative integers or integers >= total_buckets), which should be ignored.

Write a function find_unallocated_buckets that returns an ascending list of all bucket IDs in [0, total_buckets - 1] that have not been assigned to either the control group or any enabled group.

Function Signature

def find_unallocated_buckets(
    total_buckets: int,
    control: list[int],
    enabled_groups: list[list[int]]
) -> list[int]:
    pass

Input & Output Format

• Input:
  • total_buckets: Non-negative integer representing the capacity range [0, total_buckets - 1].
  • control: A list of integer bucket IDs assigned to control.
  • enabled_groups: A list of lists, where each sublist contains integer bucket IDs assigned to a treatment variant.
• Output:
  • A list of unique integers representing unallocated buckets, sorted in ascending order.

Examples

Example 1

total_buckets = 10
control = [0, 2, 2, 15]  # 15 is out of bounds, 2 is duplicated
enabled_groups = [
    [3, 4],
    [4, 7]  # 4 is duplicated across groups
]

# Output: [1, 5, 6, 8, 9]

Explanation: Valid assigned buckets are 0, 2, 3, 4, and 7. Buckets 1, 5, 6, 8, and 9 remain unassigned.

Example 2

total_buckets = 4
control = [0, 1]
enabled_groups = [[2, 3]]

# Output: []

Explanation: All buckets 0 through 3 are allocated.

Constraints

• 1 <= total_buckets <= 100,000
• 0 <= len(control) <= 100,000
• 0 <= len(enabled_groups) <= 1,000
• 0 <= sum(len(group) for group in enabled_groups) <= 100,000
• Bucket IDs in inputs can be any 32-bit signed integer.