= Solution
A fixed <array> containing the distinct seen <integers> needs capacity at most $N$, because at most one new distinct value is introduced per result entry. Its auxiliary space is therefore \b[$O(N)$], rather than the bitmap's $O(M)$ universe storage. A size field identifies the occupied prefix; insertion first checks membership, and appends only when absent.
An unsorted occupied prefix needs linear membership scans, giving \b[$O(N^2)$ total work] by the same summation as in the original version. Keeping it sorted permits <binary search> membership in $O(\log N)$, but inserting a new value can shift $O(N)$ entries, so the overall worst-case upper bound remains quadratic. Unlike a bitmap, the space cost depends on the number of stored values rather than their largest possible numerical magnitude. Compared with part (a)(ii), this extra set <array> also duplicates information already present in the output prefix; its principal benefit is a separate set interface, not an automatic asymptotic speedup.
Back to article page
