Very detailed explanation with time complexity anlaysis of O(n) time & O(1) space solution


  • 2
    C

    First of all, by observation the maximum missing positive we could get for an array of size N is actually N+1.

    Solution I: O(n) Time, O(n) Space
    Then we could have our initial solution which is using counting sort to place numbers within [1, N] value range to their correct position. Other elements in the array which are not within this value range should be left out. Then we can do a linear scan in the sorted array and find out the first one which is not in-place.

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

    Solution II: O(n) Time and O(1) Space
    To improve the O(n) space, we can actually perform the solution I operations in-place. When we are going over the original array, we can try to swap elements that are not in their final position, meaning nums[i] != i+1, to their position.

    The swapping rule is the following:

    Swap nums[i] if nums[i] != i+1, stop swapping until the nums[i] is not within [1, N] value range or the nums[i] doesn't change (because we can have duplicates)

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

    For this solution here's the time complexity analysis:

    We go over the entire array linearly and for each element we are swapping in a while loop, it seems like to be O(kn) where the k is the average swapping time. But this is wrong, because O(k) is actually O(1) amortized. Here's the explanation:

    Imagine for index [i] , we swapped k times, then the outcome is that at least k elements are in their final correct position.
    Then for index [i+1], the maximum swapping we can have is (n-k), and let's say we ended up swapping (n-k) times for [i+1].
    Then for index [i+2], the maximum swapping we can have is 0.

    So in total we are swapping only n times, thus the amortized swapping time O(k) is actually O(1), thus the overall runtime is O(n).

    Similar idea can be used for (442)Find All Duplicates in an Array and (448)Find All Numbers Disappeared in an Array


Log in to reply
 

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