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

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 2

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).