Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

First Missing Positive

Hard
arrayhash-tablecyclic-sort

Given an unsorted integer array, return the smallest positive integer not present. Your algorithm must run in O(n) time and O(1) extra space.

Input: one line of space-separated integers. Output: the smallest missing positive.

Example 1
Input:
1 2 0
Output:
3
Example 2
Input:
3 4 -1 1
Output:
2
Example 3
Input:
7 8 9 11 12
Output:
1

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -2^31 ≤ nums[i] ≤ 2^31 − 1
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.