Skip to main content

98. First Missing Positive

hardAsked at Ola

Find the smallest missing positive integer in an unsorted array in O(n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an unsorted integer array nums, return the smallest missing positive integer. Algorithm must run in O(n) time and use O(1) auxiliary space.

Constraints

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

Examples

Example 1

Input
nums = [1,2,0]
Output
3

Example 2

Input
nums = [3,4,-1,1]
Output
2

Approaches

1. Hash set scan

Put values into a set; scan upward for the smallest missing positive.

Time
O(n)
Space
O(n)
const set = new Set(nums);
for (let i = 1; i <= nums.length + 1; i++) if (!set.has(i)) return i;

Tradeoff:

2. Cyclic placement

Place each value v in slot v-1 by swapping; missing position is the answer.

Time
O(n)
Space
O(1)
function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

Tradeoff:

Ola-specific tips

Ola interviewers like the cyclic-swap trick because it shows you'll grind a O(1)-space constraint instead of giving up; tie it to finding a gap in driver-ID slots.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill First Missing Positive and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →