CareerCup

I am assuming that we need to find smallest non-negative integer in the array, it can easily be extended to smallest positive integer as well.

I am basically use the array itself as the hash-table. Since, solution would be in the range [0,sizeOfArray-1], the array itself would suffice to find the solution.

Basically, while going through the array, I am moving the element to its correct location in array based on the value as the hash-key itself. So, 2 -> index 2, 5 -> index 5, and so on. For elements, which are not in range [0,sizeOfArray-1], I do not care, as they cannot be the answer.

Here is my sample code for doing this:

#include <stdio.h>

int main()
{
	int A[] = {2, 3, 7, -6, 0, 1, 4, 5};
	int size = 8;
	int previousValue = -1;
	int currentIndex = 0;
	int currentValue = A[currentIndex];
	int nextIndex = currentIndex + 1;
	bool isChaining = false;
	
	while (nextIndex <= size)
	{
		if (currentValue != currentIndex &&
			currentValue > -1 &&
			currentValue < size)
		{
			isChaining = true;
			A[currentIndex] = previousValue;
			previousValue = currentValue;
			currentIndex = currentValue;
			currentValue = A[currentIndex];
		}
		else
		{
			if (isChaining)
			{
				A[currentIndex] = previousValue;
				isChaining = false;
			}
			
			currentIndex = nextIndex++;
			previousValue = -1;
			currentValue = A[currentIndex];
		}
	}
	
	int x;
	for (x = 0 ; x < size; x++)
	{
		if (A[x] != x)
		{
			printf ("%d\n", x);
			break;
		}
	}
	if (x == size)
	{
		printf ("%d\n", x);
	}
	
	return 0;

}

The solution above is obviously O(1) in space complexity.
To prove that it is O(n) in time complexity, it can be seen easily that I never visit an element more than twice, so it would traverse the array twice before all required elements are at their required location. Then, one more traverse is required to find the answer. Hence, O(n)

Hmm.. this is a very interesting question, so I am going to take a stab at this.

1. Go through the array once and map everything to a hash table. Also keep track of the largest positive vale you find - O(n)
2. Start a second loop from 0 or 1 (depending on your definition of smallest positive integer). - O(n)
3. In every iteration, check if value exists in hash table. If it does not, that is your value

Total time: O(n) runtime, O(n) space.

I will be very interested in a solution that can pull this off in less than O(n) space.

Finally, a flawless algorithm based on Quicksort's partition subroutine.

1. Using modified partition routine, move all the -ve elements to the right side of the array and all +ve numbers to the left side of the array
2. Let the size of all the positive numbers be N.
3. Use Quicksort's modified partition subroutine to recursively check for the missing number either in the left half or the right half of the array. This results in an O(n) time complexity algorithm.
4. At each recursive step, for a subarray starting at index S, and ending at index E, the subarray is partitioned around the pivot (S + E)/2. We check if the pivot is correctly positioned at its location. Depending on the existence of the pivot at its correct location, we recurse either in the left half or the right half of the sub array to report the missing element.
5. If no element is missing, return 0.

Java code is below: Tested on the inputs in the following format.
2 3 -7 6 8 1 -10 15
2 3 7 6 8 -1 -10 15
-1 -2 -3 -4 4 3 2 5 7 6
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11 10 12 6 9 11 13 15

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MissingPositiveNumber {

	ArrayList<Integer> numbers = new ArrayList<Integer>();

	public void readInput() {
		Scanner scanner = new Scanner(System.in);
		scanner.useDelimiter(System.getProperty("line.separator"));
		Pattern delimiters = Pattern.compile(System
				.getProperty("line.separator") + "|\\s");
		scanner.useDelimiter(delimiters);
		int i;
		while (scanner.hasNextInt()) {
			i = scanner.nextInt();
			numbers.add(i);
		}
	}

	public int findMinMissing(int[] a, int start, int end, int missingMin) {

		if (end - start <= 0) {
			if (a[start] != start)
				return start;
			else
				return missingMin;
		}

		int mid = (start + end) / 2;
		int j = start, k = end;

		while (true) {

			while (j <= end && a[j] < mid)
				j++;
			while (k > start && a[k] > mid)
				k--;
			if (j >= k)
				break;
			else {
				int temp = a[j];
				a[j] = a[k];
				a[k] = temp;
			}
		}

		if (mid < a[mid])
			return findMinMissing(a, start, mid - 1, mid);
		else if (mid > a[mid])
			return findMinMissing(a, mid, end, missingMin);
		else
			return findMinMissing(a, mid + 1, end, missingMin);
	}

	public int findMissingSmallestPosNumber() {
		int[] vals = new int[numbers.size() + 1];
		for (int i = 1; i <= numbers.size(); i++) {
			vals[i] = numbers.get(i - 1);
		}

		int j = 1, k = numbers.size();

		while (true) {

			while (j <= numbers.size() && vals[j] > 0)
				j++;
			while (k >= 1 && vals[k] < 0)
				k--;
			if (j > k)
				break;
			else {
				int temp = vals[j];
				vals[j] = vals[k];
				vals[k] = temp;
			}
		}
		return findMinMissing(vals, 1, k, 0);
	}

	public static void main(String[] args) {
		MissingPositiveNumber mpn = new MissingPositiveNumber();
		mpn.readInput();
		System.out.println("The least positive missing number ="
				+ mpn.findMissingSmallestPosNumber());
	}
}

public static int findTheMissingPositiveNumber(int[] arr) {
        int missingInt = 1;
        int curValue = arr[0];
        int lastIndex = arr.length - 1;

        while (missingInt < lastIndex) {
            if (curValue <= 0 || curValue >= lastIndex + 1) {
                curValue = arr[lastIndex];
                lastIndex--;
            } else if (curValue != missingInt) {
                int tmp = arr[curValue - 1];
                arr[curValue - 1] = curValue;
                curValue = tmp;
            } else {
                while (curValue == missingInt) {
                    arr[missingInt - 1] = curValue;
                    curValue = arr[missingInt];

                    missingInt++;
                }
            }
        }

        return missingInt;
    }

Do a radix sort O(n)

Then { 2, 3, -7, 6, 8, 1, -10, 15 } becomes {-10, -7, 1,2,3,6,8,15}

Now, iterate from left to right and check if a[i] + 1 == a[i+1]

if not then assign a min variable that number .. now go forward and keep checking till u find a minimum int

int[]  arr =  {-10, -7, 1,2,3,6,8,15};
int min = -1;
for(int i =0 i < arr.length - 1; i++){
     if( a[i] < 0 ) continue;

     if( a[i] - 1 != 0 ){
           min = a[i] - 1; break;
     }
     if ( a[i] + 1 != a[i+1] ) {
         min = a[i] + 1; break;
     }
}

sysout(min);

same as code above by gimli here is Pseudocode
Solution --> O(n) worst case + O(1) space

1. iterate array set elements > array.size to -1
2.bring respective elements to index corressponding to their value
for e.g if element=3 then set a[3]=3 and so on;
3. iterate array again and return the index corressponding to first negative value

here is the full code in java
// didn't check special case neither duplicates

package arraysnstrings;

import java.util.Arrays;

public class MinMissingPositiveInteger {

public static void main(String[] args) {

int a[]={-14,-7,7,4,2,5,6,1,0,29,30};

System.out.println(findMin(a,a.length));

}

private static int findMin(int[] a, int length) {
// TODO Auto-generated method stub


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

System.out.println("before : = " + Arrays.toString(a));
//special case if all integers are -ve return 0
int tempElement = -1;
for(int i=0;i<length;i++){
if(a[i]>=0&&a[i]!=i){

tempElement = a[i];
a[i]=-1;

while(tempElement>=0){
int temp2=a[tempElement];
a[tempElement]=tempElement;
tempElement=temp2;
}

}


}
System.out.println("after="+Arrays.toString(a));

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

return -1;
}

}

Maintain a separate array of type boolean having same size. Iterate through array of given elements and if a +ve element is found mark the corresponding element in boolean array as true. If -ve element, ignore the element.

The start iterating boolean array. The smallest positive integer will be corresponding element, having value as false in boolean array.

geeksforgeeks.org/forum/topic/to-find-the-smalest-positive-no-missing-from-an-unsorted-array

#include<stdio.h>
#include<conio.h>

int minValue(int *p);
sort(int *p)
int main()
{
	int array[] = {-2,-3,1,2,3,5,6,7};
	int min = minValue(array);
	if(min)
	printf("min value->%d",min);
	else
	printf("No missing value");
}

//First sort the array
int minValue(int *p)
{
	int flag=0;
	int min=0;
	for(int i=0;i<7;i++)
	{
		if(p[i]<0)
		;
		else if(p[i]-min==1)
		{
			min = p[i];
		}
		else
		{
			flag=1;
			break;
			return min + 1;
		}
	}
	if(flag)
	return min + 1;
	else
	return 0;
}

int missing(int *a,int n)
{
	int i,pos;
	for(i=0;i<n;i++)
	{
		if(a[i]>0 && a[i] <= n)
		{
			pos = a[i] -1;
			if(a[pos] != a[i])
			{
				swap(a[pos],a[i]);
				i--;
			}
		}
	}
	
	for(i=0;i<n;i++)
	{
		if(a[i] != i+1)
			return i+1;
	}
	return n+1;
}

int n = array.length;
		int low = -1;
		for(int i=0;i<n;i++) {
			if (array[i] >= 0) {
				if(low == -1) {
					low = array[i];
				} else if(array[i]<low){
					low = array[i];
				}
			}
		}
		
		System.out.println("-> "+low);