First Missing Positive in NLogN
Leetcode: https://leetcode.com/problems/first-missing-positive/, or copied/pasted here:
But, I did in NLogN which still beats 70% of the C# submissions. The idea is simple:
Given an unsorted integer array, find the first missing positive integer.
For example,
Given
and
Given
[1,2,0] return 3,and
[3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
The problem asks for an O(n)-time solution and O(1)-space. I couldn't do that, I'm sorry.But, I did in NLogN which still beats 70% of the C# submissions. The idea is simple:
- Sort the array (NLogN, use QuickSort)
- Traverse it once (N):
- If non-positive, continue (remember we're looking for the first positive missing number!)
- If equal to the previous, continue
- If not equal to the first positive number (set it to 1), you found the solution!
- Increment the "first" positive number
O(1)-space. Code is below - cheers, Marcelo.
public class Solution
{
public int FirstMissingPositive(int[] nums)
{
if (nums == null || nums.Length == 0) return 1;
Array.Sort(nums);
int solution = 1;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] <= 0 || (i > 0 && nums[i] == nums[i - 1])) continue;
if (nums[i] != solution) break;
solution++;
}
return solution;
}
}
awesome problem, Marcelo! I used a following observation to get an O(N) time complexity - input array either contain all numbers within a 1..n range, in which case the result is n+1 or there there is at least one gap, which gives us an answer. How do we check if en entire range is covered? Well, we can just place all numbers into positions which correspond to their value and use a second pass to get to a point where index does not correspond to its value (gap) or get to the end, in which case the result is the n+1.
ReplyDeleteHere is my 6ms solution:
class Solution {
public:
int firstMissingPositive(vector& nums) {
for (int i = 0; i < nums.size(); ++i) {
int current = nums[i];
if (current == i + 1) continue;
while (current-1 < nums.size() && current != nums[current-1]) {
int next = nums[current-1];
nums[current-1] = current;
current = next;
}
}
int i;
for (i = 0; i < nums.size() && nums[i] == i+1; ++i);
return i + 1;
}
};
Note, that even though there is a nested loop, every element is moved at most one time, so the complexity is definitely linear.
Problem creators should have came up with test cases to fail NlogN solutions :)