DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
Back to Arena
hard
Array

First Missing Positive

**Problem Statement:** Given an unsorted integer array `nums`. Return the smallest positive integer that is not present in `nums`. You must implement an algorithm that runs in `O(n)` time and uses `O(1)` auxiliary space. **Hint / Expected Approach:** Cyclic sort / index-as-hash trick **Edge Cases to Consider:** - (1) Array of all negatives - (2) Consecutive 1–n (answer is n+1) - (3) Duplicates present

Examples

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^4
  • ▪-10^9 <= nums[i] <= 10^9
  • ▪Time complexity should be O(n) or O(n log n)

Watch Out For Edge Cases

  • ▪Array of all negatives
  • ▪Consecutive 1–n (answer is n+1)
  • ▪Duplicates present
Frequently Asked At
AmazonGoogleMicrosoftMetaFlipkart