Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

22. First Missing Positive

HardDay 6 of 60Arrays & Hashing

Given an unsorted integer array nums, return the smallest positive integer (1, 2, 3, ...) that does not appear in it. Your algorithm must run in O(n) time and use only O(1) extra space.

Example 1
Input: nums = [3,4,-1,1]
Output: 2
1 is present but 2 is not.
Example 2
Input: nums = [7,8,9,11,12]
Output: 1
The smallest positive integer, 1, is missing.
Constraints
  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
Hints
Frequently asked at: Amazon, Microsoft, Google, D. E. Shaw, Adobe
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min