Leetcode 41. First Missing Positive
Problem Explanation
This problem asks to find the smallest missing positive integer from an unsorted integer array. The problem constraints are that the solution should be applied in linear runtime complexity without using extra space.
To illustrate this, let's take an example, the input array is [3,4,-1,1]. Here, we start to traverse the array from left to right and notice the first positive integer missing in the list is '2', so our output will be '2'.
The approach to solve the problem involves using the index of the array to reposition the numbers in the array. For example, if the number is 5, we would place it at index 4 (since index starts from 0). However, we would only do this if the number is positive, within the size of the array (to prevent out-of-bound error), and if the number is not already at the correct position (to prevent infinite loop).
So, if we have the array [3,4,-1,1], we would first place '1' at index 0 using the swap operation and we have [1,4,-1,3]. Then, we can leave '4' as it is (since it's at index 1, which is correct), skip '-1' (since it's not a positive number), and place '3' at index 2 and we have [1,4,3]. After these operations, we notice that there's no '2' at index 1 so the smallest missing positive number is '2'.
Python Solution
1 2python 3class Solution: 4 def firstMissingPositive(self, nums): 5 n = len(nums) 6 for i in range(n): 7 while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: 8 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] 9 10 for i in range(n): 11 if nums[i] != i + 1: 12 return i + 1 13 return n + 1
Java Solution
1 2java 3class Solution { 4 public int firstMissingPositive(int[] nums) { 5 int n = nums.length; 6 7 for (int i = 0; i < n; ++i) 8 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) 9 swap(nums, i, nums[i] - 1); 10 11 for (int i = 0; i < n; ++i) 12 if (nums[i] != i + 1) 13 return i + 1; 14 15 return n + 1; 16 } 17 18 private void swap(int[] nums, int i, int j) { 19 int temp = nums[i]; 20 nums[i] = nums[j]; 21 nums[j] = temp; 22 } 23}
JavaScript Solution
1 2javascript 3var firstMissingPositive = function(nums) { 4 const n = nums.length; 5 6 for(let i=0; i<n; i++) { 7 while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { 8 let temp = nums[i]; 9 nums[i] = nums[nums[i] - 1]; 10 nums[nums[i] - 1] = temp; 11 } 12 } 13 14 for(let i=0; i<n; i++) { 15 if(nums[i] != i+1) { 16 return i + 1; 17 } 18 } 19 20 return n + 1; 21};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int firstMissingPositive(vector<int>& nums) { 6 int n = nums.size(); 7 8 for (int i = 0; i < n; ++i) 9 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) 10 swap(nums[i], nums[nums[i] - 1]); 11 12 for (int i = 0; i < n; ++i) 13 if (nums[i] != i + 1) 14 return i + 1; 15 16 return n + 1; 17 } 18};
C# Solution
1 2csharp 3public class Solution { 4 public int FirstMissingPositive(int[] nums) { 5 int n = nums.Length; 6 7 for (int i = 0; i < n; ++i) 8 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) 9 Swap(nums, i, nums[i] - 1); 10 11 for (int i = 0; i < n; ++i) 12 if (nums[i] != i + 1) 13 return i + 1; 14 15 return n + 1; 16 } 17 18 private void Swap(int[] nums, int i, int j) { 19 int temp = nums[i]; 20 nums[i] = nums[j]; 21 nums[j] = temp; 22 } 23}
The swap method in the C# and Java solutions is just used to swap the elements of the array at indices i and j. This is necessary as the language lacks the multiple assignments syntax found in Python, JavaScript, and C++.# R Solution
While R is not traditionally utilized for this type of problems and it might not have the best performance compared to the previously mentioned languages, it still can be used to solve a wide range of problems. Below is the R implementation of the problem solution:
1 2r 3first_missing_positive <- function(nums) { 4 n <- length(nums) 5 6 for (i in 1:n) { 7 while (nums[i] > 0 && nums[i] <= n && nums[nums[i]] != nums[i]) { 8 temp <- nums[i] 9 nums[i] <- nums[nums[i]] 10 nums[nums[i]] <- temp 11 } 12 } 13 14 for (i in 1:n) { 15 if (nums[i] != i) { 16 return(i) 17 } 18 } 19 20 return(n + 1) 21}
This R function works in a similar way to the previous ones, executing a while loop to move the positive values to their corresponding indices, and then another loop to find the first missing positive integer.
Ruby Solution
Ruby is another versatile language used for a wide range of tasks. Here is how the problem could be solved using Ruby:
1 2ruby 3def first_missing_positive(nums) 4 n = nums.size 5 6 for i in 0...n 7 while nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] 8 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] 9 end 10 end 11 12 for i in 0...n 13 return i + 1 if nums[i] != i + 1 14 end 15 16 return n + 1 17end
Ruby's array indexing is zero-based, similar to other languages. The code uses two for loops: the first one repositions the numbers in the array, and the second one checks for the first missing positive integer.
Remember, however, that each programming language has its strengths and weaknesses. Thus, the right language for a task depends on the specific requirements of the task, including performance requirements and other features needed to solve the task efficiently. In addition, the problem solver's familiarity with the language is an important factor in choosing the right language for a problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.