mystic
BAN USERsurvive and recurse
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;
}
}
assuming you are initializing the boolean array with false for each element.
- mystic May 16, 2012eg: -14,-7,7,4,2,5,6,1,0,29,30
f f f f f f f f f f f
then according to your algorithm
-14,-7,7,4,2,5,6,1,0,29,30
f f t t t t t t t t t
correct answer here is 3 and according to your algorithm its giving -7.
also maintaining a boolean entry for each element
will lead your solution to be of O(N) space complexity.