O(1) space Java Solution


  • 56
    S

    The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.

    public class Solution {
        public int firstMissingPositive(int[] A) {
            int i = 0;
            while(i < A.length){
                if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
                else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
                else i++;
            }
            i = 0;
            while(i < A.length && A[i] == i+1) i++;
            return i+1;
        }
        
        private void swap(int[] A, int i, int j){
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }

  • -5
    B

    what if all numbers are larger than the array length?


  • 0
    S

    Then the answer will be 1.


  • 0
    M

    This is clever and elegant! Thanks!


  • 5
    L

    good idea, but what if there are some duplicate in the array.


  • 0
    N

    I dont understand how is this working for negative numbers?


  • 0
    H

    if A[i] is negative, i++, but in the next positive number round it goes to swap negative with positive.


  • 0
    S

    @lihe I think it doesn't matter. Just keep one of the duplicates and the code will still work~


  • 0
    S

    @lihe I understand what you said now.. I add few lines and it works~

    Spoiler while(i < nums.length){
    //如果超过范围或者已经就满足的
    if(nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1){
    i++;
    }else{
    //新换来的 要再比较
    int pre = nums[i];
    swap(nums, i, nums[i] - 1);
    if(nums[i] == pre){
    //换回来还是原来的那个 会死循环
    i++;
    }
    }
    }


  • 0
    S

    Thanks, although I code the same way, your solution is more elegant than mine.


  • 1

    I thought this line was redundant at first, so I remove since you have A[i] != i + 1. Then I stuck at [1, 1] , and I know it's about checking duplicate!

    if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
                else i++;
    

  • 0

    @baifriend
    Yeah I had the same concern at first, but then I just realized that in this if condition if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length), he put A[i] > A.length to make sure that we ignore numbers that are larger than the length


  • 0
    M

    Damn, it's a awesome solution! OTZ


  • 0
    D

    Oh great siyang3! I plead you to bless me with your wisdom!


  • 0
    This post is deleted!

  • 0
    J

    @baifriend please read the instructions carefully


  • 0
    A

    nicely done..


  • 4

    same idea

        public int firstMissingPositive(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]) {
                    swap(nums, i, nums[i]-1);
                }
            }
            
            for(int i = 0; i < nums.length; i++) {
                if (nums[i] != i+1)    return i+1;
            }
            return nums.length+1;
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

  • 0
    B

    Can someone explain why in the first if clause, it is:
    if (A[i] == i + 1 ...) instead of if(A[i] == i) ?


  • 0
    A

    Question? Does the instructions means first missing positive integer ever or the first missing positive integer in the given sample set. What I meant is for the array [5000, 4999, 4998, 4996], if applied the second meaning then the answer is 4997 but if applied the first meaning then the answer is 1. This code is not able to be handle the second meaning. Am I missing something here?


Log in to reply
 

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