## Task Description:

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

### **Complexity Conditions:**


1. Time complexity: `O(n)`
2. Space complexity:  `O(1)`

### Example 1:

```
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
```

### Example 2:

```
Input: nums = [-1,7,8,9,11,12,-10]
Output: 1
Explanation: The smallest positive integer 1 is missing.
```

## Solution:

### Brute force approach

The first thing that comes to mind is to do brute force. The idea is simple; sort through all positive numbers from 1 until we find the first missing one.

\
**Complexity:**


1. Time complexity: `O(n*n)`
2. Space complexity:  `O(1)`

\
```java
public int firstMissingPositive(int[] nums) {
    int positiveNumber = 1;
    while (true) {
        boolean exists = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == positiveNumber) {
                exists = true;
                break;
            }
        }
        if (!exists) return positiveNumber;
        positiveNumber++;
    }
}
```

\
The problem is that for each number, we re-pass through the entire array. Let's try to reduce the number of iterations by allocating extra memory.

### Approach 2: With Extra Space

We can use a `HashMap` or a `boolean array` of size N to remember which elements are in the array. And then, by simple enumeration, find the minimum positive element.

\
**Complexity:**


1. Time complexity: `O(n)`
2. Space complexity:  `O(n)`

\
```java
public int firstMissingPositive(int[] nums) {
    Map<Integer, Boolean> map = new HashMap<>();
    for (int n: nums) {
        if (n > 0) {
            map.put(n, true);
        }
    }
    int number = 1;
    while(true) {
        if (map.get(number) == null) {
            return number;
        }
        number++;
    }
}
```

\
In the first loop on lines 3-7, we remember only positive numbers, since we will need to work with them further.

\
In the second loop on lines 9-13, we sequentially check the numbers starting from 1. If the number is on the map, then we move on, otherwise, return it.


:::tip
Whenever we know how to solve an array problem using a HashMap but extra space is not allowed, try using the array itself as a HashMap.

:::

### Approach 3

To use the original array as a HashMap, we need to take a closer look at the problem statement. In the worst case, the array will contain all positive numbers from 1 to N (the length of the array), and then the answer will be N+1.

\
* Step 1. This means that all numbers less than 1 and greater than N are useless, and we can replace them with N+1. All numbers in the array are now positive, and in the range \[1..N+1\].

\
* Step 2.  We can mark each cell that appears in the array by converting the index for that number to negative

\
* Step 3. Find the first index which is positive that is our answer.

\
**Complexity:**


1. Time complexity: `O(n)`
2. Space complexity:  `O(1)`

\
```java
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int fakeNumber = n + 1;
    
    // Step 1.
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = fakeNumber;
        }
    }
    
    // Step 2.
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]); // point 1
        if (num == fakeNumber) { // point 2
            continue;
        }
        num--; // point 3
        if (nums[num] > 0) {
            nums[num] *= -1;
        }
    }
    
    // Step 3.
    for (int i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            return i + 1;
        }
    }
    
    // otherwise return n+1
    return n + 1;
}
```

\
I would like to draw your attention to a few major points:

\

1. Since we mark cells with negation, we must ignore the sign when extracting.

   \
2. In step 1, we changed all the numbers to ignore **fakeNumber,** so don't forget to ignore them.

   \
3. Do not forget to decrease the value by 1; since, in java, indexing starts from zero (so the number 1 will be at pos 0).

\
The algorithm listed above gives us the following result.

 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-j0a3of6.png)

\
I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.

\
See you soon! ✌

Read My Stories

Too Long; Didn't Read

Build an AI-based text classifier with Tensorflow & NoSQL

Java Algorithms: First Missing Positive (LeetCode)

Too Long; Didn't Read

@top4ikru

RELATED STORIES