ID Allocator with Assign and Release
Problem statement
An ID allocator manages the IDs 0, 1, ..., n - 1. At the start every ID is free. Process the operations operations[0], operations[1], ... in order, and record one result for each:
"assign": hand out the smallest free ID, mark it as in use, and record it. If every ID is in use, nothing changes and the result is-1."release":values[i]is an ID. If it is between0andn - 1and is in use, mark it as free and record1. Otherwise (it is outside that range, or it is already free), nothing changes and the result is0.
If n <= 0, the allocator has no valid IDs: every assign records -1 and every release records 0.
values[i] is only used by a release; for an assign it is 0. Return the recorded results in order.
Function
runIdAllocator(n: int, operations: String[], values: int[]) → int[]Examples
Example 1
n = 3operations = ["assign","assign","release","assign","assign","assign","release"]values = [0,0,0,0,0,0,5]return = [0,1,1,0,2,-1,0]- The first two
assigncalls hand out the smallest free IDs,0and1. release 0frees ID0, so it records1.- The next
assignreturns0again, because it is now the smallest free ID. The one after that returns2. - All three IDs are in use, so the last
assignrecords-1. release 5names an ID outside0to2, so it records0.
Example 2
n = 2operations = ["release","assign","release","release","assign"]values = [1,0,0,0,0]return = [0,0,1,0,0]release 1comes before ID1was ever handed out, so it records0.assignreturns0, andrelease 0frees it and records1.- The second
release 0finds ID0already free, so it records0and changes nothing. - The last
assignreturns0.
Example 3
n = 0operations = ["assign","release"]values = [0,0]return = [-1,0]With n = 0 there are no valid IDs. assign records -1 and release 0 records 0.
Constraints
-2000 <= n <= 20001 <= operations.length <= 2000values.length == operations.length- Each
operations[i]is"assign"or"release". -10^9 <= values[i] <= 10^9values[i] == 0wheneveroperations[i]is"assign".