As O(n) solution and O(1) space is must only way is to "sort array in O(n) time with optimal space and time overheads"


  • 6
    V

    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;
            }
        };

  • 0
    N

    perhaps the best answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.