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.


TA 👨‍🏫