 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 $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 $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.