## InMobi Interview Question

- 0of 0 votes
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.

Eg:

Input = {2, 3, 7, 6, 8, -1, -10, 15}

Output = 1

Input = { 2, 3, -7, 6, 8, 1, -10, 15 }

Output = 4

**Country:**India

**Interview Type:**In-Person

Isn't 1 the answer above?

I think the question asks for smallest positive number missing from the array, not the smallest positive number.

Hm, I think I finally got the question :)

Your solution makes total sense now unless there are no negatives there and we have {1,2,3,4}

It works for array with negatives as well, the example that I used has negative value, and gives correct answer.

what if you sort the numbers then traverse till all -ve numbers end. then check for 1 if available or not. if yes then check diff with next element and move ahead until u a[n+1] - a[n] >1 . ur answer is a[n] +1 . if 1 not found then answer is 1

gimli, I didnt look at the code in detail, but your solution seems to be correct.

Nicely done in the same array... discarding the elements that are not needed.

not workng..logic fails because the swapped value is lost

@gimli : have you checked it with both the above given example ?

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.

Instead of using the hash table, you can shift the wrong values towards the end of the array and decrease end.

eg: int[] a = {12, 2, 1, -5, 6, 18}

Keep a pointer at the start and another at the end of the array.

a[0] = 12 and 12 > a.length() so swap 12 with a[end] and do end--

so my a[] becomes {18, 2, 1, -5, 6}

similarly, 18 is also out of bounds so I repeat and a[] = {6, 2, 1, -5} and then {-5, 2, 1} and then {2, 1}

Now, in this step we see a[start] <= end so what I do is swap a[start] with a[a[start]]

Thus, a[] = {1, 2}

lastly, I have to loop only till whenever a[start] = a[a[start]], in this case till 3 (which is our answer).

1. scan the array for the largest element .

2. Now take the hash table of size = largest element.

3. map the array elements into hash table.

4. Scan the hash table for smallest positive number missing.

....I think this way space complexity is not o(n)....please comment..

The largest number can be Integer.MAX so if we have an array of say only 6-7 values, thats an overkill

Yea....but it dsnt depend on size of the array....My point is that v talk about complexity for the input of millions. In that context m talking abt...

Consider a language which can represent arbitrary large integers, in that case Integer.Max doesn't make sense and you cannot have such hash table.

`In my view ashu soln is best because it is using constant space O(1) complexity and time complexity is O(n).`

Hi ashu, I think your solution works when there is no dup positive interger in the array. I can have a long array that every element in there is smaller than array.length. Finding and swapping those dups out can be time consuming.

Hey Ric I didn't take into notice for the duplicate elements, but the algorithm can be extended for duplicate elements easily.

We are interested in smallest positive number not in array so all duplicate elements can be swapped out of the boundaries similar to a number greater than length of array (i.e. doing a start++ will do the trick)

@Ashu, pretty neat solution, though I do not clearly understand what you in case value < end.

Can you show, how would your algorithm work on following array

[6,5,4,3,2,1]

I believe we have to do a Radix Sort O(n) after the elements are deleted,and also compare the absolute values instead of comparing them directly that way we delete large negative numbers also.

I tired this and it worked. But did not use the Radix Sort in my code, went with a more easy O(n log n) sorting algorithm and here is the code, if anyone is interested

```
public int findSmallestPositiveMissing(int[] array)
{
int left = 0;
int right = array.length - 1;
while(left < right)
{
if(Math.abs(array[left]) > array.length)
{
int temp = array[left];
array[left] = array[right];
array[right] = temp;
right--;
}
left++;
}
Arrays.sort(array);
for(int i = 1; i < array[right]; i++)
{
if(Arrays.binarySearch(array, i) < 0)
{
return i;
}
}
return array[right] + 1;
}
```

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());
}
}
```

Good job! I think this works and is linear time: n + n/2 + n/4 + ... = O(n).

btw, I suggest you read Jon Bentley's Programming Pearls (and do the exercises). I believe this appears as one of the exercises in the first (or maybe second) chapter.

```
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.

assuming you are initializing the boolean array with false for each element.

eg: -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.

```
#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;
}
```

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:

The solution above is obviously O(1) in space complexity.

- gimli on February 20, 2012 Edit | Flag ReplyTo 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)