This is not the most concise solution but it has one trick that may be useful for many beginners that allows to encode two integers into one with possibility to decode it to both integers back. Once you know it you will always use it as it allows to avoid tuples of integers (as java lacks such structure in its libraries) and use just one integer to represent two.

So, if we have two integers `k`

and `m`

and `m`

is always less than some `n`

- we can encode both into one integer using formula:

```
r = k * n + m
(m < n)
```

and now to retrieve them use the following:

```
k = r / n
m = r % n
```

And just to repeat: this trick is possible only if `m`

is strictly less than `n`

Using this trick we can solve many interview tasks that require constant space and have some array which contains integers less than size or array `n`

. If this array requires some extra information for every item, but we cannot loose the initial item value - this can be solved either creating new array (simple) or just encoding initial value and new value directly in the array.

**Turning back to the task:**

We want to "seriallize" all values to their indices. So "1" will come to `nums[0]`

, "2" - `nums[1]`

etc. After this we can easily find the "gap". This is an easy task if we could use extra memory for another array. But we cannot. So we can use the "encoding" scheme offered above:

1.clean every non-relevant item from the array to match the restriction `m < n`

:

```
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) nums[i] = 0;
}
```

2.Encode all items to their matching positions:

```
int m = n + 1;
for (int i = 0; i < n; i++) {
// retrieve the value that initially was at index i (it could be overwritten by encoding)
int prev = nums[i] % m;
if (prev > 0)
// encode it using formula k * n + m, where for 'm' we also use decoding schema
nums[prev - 1] = (prev * m) + nums[prev - 1] % m;
}
```

3.Find the gap:

```
for (int i = 0; i < n; i++) {
if (nums[i] / m != i + 1) return i + 1;
}
```

All in one:

```
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int m = n + 1;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0 || nums[i] > n) nums[i] = 0;
}
for (int i = 0; i < n; i++) {
int prev = nums[i] % m;
if (prev > 0)
nums[prev - 1] = (prev * m) + nums[prev - 1] % m;
}
for (int i = 0; i < n; i++) {
if (nums[i] / m != i + 1) return i + 1;
}
return m;
}
```