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


  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.


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.


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.