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.
— idea A1
Now use CSY technique .. check array@0-N in-situ #Nsdq#contrived
— idea A2:
Use quicksort partition to anchor a random node. If it is a > 7, then discard higher section, to focus on lower section. During that scan also keep track of frequency of each int. If the lower section has no dupe numbers, then we can discard it and focus on the higher section.
However, if there are some dupes then this algo can’t discard any section.
—-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.