CareerCup

Step 1:
Disregard all negatives (put all the positives in the front of the array)

Step 2:
Say the number of positive numbers is: N

we can divide the array into two parts: <=N and >N (the part <=N is first, the >N is second)

Step 3:
For every number x in the array <=N, swap it with the number at index x. Do not swap repeats.

Step 4:
Scan through the numbers and find the first number that does not match its index.

1. Create an array of size N ( indexing 1 to N ) with all entries as zero.
2. Scan the input and ignore the input if it is
a) less than 1
b) greater than N
3. Otherwise, set array[input] = 1
4. In the end, return the first index with a zero value. If all entries are 1, return N+1.

Note: We don't have to find the maximum of elements as some people have suggested. If it is greater than N, it will create a hole in the range 1 to N, which we are trying to find out. The worst case will be the input will be a permutation of elements 1 to N.

public static int lowest (int[] arr){

int vals[] = new int[arr.length];

for( int i = 0; i < arr.length; i++ ) vals[i] = 0;

for( int i = 0; i < arr.length; i++ )
if (arr[i] > 0 && arr[i] < arr.length) vals[arr[i]] = 1;

int len = 0;
for(int i = 1; i < vals.length; i++)
if (vals[i] == 1) len++; else break;

return len+1;
}

the naive solution is

sort the array
scan from the first positive integer, and find any integer is missing.

What is the better solution for this ?

Time: O(N)
Space: O(N) in worst case

public int lowestMissedPositive(int[] arr){
		
	Set<Integer> positiveValues = new HashSet<Integer>();
		
	int min = Integer.MAX_VALUE;
	int max = 0;
			
	for( int i = 0; i < arr.length; i++ ){
		
		if( arr[i] > 0 ){
				
			positiveValues.add( arr[i] );
				
			if( arr[i] < min ){
				min = arr[i];
			}
			else if( arr[i] > max ){
				max = arr[i];
			}
		}
	}
		
	if( min > 1 ){
		return 1;
	}
		
	for( int i = min; i < max+1; i++ ){
		if( ! positiveValues.contains(i) ){
			return i;
		}
	}
	
	return max+1;		
}

There should be more elegant solution in O(N) time and O(1) space.

is this a google question? Which google office this question is asked?

If some one has asked this question he might not have interested in the o(n) solution.

essentially the question translates to whether 1 is present in the array. In an unsorted array, we can check that in o(n).

<pre lang="" line="1" title="CodeMonkey77728" class="run-this"> public int findLowestHM(int[] a){
int lowestNotPresentPos = -1;
int maxPositive = 0;

HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();


for(int i = 0;i < a.length;++i){
if(a[i] > maxPositive){
maxPositive = a[i];
}

if(a[i] > 0){
hashMap.put(i, a[i]);
}
}

for(int i = 1;i < maxPositive;++i){
if(!hashMap.containsValue(i)){
return i;
}
}

return lowestNotPresentPos;
}
</pre>

If we dont have space constraint then we can solve it in O(n) time complexity:

1) find MIN and MAX positive integer.
2) create one array with size MAX. Suppose A[MAX] and initialize it with 0.
3) Traverse the original array and put all positive integer in A in following way:

if number is x then A[x-1]=x .
4) Now traverse A and the first encountered zero value of array will the result.

Suppose A[6] is zero then result will be 7.

5) If A does not have any zero value then result will be MAX +1 .

Note: It will take more space but time complexity will O(n).

If any mistake is there please let me know.

<pre lang="" line="1" title="CodeMonkey10943" class="run-this">// Here is an O(N) time, O(N) space solution that does not depend on the value range of integers in the array
class MissingPositive {

private int[] a;
private Island lowest;
private Map<Integer, Island> map;
private Island inland = new Island(0, 0);

public static void main(String[] args) {
System.out.println(new MissingPositive(new int[]{}).find());
System.out.println(new MissingPositive(new int[]{4,2,3}).find());
System.out.println(new MissingPositive(new int[]{6,7,10,1,3,2,5,4}).find());
}

public MissingPositive(int[] a) {
this.a = a;
}

public int find() {
lowest = null;
map = new HashMap<Integer, Island>();

for (int i = 0; i < a.length; i++) {
int n = a[i];

if (n > 0 && map.get(n) == null) {
// No island containing this number exists

// Check if an island exists immediately on the left
Island left = null;
if (n > 1) {
left = map.get(n - 1);
if (left != null) {
if (left.min != left.max) {
// Mark the previous boundary number as inland
map.put(left.max, inland);
}

// Expand island to the right
left.max = n;
map.put(n, left);
}
}

// Check if an island exists immediately on the right
Island right = map.get(n + 1);
if (right != null) {
if (right.min != right.max) {
// Mark the previous boundary number as inland
map.put(right.min, inland);
}

// Expand the island to the left
right.min = n;
map.put(n, right);

storeIfLowest(right);
}

if (left != null && right != null) {
// Join the islands: the left one will be the main now.
left.max = right.max;
right.min = left.min;

// Mark the common boundary number as inland
map.put(n, inland);

map.put(left.min, left);
map.put(left.max, left);

} else if (left == null && right == null) {
// Create a new island
Island isle = new Island(n, n);
map.put(n, isle);

storeIfLowest(isle);
}

}

}

if (lowest == null) {
// No islands
return 1;
}

// The non-existing number is either before the lowest island or immediately after
return lowest.min > 1 ? lowest.min - 1 : lowest.max + 1;
}

private void storeIfLowest(Island isle) {
if (lowest == null) {
lowest = isle;

} else if (isle.min < lowest.min) {
lowest = isle;
}
}

private static class Island {
public int min;
public int max;

public Island(int min, int max) {
this.min = min;
this.max = max;
}
}

}

</pre><pre title="CodeMonkey10943" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey66871" class="run-this"># In python:
class Island:
def __init__(self, minv, maxv):
self._min = minv
self._max = maxv


def find_missing_positive(array):
islandmap = {}
min_island = Island(0, 0)

for n in array:
if islandmap.has_key(n):
continue
left = None
island = Island(n, n)
if n > 1:
left = islandmap.get(n-1)
if left is not None:
island._min = left._min
right = islandmap.get(n+1)
if right is not None:
right._min = island._min
island._max = right._max
if left is not None:
left._max = island._max

if min_island._max == 0 or min_island._min >= island._min:
min_island._max = island._max
min_island._min = island._min
islandmap[n] = island

if min_island._min > 1:
return 1
return min_island._max + 1

</pre>

public int lowestPositive(int []Arr){
for(int i=0; i< Arr.length;i++){
if(Arr[i] >0){
Arr[Arr[i]-1]= (Arr[Arr[i]-1]==0)?-1:0;
}
}

for(int i=0; i< Arr.length ; i++)
{
if(Arr[i]==0)
return i++;

}
return i++;
}

@Xiaoyu

There is another problem with your solution.(Apart from space limitations)
while you check whether a no is positive or negative before inserting it into the hash map
however you enter the elements in the hash map using index i, and for a missing index i, you return i.
thus if you have a negative no in your array it wont be inserted into the hashmap and hence that index will be returned while checking for the missing smallest positive integer.

private static int findLowestPostiveValue(int[] a) {

int min= a[0];
for(int i=1;i<a.length;i++)
{
if((a[i]<min)&&(a[i]>=0))
{
min=a[i];
}
}
return min;

}

Sorry I misread the question:
This solution would work, the complexity is o(n)
private static int findLowestPostiveValue(int[] a) {

int min= a[0];
for(int i=1;i<a.length;i++)
{
if((a[i]<min)&&(a[i]>=0))
{
min=a[i];
}
}
int resultmin=min-1;
if(resultmin>=0)
return resultmin;
else
return min;


}

Maintain an n-bit vector(initialized to 0). Scan through the array, whenever you find a positive element(a[i]) and a[i] <= n, set the a[i]'th bit of bit vector to 1. After complete scan on array, let's say that bit vector contains 1st zero at xth position, then x is your answer!!

sort the array e.g (quick sort) -- O(log n)
Binary search the array for where +ive #s start. -- O(log n)
if(1st +ive # is not 1) return 1;
else scan till missing +ive # -- worst case O(n)

If space is no constraint then the solution suggested by some of us here, that to create a new array with size equal to max integer in the list is good.
If space is constraint then here is another method that can be used:
1) sort the array, TC O(nlgn)
2) traverse the array from start till first positive number is encountered, take care of if 0 is also an element of array.
3) lets assume the index of first positive number is i and length of array is n
use another variable, j and initialize it to 1.
the code will now look like
for(j=1;i<n;++j,++i) //traverse loop till we reach end of array, increment i & j at each step.
{
if(arr[i]/j != 1 && arr[i]%j != 0)
first_missing_positive_num = j;
}
We can also use if condition like (this strike me a moment later :) )
if(a[i] != j)
first_missing_positive_num = j;

Pls check my solution here : ideone.com/Dhi7n

It takes O(n) time and O(1) space. Only input constraint is that there should no duplicate in the array.

O(n), constant storage.

void foo(int[] ai) {
   int missing_min = 1;
   for(int i = 0; i < ai.length; i++) {
      if(ai[i] == missing_min) {
         missing_min++;
   }
}

If this problem has only one number missing and there is no repetition of numbers. Then XOR all the positive number is one iteration and store the max number too. Then Again XOR the resultant from 1^2^3^...^max
ans = resultant^1^2^3^...^max.

Use a min-heap. Go through array (ignoring negative integers) and add positive numbers to heap. If you find integers 1&2 then remove 1 from heap. If heap has already 3, remove 2 and so on. We would need custom heap which would return min() and secondMin(). After starting removing minimal numbers from heap we could also ignore such numbers during going through array.

At the end start removing min numbers from heap, is next number is greater than current more than 1 you found the solution.

Worst case performance will be O=(n*log(n)), but the average case will be much faster than sorting.

1. Remove all negatives. Let nPos be no of +ves.
2. For 0 to Npos-1
a) if array element is greater than nPos-1--> set it to -1.
b) if Array element is not equal to its index and index of array element is also not equal to its value -->swap them
c) if Array element is not equal to its index but index of array elem is equal to its value --> Set elem -1
3. Find the first elem that is not equal to index and return it as minimum missing.

Complexity n+n+n= O(n)

Code:
int find_first_missing(int arr[],int len)
{
int i=0;
int j=0;

/** Remove all negatives STEP 1 **/
for(j=0;j<len;j++)
{
if(arr[j] >= 0)
{
arr[i++]=arr[j];
}

}
arr[i]='\0';

/*****STEP 2 ******/
for(j=0;j<i;j++)
{
if(arr[j]>i)
{
arr[j]=-1;
}
else if(j != arr[j])
{
if(arr[arr[j]]!=arr[j])
{
int temp=arr[arr[j]];
arr[arr[j]]=arr[j];
if(temp<i)
{
arr[j]=temp;
}
else
{
arr[j]=-1;
}
}
else
{
arr[j]=-1;
}

}
}


/******* STEP 3 ***/
for(j=0;j<i;j++)
{
if(arr[j] !=j)
return j;
}

}

1. Remove all negatives. Let nPos be no of +ves.
2. For 0 to Npos-1
a) if array element is greater than nPos-1--> set it to -1.
b) if Array element is not equal to its index and index of array element is also not equal to its value -->swap them
c) if Array element is not equal to its index but index of array elem is equal to its value --> Set elem -1
3. Find the first elem that is not equal to index and return it as minimum missing.

Complexity n+n+n= O(n)

Code:
int find_first_missing(int arr[],int len)
{
int i=0;
int j=0;

/** Remove all negatives STEP 1 **/
for(j=0;j<len;j++)
{
if(arr[j] >= 0)
{
arr[i++]=arr[j];
}

}
arr[i]='\0';

/*****STEP 2 ******/
for(j=0;j<i;j++)
{
if(arr[j]>i)
{
arr[j]=-1;
}
else if(j != arr[j])
{
if(arr[arr[j]]!=arr[j])
{
int temp=arr[arr[j]];
arr[arr[j]]=arr[j];
if(temp<i)
{
arr[j]=temp;
}
else
{
arr[j]=-1;
}
}
else
{
arr[j]=-1;
}

}
}


/******* STEP 3 ***/
for(j=0;j<i;j++)
{
if(arr[j] !=j)
return j;
}

}

An O(n) solution with maximum 3 run:
1st run: find minimum number a[k]>0
if a[k]>1 return return

2nd run: set bool b[a[i]]=true if a[i]>0 and a[i]<a.Length
3nd run: return first i that b[i]==false
if every b[i] is false, return a.length

The logic is that in the 1st run, if we can find the min number in array more than 1 , that means 1 is not in the array.
Otherwise, the array must has a subset(no need to be a sub-sequence) containing consecutive number staring from 1. so the length of that subset can not be more than the length of original array. So we just need to use a bit array b[] to record the consecutive numbers starting from 1 in original array.
The left thing is easy though......

1. remove all negative numbers and zeros
2. suppose the number of remaining positive numbers is N
3. remove all numbers greater than N
4. loop through all remaining numbers K, and place K at index K, drop duplicates.
O(n)

# ruby : find lowest positive number not in array (or nil)
p nums = [13, 12, 9, 3, 9, 4, 3]
min = nums.min
p min <= 1 ? (min_pos = nil) : (min_pos = min - 1)

int findLowestPositiveInt(int* A, int n)
	{
		for(int i=0; i<n; i++)
		{
			int j = A[i];
			if (j>=1 && j<= n)
			{
				int tmp = A[j-1];
				A[j-1] = A[i];
				A[i] = tmp;
			}
		}
		for(int i=0; i<n; i++)
		{
			if (A[i] != (i+1))
			{
				return i+1;
			}
		}
		return n+1;
	}

public class MinPositiveNotInArray {

	static int minPositiveNotInArray(int a[]){
		int n = a.length;
		
		// need to keep track of the end points of ranges for the endpoints only
		Map<Integer,Integer> rangeMinWithElement = new HashMap<Integer,Integer>();
		Map<Integer,Integer> rangeMaxWithElement = new HashMap<Integer,Integer>();
		
		for(int i = 0; i < n; i++){
			if(a[i] > 0){
				int min = a[i], max = a[i];
				if(!rangeMinWithElement.containsKey(a[i])){
					rangeMinWithElement.put(a[i], a[i]);
				}
				if(!rangeMaxWithElement.containsKey(a[i])){
					rangeMaxWithElement.put(a[i], a[i]);
				}
				
				if(rangeMinWithElement.containsKey(a[i]-1)){
					min = rangeMinWithElement.get(a[i]-1);
				}
				
				if(rangeMaxWithElement.containsKey(a[i]+1)){
					max = rangeMaxWithElement.get(a[i]+1);
				}
				
				//System.out.println(a[i] + "\t" + min + "\t" + max);
				rangeMaxWithElement.put(min, max);
				rangeMinWithElement.put(max, min);
			}
		}
		
		if(!rangeMinWithElement.containsKey(1)){
			return 1;
		} else {
			int max = rangeMaxWithElement.get(1);
			return max+1;
		}
	}
	
	public static void main(String[] args){
		   int[] testcase1 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2};
		   int res1 = 3;
		   int[] testcase2 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2 , 3 , 4};
		   int res2 = 6;

		   System.out.println(Arrays.toString(testcase1));
		   System.out.println(minPositiveNotInArray(testcase1)+ "\t" + res1);

		   System.out.println(Arrays.toString(testcase2));
		   System.out.println(minPositiveNotInArray(testcase2)+ "\t" + res2);
	   }
	
}

an O(n) C++ code with O(1) space

void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
}

int lowest_pos(int a[], int n)
{
	int i = 0;
	while(true){
		if(a[i] == i+1)
			i++;
		else if(a[i] <= n && a[i] > 0)
			swap(a[i],a[a[i]-1]);
		else i++;
		if(i==n)
			break;
	}
	for(int i = 0; i < n ; i++)
		if(a[i] != i+1)
			return i+1;
	return n+1;
}