Solution in java

  • 0

    O(n) space solution -
    If we were to use O(n) extra space, we could have easily solved it by following the steps given below:

    1. Create another array of size n.
    2. Traverse the given array and mark the index corresponding to the traversed value in new array (if possible).
    3. In the end, traverse the new array and first unmarked index, that should be the answer.
    4. If every index in new array is marked then (length_of_array + 1) is the answer.

    O(1) space solution with in-place array modification -
    But, now that we can not use extra space, we are left with no choice but to alter the array in place (If you think not, please suggest the alternative).
    Idea is very simple here too. Basically we will move every element in given array to its designated location. Once this movement is done, we can traverse the array again and find the first index where the designated value is not present and that will be the answer. Code snippet below -

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

Log in to reply

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