Get Smallest Nonnegative Integer Not In The Array
- finds the smallest nonnegative integer that is NOT in the array.
Given an array arr
of unique nonnegative integers, implement a functiongetDifferentNumber
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 isMAX_INT = 2^31-1
. So, for instance, the operationMAX_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 inputarr
. If successful and still have time, see if you can come up with an algorithm with an improved space complexity when modifyingarr
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++) {
set.add(arr[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 conditioni != arrSorted[i]
is met, wherearrSorted
is the sorted copy ofarr
. This approach works since all the values inarr
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:
Last updated
Was this helpful?