Leetcode : First Missing Positive

Question

I was trying out leetcode's first missing positive.
As per the challenge's description:

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

My solution passes all tests, except last five i.e. where the nums array's size is \$10^5\$. When the array is of that size I get "Time Limit Exceeded".

Here is my solution: (PS: class and methods naming are kept as given by leetcode)

class Solution {
  public int firstMissingPositive(int[] nums) {
    int minIndex = 0;
    int integerCounter = 0;

    for (int i = minIndex; i < nums.length; i++) {
        if (i == 0) {
            integerCounter += 1;
        }

        if (nums[i] == integerCounter) {
            // swap
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;

            minIndex += 1;
            i = minIndex - 1;

            integerCounter++;
        }
    }

    return integerCounter > 0 ? integerCounter : -1;
  }
}

My Question
How can I improve this algorithm to tackle super large (e.g. \$10^5\$) nums array without getting the "Time Limit Exceeded" and without having to completely modify the function?

Graphical explanation of my solution using an example

Answer 1

One way to solve this within the given constraints is to use the input array to store which numbers have been seen. Negative numbers will never contribute to the answer, so we can iterate once to replace them with 0 (which will help with the next step).

Let us use nums[i] to mark whether the integer i + 1 appears in nums. To prevent overwriting elements we might need later, if we need to indicate the existence of a value i + 1, we can make the element at index i negative. Then, we can recover the original value of an element by taking the absolute value (with Math.abs). The longest possible consecutive sequence of positive numbers would be the range [1, nums.length] (which can only occur when all elements are distinct), so we can ignore any elements outside that range.

We make another pass over the array to mark the seen elements that could contribute to a consecutive sequence of positive numbers. When marking an element, if the value at the position is positive, we multiply it by -1 to make it negative. If it is 0, we set the value to a negative value such that its absolute value is outside the range of [1, nums.length] to ensure it is not considered part of the answer, e.g. -nums.length - 1. (Alternatively, we can set the value to the value seen on the current iteration multiplied by -1, as having the same number appear multiple times does not affect the answer.)

Finally, we loop over the array once more, finding the longest prefix of negative numbers (which indicates the longest consecutive sequence of positive numbers we can make from numbers in the array starting from 1).

Sample implementation:

public int firstMissingPositive(int[] nums) {
    for (int i = 0; i < nums.length; i++) nums[i] = Math.max(nums[i], 0);
    for (int i = 0; i < nums.length; i++) {
        int actualVal = Math.abs(nums[i]);
        if (actualVal > 0 && actualVal <= nums.length) {
            if (nums[actualVal - 1] == 0) nums[actualVal - 1] = ~nums.length;
            else if (nums[actualVal - 1] > 0) nums[actualVal - 1] *= -1;
        }
    }
    int i = 0;
    while (i < nums.length && nums[i] < 0) ++i;
    return i + 1;
}

Answer 2

The only clue the code presented offers as to what it is all about is the name of the sole public instance method.

Do not follow bad examples, e.g. set by challenge sites. Commendable habits:

• name essential things descriptively
• document everything important, and everything "externally visible"

/** Determine the smallest positive integer not in an array
 *   where the array elements are not necessarily ordered.
 */// https://leetcode.com/problems/first-missing-positive/description/
class SmallestPositiveIntNotInArray {
    /** @return the smallest positive integer not in <code>nums</code>. */
    // required to run in O(nums.length) time and O(1) additional space.
    public int firstMissingPositive(int[] nums) {
        throw new UnsupportedOperationException(
                  "firstMissingPositive() not implemented (yet)");   
    }
}
class Solution extends SmallestPositiveIntNotInArray {}

The for-loop looks an ordinary "counting" loop, but isn't:
give an advance alert!

    // i manipulated non-monotonically in loop body
    for (int i = minIndex; i < nums.length; i++) {
        …
            i = minIndex;
            minIndex += 1;
        …

Answer 3

You search for a "1" first, starting at index 0, exchange it with the element at index 0, if found, and then search for "2", starting at index 1, a.s.o.

That is something similar to Exchange sort, but optimized for the specific needs of the problem, but still has the O(\$n^2\$) worst case run time.

To see this, look what happens when the array has the numbers \$1,2,\ldots,n\$ in reverse order! You take n steps to find the "1", then n-2 steps to find the "2", a.s.o. Once you've found the numbers until \$\frac{n}2\$, the remaining part goes fast as the array is then ordered.

The number of steps through the array is \$n+(n-2)+(n-4)+\ldots+n/2\$, which is roughly \$\frac{3}{16}n^2\$ (CORRECTED, was \$\frac{}8\$ before), which is not what the problem wants.

Considering that general sorting algorithms take O(\$n\log n\$) time, even changing to a better (general) sorting algorithm would not help conceptually (it might help get past the timing tests).

Answer 4

You solve this by using the original array to store whether values are present. There are 3 "paths" for each index.

1. You will leave the item alone at nums[i] then i++and continue
   • This is the case if nums[i] == 0 or nums[i] = i + 1
2. You will set nums[i] = 0 then i++and continue
   • This is the case when, nums[i] is negative, or nums[i] > nums.length
3. You will swap nums[i] and nums[nums[i] - 1] (DO NOT INCREASE INDEX WITH i++)
   • this is the default case

Then, you loop over you array and check if nums[i]==0 return i+1. If you make it through the whole loop return nums.length+ This uses O(1) memory and O(n) runtime.

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        
        for (int i = 0; i < length;) {
            if (nums[i] == 0 || nums[i] == i + 1) {
                i++;
                continue;
            }

            if (nums[i] > length || nums[i] < 0 || nums[nums[i] - 1] == nums[i]) {
                nums[i] = 0;
                i++;
                continue;
            }

            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
        
        for (int i = 0; i < length; i++) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }
        return length + 1;
    }
}