Share my O(n) time, O(1) space solution


  • 101
    Y

    Share my O(n)/O(1) solution


    The basic idea is for any k positive numbers (duplicates allowed), the first missing positive number must be within [1,k+1]. The reason is like you put k balls into k+1 bins, there must be a bin empty, the empty bin can be viewed as the missing number.


    1. Unfortunately, there are 0 and negative numbers in the array, so firstly I think of using partition technique (used in quick sort) to put all positive numbers together in one side. This can be finished in O(n) time, O(1) space.
    2. After partition step, you get all the positive numbers lying within A[0,k-1]. Now, According to the basic idea, I infer the first missing number must be within [1,k+1]. I decide to use A[i] (0<=i<=k-1) to indicate whether the number (i+1) exists. But here I still have to main the original information A[i] holds. Fortunately, A[i] are all positive numbers, so I can set them to negative to indicate the existence of (i+1) and I can still use abs(A[i]) to get the original information A[i] holds.
    3. After step 2, I can again scan all elements between A[0,k-1] to find the first positive element A[i], that means (i+1) doesn't exist, which is what I want.

     public int firstMissingPositive(int[] A) {
        int n=A.length;
        if(n==0)
            return 1;
        int k=partition(A)+1;
        int temp=0;
        int first_missing_Index=k;
        for(int i=0;i<k;i++){
            temp=Math.abs(A[i]);
            if(temp<=k)
                A[temp-1]=(A[temp-1]<0)?A[temp-1]:-A[temp-1];
        }
        for(int i=0;i<k;i++){
            if(A[i]>0){
                first_missing_Index=i;
                break;
            }
        }
        return first_missing_Index+1;
    }
    
    public int partition(int[] A){
        int n=A.length;
        int q=-1;
        for(int i=0;i<n;i++){
            if(A[i]>0){
                q++;
                swap(A,q,i);
            }
        }
        return q;
    }
    
    public void swap(int[] A, int i, int j){
        if(i!=j){
            A[i]^=A[j];
            A[j]^=A[i];
            A[i]^=A[j];
        }
    }

  • 0
    F

    Similar but simpler than my solution, i fill -1 for A[i] in 1..k at your step 3, yours is better.


  • 32
    V

    Another version of O(n) time complexity and constant space complexity

    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
    S

    What's the benefit of your way to do the swap? Is that more efficient?


  • 0
    L
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 1
    L

    I think this is O(n^2) solution, because the while loop is O(n), am I correct?


  • 0
    S

    I'm not sure if this is O(1) space complexity because you are using A[1:k], that is O(n) space. I know that it is input parameter but I'm not sure if you can change it.


  • 1
    D

    No, it is O(n). There is a nested loop there, but think it this way: in the inner loop, we are doing swap for each A[i] ONLY if A[i-1] != i, otherwise the loop breaks. And for outer loop, we are just iterating through the array. Therefore, we will do swap for each A[i] for at most 1 time. :)


  • 1
    C

    Thank you yuyibestman, below is my Java solution with similar idea.

    public class Solution {
        public int firstMissingPositive(int[] A) {
            if (A == null || A.length == 0) {
                return 1;
            }
            int start = 0, end = A.length - 1;
            while (start <= end) {
                while (start < A.length && A[start] > 0) {
                    start++;
                }
                while (end >= 0 && A[end] <= 0) {
                    end--;
                }
                if (start <= end) {
                    int temp = A[start];
                    A[start] = A[end];
                    A[end] = temp;
                }
            }
            for (int i = 0; i < start; i++) {
                if (Math.abs(A[i]) <= A.length && A[Math.abs(A[i]) - 1] > 0) {
                    A[Math.abs(A[i]) - 1] = -A[Math.abs(A[i]) - 1];
                }
            }
            for (int i = 0; i < start; i++) {
                if (A[i] > 0) {
                    return i + 1;
                }
            }
            return start + 1;
        }
    }

  • 0
    T
    This post is deleted!

  • 1
    T

    I think we need not to swap negative numbers,just like this :

        int index = 0;
    	for (int i = 0; i < A.length; i++) {
    		if (A[i] > 0) {
    			A[index++] = A[i];
    		}
    	}
    

    index is the length of positive numbers.

    Anyway, i like your step 3. :)


  • 0
    J

    That's very elegant, thank you for sharing your solution.


  • 0
    Z
    This post is deleted!

  • 0
    A

    It is actually constant space since we modify the original array directly without creating extra space.


  • 0
    P

    I think you can use XOR in step 2. It is simpler.


    sorry, I'm wrong. XOR can not solve the duplicate situation.


  • 0
    C

    Brilliant idea on step 2, much better than swap!


  • 0
    B

    Nice solution, this idea is similar with highest voted solution ( by makuiyu ) ; while the second step, which uses negative number to indicate the existence of a particular number ( really brilliant ! ), and this minor detail is different from that solution.


  • 2
    G

    Inspired by your solution, I came up a solution without partition and swap.

    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0 || nums[i] > nums.length) nums[i] = nums.length + 1;
        }
        for (int i = 0; i < nums.length; i++) {
            int abs = Math.abs(nums[i]);
            if (abs <= nums.length) {
                nums[abs - 1] = -Math.abs(nums[abs - 1]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) return i + 1;
        }
        return nums.length + 1;
    }
    

  • 0
    J

    The "bins" is really a good analogy! But I think there is no need to partition. We can just skip 0 or negative numbers and only assign those positive numbers to the corresponding positions in a new array A (i.e. A[nums[i]-1] = nums[i] if nums[i] is a positive number in [1,N]).
    There is only one special case: when all the N numbers are exactly positive ones from 1 to N, we cannot return in the second for loop. In this case, we should return N+1.

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            int N = nums.length;
            int[] A = new int[N];
            for(int i = 0; i < N; i++)
                if(nums[i]>0 && nums[i]<=N)
                    A[nums[i]-1] = nums[i];
            for(int i = 0; i < N; i++)
                if(A[i] != i+1)
                    return i+1;
            return N+1;
        }
    }

Log in to reply
 

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