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 functiongetDifferentNumberthat 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 + 1would 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 modifyingarris 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.integerarr

  • 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 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/