4 Different Ways to Solve LeetCode 268 — Missing Numbers

Yan’s Note: This is an example of what an upgraded blogpost may look like if I wrote it. Original found here. Please also note that I have not looked through the code for correctness and I have only included half of the original post as an example.

There are a few small, simple things that you can do to make technical blog posts look a bit more professional and attractive for readers:

🏆 Adding some headers and styling to make it easy to follow
🥰 Emojis and gif to make it fun
📷 A picture/banner that will be included in metatags

I hope this is educational.

I have started doing LeetCode for fun ✨ and thought I would share some of my solutions to help others. 👩🏻‍🏫

This is a question from LeetCode’s missing number coding challenge.

Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

On the surface, this is what I would call an “easy” problem but there are multiple ways to solve it. This is probably good for beginners to understand different algorithmic solutions that can be applied to LeetCode problems. 💁🏻‍♀️

Solution #1: List 📝

Strategy: Sort the list and inspect the elements inside the sorted list. If the value of the next element minus the current element is greater than one, then the missing number will be the value of the current element + 1.

Code (Python):

Summary: This method is quite slow. Why? It takes O(n log n) to sort the list and O(n) to go through it.

The note in problem description requires you to use algorithms with linear complexity, so while this does work and is easy to understand, I suggest you not to use it.

Solution #2: Using a Dictionary 📖

Strategy: Create a set with all elements inside it and remove the elements from that set which could be found in given list.

Code(Python)

Summary:

O(n) to create the new list
O(n) to convert list to set
O(n) to go through the given list
O(n) to remove all elements(except missing number) from the set

Much better than the previous example, but there is a lot of looping happening that could be reduced.