First Missing Positive
This problem is about finding the smallest missing positive integer in an unsorted array with the constraint that the algorithm should run in O(n) time and use O(1) auxiliary space.
Approach
The idea is to use the given array itself to arrange the elements in such a way that if an element nums[i]
is positive and less than the length of the array, then it should be put at its correct position (i.e., nums[nums[i]  1]
).
Here’s a stepbystep approach:
 Iterate through the array: For each element, if it is positive and less than or equal to the length of the array, and it’s not already at its correct position, swap it with the element at its target position.
 Find the first mismatch: Iterate through the modified array, and find the first element that doesn’t match its index. The missing positive integer is
index + 1
.  Return the result: If no mismatch is found, return the length of the array + 1 as the missing integer.
Implementation


Insights and Key Takeaways
 The solution cleverly uses the array itself as a storage to keep track of the presence of integers.
 By putting the numbers in their correct positions (if they fall within the range [1, n]), we can quickly find the missing integer without extra space.
 The while loop ensures that the swapping continues until an element is placed in its correct position or an outofrange element is encountered.
 The time complexity is O(n) since each element is swapped at most once.
 The space complexity is O(1), as required, since we only use a constant amount of extra space.
 This problem is a great example of an inplace algorithm that leverages the structure of the input to achieve space efficiency.
10 Prerequisite LeetCode Problems
“First Missing Positive” requires an understanding of array manipulation and hashing. Here are 10 simpler problems to build the necessary skills:
“Two Sum” (LeetCode Problem #1): This problem helps to understand the usage of hash maps, which can be useful for the “First Missing Positive” problem.
“Remove Duplicates from Sorted Array” (LeetCode Problem #26): This problem introduces basic array manipulation techniques.
“Find All Numbers Disappeared in an Array” (LeetCode Problem #448): This problem introduces the concept of using array indices as a form of inplace hashing.
“Contains Duplicate” (LeetCode Problem #217): This problem provides further practice with using array elements for inplace hashing.
“Missing Number” (LeetCode Problem #268): This problem is directly related to finding missing elements in an array.
“Single Number” (LeetCode Problem #136): This problem helps to understand XOR operations which can be beneficial in many array problems.
“Find the Duplicate Number” (LeetCode Problem #287): It introduces the concept of detecting duplications in an array which is important for “First Missing Positive”.
“Rotate Array” (LeetCode Problem #189): This problem provides good practice for array manipulation, especially for understanding how to rearrange elements within an array.
“Move Zeroes” (LeetCode Problem #283): This problem also helps to understand inplace modifications in arrays.
“Find All Duplicates in an Array” (LeetCode Problem #442): This problem provides further practice with using array indices as a form of inplace hashing, similar to what’s required in “First Missing Positive”.


Problem Classification
This problem deals with finding the first missing positive integer in an unsorted integer array. Since we are examining the properties of numbers and identifying missing elements, it’s categorized as Number Properties Analysis.
The problem is about finding the first missing positive number in a list of numbers that are not in order. Since we’re looking at the properties of numbers and finding what’s missing, this is Number Analysis.
Language Agnostic Coding Drills
Working with Lists/Arrays: Understanding the basic operations with lists/arrays: accessing elements, iterating over the list, updating elements based on conditions.
Understanding Conditional Statements: The code uses simple conditional statements to check for certain conditions and perform operations based on those.
Basic Arithmetic Operations: The code uses arithmetic operations to manipulate indices and array elements.
Understanding the concept of inplace operations: The problem is solved in constant space complexity. Understanding how inplace operations work, where the input array is updated during each operation rather than creating new data structures.
Understanding absolute value function: The code uses the absolute value function to maintain the numbers in positive format for the comparison and then making them negative for marking as visited.
Understanding the concept of Marking elements in the array: The problem is solved using the logic where the existence of a number in the array is marked by making the number at its index negative. This is a common technique in solving such problems.
Identifying the first missing positive integer: The final step involves iterating over the array to identify the first index which is positive indicating the missing smallest positive integer.
The problem solving approach:
Step 1  Understanding the problem statement: We need to find the first missing positive integer from the list of integers.
Step 2  Preprocessing the array: Go through the array, and all the nonpositive numbers and numbers greater than the length of the array are replaced with a constant number which is greater than the length of the array.
Step 3  Marking numbers in the array: Go through the array again, for every number encountered check if the absolute value is greater than the length of the array. If not, make the number at its index position negative.
Step 4  Finding the first missing positive integer: Finally, go through the array and find the first index which has a positive number. The first missing positive number will be index+1. If no such index is found, return length+1.
This algorithm works in O(N) time and uses O(1) space, by using the indices of the array itself to keep track of the numbers that are present.
Targeted Drills in Python
Working with Lists/Arrays: Understand how to access, iterate, and modify elements in a list.
1 2 3 4 5
arr = [1, 2, 3, 4, 5] for i in range(len(arr)): print(arr[i]) arr[i] = arr[i]*2 print(arr)
Understanding Conditional Statements: Write a function that takes an array and a number as inputs, and returns a new array with all elements greater than the number doubled.
1 2 3 4 5
def double_greater(arr, num): for i in range(len(arr)): if arr[i] > num: arr[i] = arr[i]*2 return arr
Basic Arithmetic Operations: Practice simple arithmetic operations by writing a function that calculates the mean of a list.
1 2
def mean(arr): return sum(arr)/len(arr)
Understanding the concept of inplace operations: Write a function that reverses a list inplace.
1 2 3 4 5
def reverse_list(nums): left, right = 0, len(nums)  1 while left < right: nums[left], nums[right] = nums[right], nums[left] left, right = left + 1, right  1
Understanding absolute value function: Write a function that replaces all elements in a list with their absolute value.
1 2 3 4
def absolute_list(nums): for i in range(len(nums)): nums[i] = abs(nums[i]) return nums
Understanding the concept of Marking elements in the array: Write a function to mark an element in an array as visited by negating it.
1 2 3
def mark_visited(arr, i): arr[i] = arr[i] return arr
Identifying the first missing positive integer: Write a function that finds the first positive integer missing from the list. (This is a simplified version of the final problem where the list only contains positive integers)
1 2 3 4 5 6 7 8 9
def first_missing_positive(nums): if not nums: return 1 nums.sort() smallest_int = 1 for num in nums: if num == smallest_int: smallest_int += 1 return smallest_int
These drills will help you understand the basics required to solve the final problem. You can start by solving these simple problems and then gradually move to solve the final problem. It is suggested to understand each of these drills as they form the building blocks for solving complex problems.