## Amazon Interview Question

Interns**Country:**India

**Interview Type:**In-Person

How about maintaining a HashSet that covers the values that have already been encountered along with the minimal value found so far? O(n) memory and O(n) runtime:

```
public static int getSmallestUnfoundInInterval(int[] arr){
if(arr == null){
throw new NullPointerException();
}
if(arr.length == 0){
throw new IllegalArgumentException();
}
//build the HashSet and get the min
HashSet<Integer> set = new HashSet<Integer>();
int minVal = Integer.MAX_VALUE;
for(int i : arr){
if(i < minVal){
minVal = i;
}
set.add(i);
}
//search the HashSet for the first value counting up from the min that is NOT in the set
while(set.contains(minVal)){
minVal++;
}
return minVal;
```

Your idea of maintaining a min value makes sense, but I wonder if you actually need the set.

Simply keep track of a min value, but with the special property that this min value must be at least 2 less than the next min value.

Pseudocode:

```
int min = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
if (a[i] < (min-1)) {
min = a[i];
}
}
return min;
```

O(n) time, O(1) space

```
def getMissingMin(a = []):
if a:
min = a[0]
for i in a:
if i < min:
min = i
return min+1
else:
return 0
```

Fails because min+1 could be within the array. IE: [-5, 1, -4, 2] would return -4 but -4 is in the array.

It means the minimum value in range of min and max of elements.

Here is my solution.it works.

```
public static void main(String[] args) {
int[] arr = {-1,4,5,-23,24};
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
HashSet<Integer> set = new HashSet<Integer>();
for (int i =0;i<arr.length;i++){
if(arr[i]<min)
min = arr[i];
if(arr[i]>max)
max = arr[i];
set.add(arr[i]);
}
for(int i = min; i<=max; i++){
if(!set.contains(i)){
System.out.println(i);
break;
}
}
}
```

Here was a good idea to use HashSet, however the time complexity is presented for that solution not sharp, actually it should be O(N + M) where N is number of elements in array and M is offset which we have to go from min value in the array to the next omitted value if we sorted it. In some cases M could be significant bigger than N.

The following solution works guaranteed O(N). We just use one more HashSet to store potential answer to our question:

```
import java.util.HashSet;
/**
* Created by sis on 5/27/15.
*/
public class CareerCup_5758677862580224 {
public static void main(String[] args) {
int[] a = {-1, 4, 5, -23, 24};
int m = getNotPresentedMin(a);
System.out.println(m);
}
private static int getNotPresentedMin(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException();
}
HashSet<Integer> real = new HashSet<>();
HashSet<Integer> potential = new HashSet<>();
for (int i = 0; i < a.length; i++) {
real.add(a[i]);
potential.add(a[i] + 1);
}
int min = Integer.MAX_VALUE;
for (int i: potential) {
if (!real.contains(i)) {
min = Math.min(min, i);
}
}
return min;
}
}
```

```
public class CareerCup5758677862580224 {
public static void main(String[] args) {
int[] sampleArray = {-1,4,5,-23,24};
int minimum = 0;
System.out.println(minValue(sampleArray,minimum));
}
public static int minValue(int[] sampleArray, int min){
for(int x = 0; x < sampleArray.length; x++){
if(sampleArray[x] < min)
min=sampleArray[x];
}
return min+=1;
}
}
```

import java.util.ArrayList;

import java.util.List;

public class MinmumNotPresentInArray {

public static void main(String[] args) {

Integer[] input = { -1, 4, 5, -23, 24 };

System.out.println("Min 1= " + getMinimumMissingNumber(input));

input = new Integer[]{ -1, 4, 5, -23, 24 };

System.out.println("Min 2= " + getMinimumMissingNumber(input));

input =new Integer[] { 1,5,3,4,6};

System.out.println("Min 3= " + getMinimumMissingNumber(input));

input = new Integer[]{5,4,3,2};

System.out.println("Min 4= " + getMinimumMissingNumber(input));

input =new Integer[] {1,2,4,3};

System.out.println("Min 5= " + getMinimumMissingNumber(input));

input =new Integer[] {1,2,5,3};

System.out.println("Min 6= " + getMinimumMissingNumber(input));

input =new Integer[] {1,2,3,4};

System.out.println("Min 7= " + getMinimumMissingNumber(input));

input =new Integer[] {5,1,3,4};

System.out.println("Min 8= " + getMinimumMissingNumber(input));

}

private static long getMinimumMissingNumber(Integer[] input) {

List<Integer> array=new ArrayList<Integer>();

List<Integer> array1=new ArrayList<Integer>();

long min=Long.MAX_VALUE;

for (int i = 0; i < input.length; i++) {

array.add(input[i]);

array1.add(input[i]+1);

}

for (Integer iy:array1) {

if(!array.remove(iy) && min>iy.intValue()){

min=iy.intValue();

}

}

System.out.println();

if(array.size()==1){

return Long.MIN_VALUE;

}

return min;

}

}

Take a boolean array of size n say bool[]

Iterate over the number array once and find the minimum say it is k

Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.

Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.

Check index of first false index in bool array. Say the index is j.

The number is j+k

```
public int minNonArrayNum(num[]){
int size = num.length;
boolean bool[] = new boolean[size];
bool[0] = true;
int minimum = num[0];
for (int i = 0 ; i < size ; i++) {
if (num[i] < minimum) {
minimum = num[i];
}
}
for (int i = 0 ; i < size ; i++) {
if (num[i]-minimum < size) {
bool[num[i]-minimum] = true;
}
}
for (int i = 1 ; i < size ; i++) {
if (!bool[i]) {
return i+minimum;
}
}
}
```

Take a boolean array of size n say bool[]

Iterate over the number array once and find the minimum say it is k

Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.

Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.

Check index of first false index in bool array. Say the index is j.

The number is j+k

```
public int minNonArrayNum(num[]){
int size = num.length;
boolean bool[] = new boolean[size];
bool[0] = true;
int minimum = num[0];
for (int i = 0 ; i < size ; i++) {
if (num[i] < minimum) {
minimum = num[i];
}
}
for (int i = 0 ; i < size ; i++) {
if (num[i]-minimum < size) {
bool[num[i]-minimum] = true;
}
}
for (int i = 1 ; i < size ; i++) {
if (!bool[i]) {
return i+minimum;
}
}
}
```

Why you need a HashSet if it can be done using a boolean array of size n say bool[]

Iterate over the number array once and find the minimum say it is k

Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.

Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.

Check index of first false index in bool array. Say the index is j.

The number is j+k

```
public int minNonArrayNum(num[]){
int size = num.length;
boolean bool[] = new boolean[size];
bool[0] = true;
int minimum = num[0];
for (int i = 0 ; i < size ; i++) {
if (num[i] < minimum) {
minimum = num[i];
}
}
for (int i = 0 ; i < size ; i++) {
if (num[i]-minimum < size) {
bool[num[i]-minimum] = true;
}
}
for (int i = 1 ; i < size ; i++) {
if (!bool[i]) {
return i+minimum;
}
}
}
```

private static int getmin(int[] a) {

int result= Integer.MAX_VALUE;

Set<Integer>num= new HashSet<Integer>();

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

if(!num.contains(a[i])){

num.add(a[i]);

}

}

for(int l: num){

if(l<result){

result=l;

}

}

if(result<0){

result= result+1;

}

else{

result= result-1;

}

return result;

}

//This can be done in O(n) time with O(1) space complexity.

public class Solution {

public static void main(String[] args){

int[] a = {-23,1,8,-22,-47,-46,-45,-44,100,200};

int answer = findMinimumNotPresentInArray(a);

System.out.println(answer);

}

private static int findMinimumNotPresentInArray(int[] a){

int answer = a[0];

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

if(a[i] < answer - 1 ){

answer = a[i];

}

if(a[i] == answer +1 ){

answer = a[i];

}

}

return answer + 1;

}

}

I suppose the answer should be -24 which is smaller than -23.

- sv May 26, 2015where as -22 is greater than -23.