Add, Remove, and Find Values in a Bounded Integer Universe

Implement a set that supports adding, removing, and searching integer values from a known bounded range.

Implement bounded_set(limit: int, operations: string[][]) -> bool[]. Each operation is [action,value], with action ADD, REMOVE, or CONTAINS and value represented as a decimal string. Return one boolean per operation.

Constraints & Assumptions

The source emphasizes that the hidden bounded-value range makes a simpler bucket/direct-address representation possible. This practice contract states that range explicitly and defines set semantics where duplicate behavior was unreported.

• 1 <= limit <= 1000000; every value satisfies 0 <= value < limit.
• At most 200000 operations. The set is initially empty.
• ADD returns true if it inserted a previously absent value, false if already present.
• REMOVE returns true if it removed a present value, false if absent.
• CONTAINS returns whether the value is currently present.
• Use O(limit) state and support each operation in worst-case O(1) time after initialization. Account separately for initializing that state.

Example

limit = 5
operations = [["ADD","2"],["ADD","2"],["CONTAINS","2"],
              ["REMOVE","2"],["CONTAINS","2"],["REMOVE","2"]]
result = [true,false,true,true,false,false]

Explain why the known range changes the data-structure choice and what you would use if values were sparse across an enormous or unknown universe. Clarify the distinction between membership and maintaining sorted iteration.

Hint: Use the contract before adding machinery

Every possible value has a valid small array index. Decide what one bit or boolean at that index should represent.

Implement a Set over a Bounded Integer Universe

Approach

Allocate one false membership slot for each value from zero through limit-1. Its invariant is that present[v] is true exactly when v belongs to the set. ADD sets the slot and reports whether it changed from false; REMOVE clears it and reports the previous value; CONTAINS simply reads it. These local operations preserve the invariant and naturally implement duplicate semantics. Initialization costs O(limit) time and state; each set operation then performs worst-case O(1) array accesses, with input-token parsing accounted separately. A sparse enormous or unknown universe would favor a hash set for expected constant-time access or a balanced search tree for logarithmic worst-case access. Direct addressing here uses the bounded range rather than general-purpose hashing. Membership does not itself provide efficient sparse sorted iteration: scanning this representation in value order costs O(limit), while an ordered set offers sorted traversal over stored values.

• Time complexity: O(limit) initialization, O(1) set work per operation plus decimal-token parsing
• Space complexity: O(limit) state, excluding output