Leetcode Problem 41. First Missing Positive

41. First Missing Positive

Leetcode Solutions

Index as a Hash Key

  1. Check if 1 is present in the array. If not, return 1 as the answer.
  2. Replace negative numbers, zeros, and numbers larger than n by 1s.
  3. For each number a in the array, negate the value at index abs(a) - 1 if it is positive, to mark a as present. Use index 0 to record the presence of n.
  4. Iterate over the array starting from index 1. The first index with a positive value indicates the smallest missing positive integer.
  5. If all values from indices 1 to n - 1 are negative, check the value at index 0. If it's positive, return n, otherwise return n + 1.
UML Thumbnail

Sorting and Linear Scan

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...