Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Given an array of integers, find the first missing positive integer in linear time and constant space

Tags:

In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same as below:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[]={1,-1,-5,-3,3,4,2,8};
    int size= sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+size);
    int min=1;

    for(int i=0; i<size; i++){
        if(arr[i]>min) break;
        if(arr[i]==min) min=min+1;
    }
    cout<<min;
    return 0;
}

Here, I am first sorting the array, and then traversing the array once. Before traversing the array, I have initialized a variable named "min" as 1. Now, while traversing the array, when we get an integer that is equal to min, we simply increment the value of min. This ensures that the min variable hold the latest least positive integer that has not occurred yet. Can you think of any better approach? Thanks in advance.

like image 853
Jhanak Didwania Avatar asked Jul 15 '18 07:07

Jhanak Didwania


People also ask

What is the smallest positive integer with 6 8 and 10 factors?

Answer: LCM of 6, 8, and 10 is 120. Explanation: The LCM of three non-zero integers, a(6), b(8), and c(10), is the smallest positive integer m(120) that is divisible by a(6), b(8), and c(10) without any remainder.

How do you find the first missing positive integer in an array?

Solution steps We create a hash table H of size n. Now we run a loop from i = 0 to n - 1 and insert all elements in the hash table H. Now we another loop from i = 1 to n + 1 to search all the possible positive numbers from 1 to n + 1 in the hash table H. If any positive integer i is not present in H, we return i.


2 Answers

Assuming the array can be modified,

  1. We divide the array into 2 parts such that the first part consists of only positive numbers. Say we have the starting index as 0 and the ending index as end(exclusive).

  2. We traverse the array from index 0 to end. We take the absolute value of the element at that index - say the value is x.

    1. If x > end we do nothing.
    2. If not, we make the sign of the element at index x-1 negative. (Clarification: We do not toggle the sign. If the value is positive, it becomes negative. If it is negative, it remains negative. In pseudo code, this would be something like if (arr[x-1] > 0) arr[x-1] = -arr[x-1] and not arr[x-1] = -arr[x-1].)
  3. Finally, we traverse the array once more from index 0 to end. In case we encounter a positive element at some index, we output index + 1. This is the answer. However, if we do not encounter any positive element, it means that integers 1 to end occur in the array. We output end + 1.

It can also be the case that all the numbers are non-positive making end = 0. The output end + 1 = 1 remains correct.

All the steps can be done in O(n) time and using O(1) space.

Example:

Initial Array:            1 -1 -5 -3 3 4 2 8
Step 1 partition:         1 8 2 4 3 | -3 -5 -1, end = 5

In step 2 we change the signs of the positive numbers to keep track of which integers have already occurred. For example, here array[2] = -2 < 0, it suggests that 2 + 1 = 3 has already occurred in the array. Basically, we change the value of the element having index i to negative if i+1 is in the array.

Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1

In step 3, if some value array[index] is positive, it means that we did not find any integer of value index + 1 in step 2.

Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
        The answer is 4 + 1 = 5
like image 163
pmcarpan Avatar answered Sep 19 '22 00:09

pmcarpan


This is actually a LeetCode problem that asks for O(n) time and O(1) space, so sorting the input or converting it to a set won't work. Here's a Python 3 implementation of pmcarpan's answer that runs in O(n) time and uses O(1) space.

def missing_int(nums: MutableSequence[int]) -> int:
    # If empty array or doesn't have 1, return 1
    if not next((x for x in nums if x == 1), 0):
        return 1

    lo: int = 0
    hi: int = len(nums) - 1
    i: int = 0
    pivot: int = 1

    while i <= hi:
        if nums[i] < pivot:
            swap(nums, i, hi)
            hi -= 1
        elif nums[i] > pivot:
            swap(nums, i, lo)
            i += 1
            lo += 1
        else:
            i += 1

    x = 0
    while x <= hi:  # hi is the index of the last positive number
        y: int = abs(nums[x])
        if 0 < y <= hi + 1 and nums[y - 1] > 0:  # Don't flip sign if already negative
            nums[y - 1] *= -1
        x += 1

    return next((i for i, v in enumerate(nums[:hi + 1]) if v >= 0), x) + 1

Tests:

def test_missing_int(self):
    assert func.missing_int([1, 2, 1, 0]) == 3
    assert func.missing_int([3, 4, -1, 1]) == 2
    assert func.missing_int([7, 8, 9, 11, 12]) == 1
    assert func.missing_int([1]) == 2
    assert func.missing_int([]) == 1
    assert func.missing_int([0]) == 1
    assert func.missing_int([2, 1]) == 3
    assert func.missing_int([-1, -2, -3]) == 1
    assert func.missing_int([1, 1]) == 2
    assert func.missing_int([1000, -1]) == 1
    assert func.missing_int([-10, -3, -100, -1000, -239, 1]) == 2
    assert func.missing_int([1, 1]) == 2
like image 31
Abhijit Sarkar Avatar answered Sep 21 '22 00:09

Abhijit Sarkar