Pramp – Getting a Different Number

Question

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

Solutions

1. Brute Force

Time Complexity: O(n * log(n))
Space Complexity: O(n)

def get_different_number_bruteforce(arr):
  _arr = sorted(arr)
  
  for i in range(len(arr)):
    if arr[i] != i:
      return i
  return len(arr)

2. In-place algorithm

因為解法 1. 的時間複雜度主要來自 Sorting
而因為題目說了 arr 中只有 unique nonnegative integers
所以我們可以不去排序，而是將數字放置至對應的 index （如果其不超過 arr 長度）

Time Complexity: O(n)
Space Complexity: O(1)

def get_different_number_inplace(arr):
  for  i in range(len(arr)):
    # Make positions of all elements in arr which smaller
    # than len(arr) at the index same to their value
    while arr[i] < len(arr) and arr[arr[i]] != arr[i]:
      temp = arr[i]
      arr[i], arr[temp] = arr[temp], arr[i]
  
  for i in range(len(arr)):
    if arr[i] != i:
      return i
  return len(arr)

3. Using Hashmap

Time Complexity: O(n)
Space Complexity: O(n)

def get_different_number_efficient(arr):
  num_in_arr = set()
  for num in arr:
    num_in_arr.add(num)
  for i in range(len(arr) + 1):
    if i not in num_in_arr:
      return i

Last Updated on 2023/08/16 by A1go