Clean and systematic O(n) and constant time C++ solution, beat 94%


  • 1
    C

    We know that the elements in the array has a value range of [0, N], so the first natural solution is to use counting sort and try to place elements to their correct position by using nums[i]-1 as its index. Then finally do a O(n) scan to see which one is the first one that is not in correct position, that position's index+1 is our answer.

    This would take O(n) time and O(n) space.

    However, we can further improve this solution by doing this counting sort in place. We still go over the entire array from left to right, if the current element is not in its correct position, meaning nums[i] != i+1, we do a swap with the following rules:

    Repeatedly swap nums[i] and nums[nums[i]-1] until nums[i] == i+1 or we can not further swap.

    Then finally do a linear scan to discover the first one that is not in correct position.

        int missingNumber(vector<int>& nums) {
            for (int i=0; i<nums.size(); i++) {
                while (nums[i] != i+1 && nums[i] != 0) {
                    swap(nums[i], nums[nums[i]-1]);
                }
            }
            for (int i=0, expected=1; i<nums.size(); i++, expected++) {
                if (nums[i] != expected) return expected;
            }
            return 0;
        }
    

    The time complexity is O(n), for analysis of why time complexity is O(n), see my original post here:
    https://discuss.leetcode.com/topic/75753/very-detailed-explanation-with-time-complexity-anlaysis-of-o-n-time-o-1-space-solution


Log in to reply
 

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