How to Find the Missing Number in an Array (With Solutions in Python & JavaScript)

An Overview of the Find Missing Number in an Array Problem

The Find Missing Number in an Array problem involves identifying the missing number between two almost identical arrays. While the task is straightforward, the challenge in this problem is appropriately communicating the time and space complexity tradeoffs offered by data structures with constant time or linear time lookups.

Examples of the Find Missing Number in an Array Interview Question

Given an unsorted array of unique integers (size n + 1) and a first array identical to the second array, but missing one integer (size n), find and output the missing integer.

Input: list1 = [1, 2, 3, 4] list2 = [1, 2, 3, 4, 5] Output: 5

Input: [1], [] Output: 1

Constraints

• -inf ≤ n ≤ inf
• All entries are unique
• length(list2) - length(list1) == 1

How to Find the Missing Number in an Array: 4 Approaches

Let’s start by reframing this problem as a real world problem. Imagine you're a warehouse supervisor and you have to conduct a roll call every morning.

To keep the problem statement analogous to our real-world example, let’s refer to the longer list as the register, which enumerates all the workers who are supposed to show up to the warehouse on a given day. Let’s refer to the smaller list as the actual attendance, denoting who actually showed up.

Approach 1: Brute Force

In a warehouse, the supervisor typically has a list of all the workers for a given shift. As the workers arrive, they're crossed out on the list, leaving the absentees.

To conduct our roll call, we run through the register (or longer list), verifying that we have the integers in the attendance list (the smaller list). If any of the workers are missing, we would have found our absentee, so we return it, or break out of the loop and return the integer at which we stopped iterating. The code for this in Python would be as follows:

list1 = [1,2,3,4]
list2 = [1,2,3,4,5]

def find_missing_number(list1, list2):
   for integer in list2: # Conduct our roll call against the list2
       if integer not in list1:
           return integer # Break when an absentee is found

find_missing_number(list1, list2) # returns 5

Time/Space Complexity

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

Approach 2: Leveraging O(1) Lookups

The first approach works, but scanning the attendance list every time isn't optimal. Can we leverage any data structures that optimize for lookups? Both hash maps and sets allow for O(1) lookups. We can optimize for time by converting the smaller list into a set, then searching for every item in the longer list within the set. The tradeoff with this approach is increased efficiency from a time-complexity perspective at the expense of additional memory / space complexity, as we need an auxiliary hash table or set to do the O(1) lookups.

def find_missing_number_sets(list1, list2):
   list1 = set(list1) # ’Setify’ the list
   for integer in list2: # Conduct our roll call against the list2
       if integer not in list1:
           return integer # Break when an absentee is found

print(find_missing_number_sets(list1, list2)) # returns 5

Time/Space Complexity

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

Approach 3: Supervisor Keeping Track of Orders Filled

Consider the list [1, 2, 3, 4, 5], which sums to 15. Now consider another list [1, 2, 3, 5], which sums to 11. Notice anything about these two numbers? The difference between 11 and 15 is 4, which is our answer.

def find_missing_number_simple_sum(list1, list2):
   expected_sum = 0

for integer in list2: expected_sum += integer # Calculate expected total
   for integer in list1: expected_sum -= integer # Subtract filled orders

return expected_sum # Return pending orders

print(find_missing_number_simple_sum(list1, list2))

Time/Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) (but technically O(n) if the sum exceeds memory limits)

Approach 4: Bit Manipulation

XOR stands for 'exclusive OR'. With just 2 bits, 0 is equivalent to 00, 1 is equal to 1, and 3 is 11.

def find_missing_number_simple_bitwise(list1, list2):
   slate = 0

for integer in list2: slate ^= integer # XOR integers against slate
   for integer in list1: slate ^= integer

return slate # Whatever we are left with is the missing int

print(find_missing_number_simple_bitwise(list1, list2))

Time/Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1), as we will only ever need 32 bits.