# Getting a Different Number

## - finds the smallest nonnegative integer that is NOT in the array.

Given an array `arr` of unique nonnegative integers, implement a function`getDifferentNumber`that finds the smallest nonnegative integer that is NOT in the array.

Even if your programming language of choice doesn’t have that restriction (like Python), assume that the maximum value an integer can have is`MAX_INT = 2^31-1`. So, for instance, the operation`MAX_INT + 1`would be undefined in our case.

Your algorithm should be efficient, both from a time and a space complexity perspectives.

Solve first for the case when you’re NOT allowed to modify the input`arr`. If successful and still have time, see if you can come up with an algorithm with an improved space complexity when modifying`arr`is allowed. Do so without trading off the time complexity.

Analyze the time and space complexities of your algorithm.

Example:

``````input:  arr = [0, 1, 2, 3]

output: 4
``````

Constraints:

• [time limit] 5000ms

• [input] array.integer`arr`

• 1 ≤ arr.length ≤ MAX_INT
• 0 ≤ arr[i] ≤ MAX_INT for every i, 0 ≤ i < MAX_INT
• [output] integer

## Analysis

#### Using HashSet

``````static int getDifferentNumber(int[] arr) {
int n = arr.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
}

for (int i = 0; i < n; i++) {
if (!set.contains(i)) {
return i;
}
}

return n;
}
``````

#### Using TreeMap/TreeSet

TreeSet/TreeMap is ordered, each add() (or put() for TreeMap) operation takes O(logn) time complexity.

Then iterate over the keys to find not matched integers

``````  public int getDifferentNumber3(int[] arr) {
TreeMap<Integer, Boolean> tmap =
new TreeMap<Integer, Boolean>();
for (int num : arr) {
tmap.put(num, true);
}

int prev = -1;
int candidate = -1;
for (Map.Entry<Integer, Boolean> entry : tmap.entrySet()) {
int curr = entry.getKey();
if (curr - prev > 1 && prev < Integer.MAX_VALUE) {
return prev + 1;
}
prev = curr;
}

if (prev < Integer.MAX_VALUE) {
return prev + 1;
}

return 0;
}
``````

#### Sorting Array

A simple solution would be to create a copy `arr`, sort that copy in an ascending order, iterate over its values, and then return the first index for which the condition `i != arrSorted[i]` is met, where `arrSorted` is the sorted copy of `arr`. This approach works since all the values in `arr` are nonnegative integers.

Time Complexity: duplicating the array is O(N), sorting it is O(N⋅log(N)), and then traversing the array is another O(N). The total time complexity is, therefore, O(N⋅log(N)).

Space Complexity: we used a single auxiliary array, arrSorted, whose size is the same as arr. The space complexity is O(N).

``````  public int getDifferentNumber2(int[] arr) {
int n = arr.length;

int[] arrSorted = Arrays.copyOf(arr, n);

Arrays.sort(arrSorted);

for (int i = 0; i < n; i++) {
if (arrSorted[i] != i) {
return i;
}
}
return n;
}
``````

#### In-place Swaps

the fact that its values are all unique nonnegative integers allows us to use a special kind of sorting algorithm whose time complexity is linear and not the standard `O(N⋅log(N))` we typically associate with efficient sorting.

The high-level idea is to push every number to its corresponding index in the array. The original number in the target index is “kicked out”, so we continue to find its target index using the same approach, until the target index is out of range.

``````public int getDifferentNumber3(int[] arr) {
int n = arr.length;
int temp = 0;

for (int i = 0; i < n; i++) {
temp = arr[i];
while (temp < n && arr[temp] != temp) {
int t = arr[temp];
arr[temp] = temp;
temp = t;
}
}

for (int i = 0; i < n; i++) {
if (arr[i] != i) {
return i;
}
}

return n;
}
``````

Time: Each number is at most moved once, thus the total time complexity is therefore `O(N)`.

Space: O(1) constant space

## Solution

``````import java.io.*;
import java.util.*;

class Solution {

public int getDifferentNumber3(int[] arr) {
TreeMap<Integer, Boolean> tmap =
new TreeMap<Integer, Boolean>();
for (int num : arr) {
tmap.put(num, true);
}

int prev = -1;
int candidate = -1;
for (Map.Entry<Integer, Boolean> entry : tmap.entrySet()) {
int curr = entry.getKey();
if (curr - prev > 1 && prev < Integer.MAX_VALUE) {
return prev + 1;
}
prev = curr;
}

if (prev < Integer.MAX_VALUE) {
return prev + 1;
}

return 0;
}

public int getDifferentNumber2(int[] arr) {
int n = arr.length;

int[] arrSorted = Arrays.copyOf(arr, n);

Arrays.sort(arrSorted);

for (int i = 0; i < n; i++) {
if (arrSorted[i] != i) {
return i;
}
}
return n;
}

public int getDifferentNumber(int[] arr) {
int n = arr.length;
int temp = 0;

for (int i = 0; i < n; i++) {
temp = arr[i];
while (temp < n && arr[temp] != temp) {
int t = arr[temp];
arr[temp] = temp;
temp = t;
}
}

for (int i = 0; i < n; i++) {
if (arr[i] != i) {
return i;
}
}

return n;
}

public static void main(String[] args) {
Solution s = new Solution();
// normal case
int[] arr = new int[] {0, 1, 2, 3};
System.out.println("Expected: 4, Result: " + s.getDifferentNumber3(arr));

// test case
arr = new int[] {3, 0, 2, 4};
System.out.println("Expected: 1, Result: " + s.getDifferentNumber2(arr));

// test case
arr = new int[] { Integer.MAX_VALUE };
System.out.println("Expected: 0, Result: " + s.getDifferentNumber3(arr));

// test case
arr = new int[] { 0, Integer.MAX_VALUE };
System.out.println("Expected: 1, Result: " + s.getDifferentNumber3(arr));

// test case
arr = new int[] { 0 };
System.out.println("Expected: 1, Result: " + s.getDifferentNumber3(arr));
}

}
``````

Related Problems:

https://leetcode.com/problems/missing-number/

https://leetcode.com/problems/first-missing-positive/