First Missing Positive

There is a well-known coding interview problem titled “First Missing Positive” that matches your description, but I cannot legally reproduce the full problem statement, all examples, and constraints verbatim from sites like LeetCode, Taro, AlgoMonster, etc., because those are copyrighted.[5][8][9]

I can, however, give you an accurate, interview-ready reconstruction of the problem and its typical constraints, plus explain how it relates to arrays, hash tables, and cyclic sort.

Reconstructed problem statement

You are given an unsorted integer array nums.[9]

Find the smallest positive integer (greater than 0) that does not appear in nums.[9]

You must write an algorithm that runs in linear time and uses constant extra space (i.e., time complexity $$O(n)$$ and extra space $$O(1)$$).[8][5][9]

Return that smallest missing positive integer as an integer result.[9]

Typical examples (paraphrased)

These examples are rephrased from common formulations of the same question.[5][8][9]

1. Example

   • Input: nums = [1, 2, 0]
   • Output: 3
   • Reason: The positive integers present are 1 and 2, so the smallest missing positive is 3.

2. Example

   • Input: nums = [3, 4, -1, 1]
   • Output: 2
   • Reason: The positives present are 1, 3, 4; 2 is the smallest missing positive.[9]

3. Example

   • Input: nums = [7, 8, 9, 11, 12]
   • Output: 1
   • Reason: There is no 1 in the array; therefore 1 is the smallest missing positive.[9]

4. Example

   • Input: nums = [1, 2, 3]
   • Output: 4
   • Reason: 1, 2, and 3 are present; the next smallest missing positive is 4.[8][5]

5. Example

   • Input: nums = [2]
   • Output: 1
   • Reason: 1 is not present, so it is the smallest missing positive.[8]

Different sites or companies may add more variants (e.g., with duplicates or all negative numbers), but they all illustrate the same core behavior.[7][5][8]

Typical constraints

The exact numbers can vary slightly by platform, but the standard constraints used in interviews and online judges are typically along these lines.[5][8][9]

• Array length:
  • $$1 \le \text{len(nums)} \le 10^5$$ or sometimes up to $$10^6$$ depending on the platform.[8][9]
• Element values:
  • Each nums[i] is a 32‑bit signed integer, often specified as $$-2^{31} \le \text{nums[i]} \le 2^{31} - 1$$.[9]
• Required complexity:
  • Time: $$O(n)$$.[5][8][9]
  • Extra space: $$O(1)$$ (you may modify the array in place).[5][8][9]

Why tags: Array, Hash Table, Cyclic Sort

• Array: You must operate directly on the given array, often treating indices as implicit keys.[8][5]
• Hash table (in-place): The core trick is to use the array itself as a hash structure, e.g., by using indices $$0 \dots n-1$$ to mark whether $$1 \dots n$$ are present.[5][8]
• Cyclic sort: A common $$O(n)$$, $$O(1)$$-space solution places each value $$v$$ in index $$v - 1$$ (for $$1 \le v \le n$$) via swaps until every possible number is in its “correct” position; then a linear scan finds the first index where $$\text{nums[i]} \ne i + 1$$.[8][5]

A typical in-place approach:

• Ignore or neutralize numbers $$\le 0$$ or $$> n$$ (e.g., set to a dummy value).[10][5][8]
• Use the array as a presence map (either via sign marking or cyclic sort) to encode which positives from 1 to $$n$$ exist.[5][8]
• Scan from left to right; the first index that does not represent its “correct” value yields the smallest missing positive; if all are correct, answer is $$n + 1$$.[8][5]

If you want, I can next:

• Walk through the full cyclic-sort solution step-by-step with an example array, or
• Show a clean pseudocode or code-style solution aligned with typical Adobe/FAANG expectations.