It is certain that to get **O(n) time complexity** and to do in **constant space** O(n) time complexity sorting technique need to be used, any of the following sorts counting sort, radix sort, bucket sort can be used.

As the input array can contain **negative integers** counting sort may not be applied here as we use keys as index in counting sort and it has memory overhead too, but when the input array has many **duplicates** then counting sort performs better it's good to discuss such trade offs with interviewer.

Radix sort is a specific type of bucket sort, It starts with the top n-bit or n-digits and may sort those buckets using a radix sort until every entry is sorted. So if the elements in the input array are single digit integers in the **range [-9,9]** then essentially radix sort and bucket sort are similar.

Bucket sort is the best sorting technique that might be used here because when the **input is uniformly** **distributed over a range**(here the elements of the input array are in range [-9,9]) bucket sort performs in O(n) time complexity and O(1) space complexity.

**Counting sort** -- simple buckets, simple processing, memory overhead, performs well when input has many duplicates.

**Radix sort** -- simple buckets, sophisticated processing, speed overhead (and still need additional static memory)

**Bucket sort** -- sophisticated buckets, simple processing, requires dynamic memory, good in average compared to counting and radix sorts.

```
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for (int i = 0; i < n; ++i)
{
int digit = A[i];
while (digit <= n && digit > 0 && A[digit - 1] != digit)
{
swap(A[digit - 1], A[i]);
digit = A[i];
}
}
for (int i = 0; i < n; ++i)
{
if (A[i] != i + 1)
{
return i + 1;
}
}
return n + 1;
}
};
```