# First Missing Positive

To understand the concept of the "First Missing Positive" problem, let's start with basic principles and then delve into how the problem is approached and solved.

### Basic Principles

1. Numbers and Sequences: In mathematics, numbers are fundamental. A sequence is a list of numbers in a specific order. For instance, the sequence of positive integers starts like this: 1, 2, 3, 4, ...

2. Identifying Missing Elements: If there is a sequence, we can talk about missing elements. For example, in the sequence 1, 2, 4, 5, the number 3 is missing.

3. Positive Integers: These are numbers greater than zero (1, 2, 3, ...). They are used to count or measure things.

### The "First Missing Positive" Problem

The problem statement is typically framed like this: "Given an unsorted integer array, find the smallest missing positive integer."

#### Key Components of the Problem:

• Unsorted Array: The input is a list of integers that are not in any specific order.

• Smallest Missing Positive Integer: This is the smallest number in the sequence of positive integers (1, 2, 3, ...) that does not appear in the array.

### Solving the Problem

#### Approach:

1. Understand the Input: The input is an array of integers. These integers can be positive, negative, or zero.

2. Identify the Target: We need to find the first number in the sequence of positive integers that is not in the array.

3. Constraints: The solution should be efficient in terms of time and space complexity.

#### Example:

Consider the array: [3, 4, -1, 1]

• The positive integers in this array are 3, 4, and 1.
• The sequence of positive integers starts with 1, 2, 3, 4, ...
• The first positive integer not present in the array is 2.

Therefore, for this array, the answer is 2.

#### Algorithm Strategy:

1. Filtering Non-Positive Numbers: Since we are only interested in positive integers, we can ignore negative numbers and zero.

2. In-Place Hashing Technique: This technique is often used to solve this problem efficiently. The idea is to place each number in its 'correct' position in the array. For instance, the number 1 should be in the first position (array index 0), the number 2 in the second position (array index 1), and so on.

3. Checking for the Missing Number: After rearranging the numbers, we traverse the array to find the first place where the number does not match its index + 1. That number is the first missing positive.

### Complexity Analysis

• Time Complexity: The in-place hashing technique typically results in an algorithm with O(N) time complexity, where N is the number of elements in the array.

• Space Complexity: Since the rearrangement is done in place, the space complexity is O(1), as no extra space is used other than the input array.

### Conclusion

The "First Missing Positive" problem is a classic example of applying basic mathematical and algorithmic concepts to efficiently solve a seemingly complex problem. By understanding and applying these first principles, one can design an algorithm that effectively finds the smallest missing positive integer in an unsorted array.