Q: Write a function int solution(int A); that, given an array A of N integers, returns the smallest natural number that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
• each element of array A is an 32-bit signed int
• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N).
* Elements of input arrays can be modified.
https://leetcode.com/problems/first-missing-positive/description/ is similar but O(1) space and average O(N) time!
—— my analysis —–
The mutable and O(1) space hints at — saving array indices as payload !
—- Idea A:
first scan to swap non-positives to the end and remember the new boundary (say #111).
In the same scan also determine min and max. Suppose min=55.
Another scan to reduce all payloads by 55 so they fall in the range of 0 to max-55.
Now use CSY technique .. check array@0-N in-situ #Nsdq#contrived
—-solutionB: make_heap O(1) space but O(N logN) time. Build a min-heap based on the array in O(1) space, then keep calling min().
- make_heap shows random access container (vector used in demo), and “rearrange”, implying O(1) space
- make_heap shows O(N) to construct the heap
min() is O(1) but delete_min() is O(log N), so overall we probably get O(N logN)
—-solutionC: radix sort. https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations shows an in-place binary radix sort.
First pass to transform all negative numbers to 0. Then iterate the sorted array and check for the earliest “gap”. Worst case — you get 1,2,3… without gap, so answer is the 1+ largest array element.
O(W*N) where W is width of the largest integer. If we assume 64-bit then W is a constant:)
http://www.drdobbs.com/parallel/parallel-in-place-radix-sort-simplified/229000734 is another in-place radix sort.