Skip to main content

Leetcode 41: First Missing Positive


1. Problem Statement (Simple Explanation):


You’re given an unsorted integer array nums.

You must return the smallest positive integer (i.e., >= 1) that is not present in nums.

Constraints:

  • Must run in O(n) time.

  • Must use O(1) auxiliary space (i.e., in-place; ignoring input array itself).


2. Examples:


Example 1:

Input: nums = [1,2,0]

Present positives: 1, 2.
Missing smallest positive: 3.

Output: 3


Example 2:

Input: nums = [3,4,-1,1]

Present positives: 1, 3, 4.
Smallest missing positive is 2.

Output: 2


Example 3:

Input: nums = [7,8,9,11,12]

No 1 in the array, so the smallest missing positive is 1.

Output: 1


3. Key Insight:


For an array of length n:

  • The smallest missing positive integer is always in the range: [1, n+1]

  • Because:

    • In the best case, the array contains all 1..n, so the answer is n+1.

    • Otherwise, some number in 1..n is missing.

We can use the array itself as a hash map to record which numbers in [1..n] are present, in O(1) extra space.


4. Approach – In-place Index Mapping (Cyclic Placement):


We will rearrange numbers so that:

  • If possible, nums[i] == i + 1 for 0 <= i < n.

Meaning:

  • Place value 1 at index 0

  • value 2 at index 1

  • ...

  • value k at index k-1

After this arrangement, we can scan once:

  • The first index i where nums[i] != i + 1 means i + 1 is missing.

  • If all positions match, then the missing value is n + 1.


Step-by-Step:


Let n = nums.length.

  1. Rearrange in place:

For each index i from 0 to n - 1:

  • While nums[i] is in the range [1..n] and nums[nums[i] - 1] != nums[i]:

    • Swap nums[i] and nums[nums[i] - 1].

    • We do not increment i here; we re-check the new nums[i].

This loop will:

  • Move each number x into its correct position x-1 if possible.

  • Skip:

    • Negative numbers

    • Zero

    • Numbers > n

    • Duplicates (since we check nums[nums[i]-1] != nums[i]).

  1. Scan to find missing positive:

    • For i from 0 to n - 1:

      • If nums[i] != i + 1, then return i + 1.

    • If no such i is found, return n + 1.


Example Walkthrough – [3,4,-1,1]:


n = 4

Initial: [3,4,-1,1]

  • i = 0:

    • nums[0] = 3 ∈ [1..4], target index = 3-1=2

    • nums[2] = -1 != 3 → swap nums[0] and nums[2]

    • Array → [-1,4,3,1]

    • Now nums[0] = -1 (out of range) → move to i = 1.

  • i = 1:

    • nums[1] = 4, target index = 4-1=3

    • nums[3] = 1 != 4 → swap

    • Array → [-1,1,3,4]

    • Now nums[1] = 1, target index = 0

    • nums[0] = -1 != 1 → swap nums[1] and nums[0]

    • Array → [1,-1,3,4]

    • Now nums[1] = -1 → out of range → i = 2.

  • i = 2: nums[2] = 3 at index 2 → correct (3-1=2).

  • i = 3: nums[3] = 4 at index 3 → correct (4-1=3).

Now array: [1,-1,3,4]

Scan:

  • i=0: nums[0]=1 -> ok

  • i=1: nums[1]=-1 != 2 → return 2.


Pseudo-code:



Complexity:


  • Time: We might swap each element a few times, but each element can be moved at most once to its correct position. Overall: O(n)

  • Space: We only use a few variables, no extra arrays: O(1)


5. Java code:



6. C code:



7. C++ code:


8. Python code:



9. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more