First Missing Positive Problem

First Missing Positive Problem — ExecCode Medium DSA Practice

Solve the First Missing Positive problem on ExecCode. Free online medium DSA practice in Hashing. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given an unsorted integer array nums, find the smallest missing positive integer, ignoring zero and negative numbers. Solve it in O(n) time and O(1) extra space by cyclically placing every valid value v at index v-1 and scanning for the first mismatch.

Examples

Input nums = [3, 4, -1, 1]; Output 2. Input nums = [1, 2, 0]; Output 3. Input nums = [7, 8, 9, 11, 12]; Output 1

Constraints

1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1

Practice First Missing Positive free on ExecCode. Browse DSA problems, topic map, and placement guides.