Missing Number
How to Find the Missing Number in an Array
Finding a missing number in an array is a classic coding problem that tests your understanding of mathematical patterns and algorithm optimization. In this article, we’ll explore how to solve this problem efficiently, ensuring we meet the constraints of O(n) runtime and O(1) extra space complexity.
Problem Statement
You are given an array nums containing n integers, where the integers are in the range [0, n] and appear exactly once, except for one missing number. Your task is to identify the missing number.
Constraints
- The length of the array satisfies: 1≤nums.length≤10001 \leq \text{nums.length} \leq 1000
- All numbers in the array are distinct and within the range
[0, n]. - The solution should achieve:
- O(n) runtime.
- O(1) extra space.
Example 1
Input: nums = [0,2]
Output: 1
Explanation:
Explanation:
The range [0, 3] contains the numbers {0, 1, 2, 3}. The number 0 is missing from the array nums.
Example 2
Input: nums = [1,2,3]
Output: 0
Explanation:
The range [0, 2] includes the numbers {0, 1, 2}. The number 1 is missing.
There are mainly 4 approach to solve this problem –
- Sorting
- Hash Set
- Bitwise XOR
- Math
1. Sorting
- Time complexity: O(nlogn)
- Space complexity: O(1) or O(n) depending on the sorting algorithm.
Python
C++
Java
JavaScript
Python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
for i in range(n):
if nums[i] != i:
return i
return n
C++
class Solution {
public:
int missingNumber(vector& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}
return n;
}
};
Java
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}
return n;
}
}
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
missingNumber(nums) {
let n = nums.length;
nums.sort((a, b) => a - b);
for (let i = 0; i < n; i++) {
if (nums[i] !== i) {
return i;
}
}
return n;
}
}
2. Hash Set
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int missingNumber(vector& nums) {
unordered_set num_set(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i <= n; i++) {
if (num_set.find(i) == num_set.end()) {
return i;
}
}
return -1;
}
};
Java
public class Solution {
public int missingNumber(int[] nums) {
Set numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int n = nums.length;
for (int i = 0; i <= n; i++) {
if (!numSet.contains(i)) {
return i;
}
}
return -1;
}
}
Python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
num_set = set(nums)
n = len(nums)
for i in range(n + 1):
if i not in num_set:
return iJavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
missingNumber(nums) {
const numSet = new Set(nums);
const n = nums.length;
for (let i = 0; i <= n; i++) {
if (!numSet.has(i)) {
return i;
}
}
}
}3. Bitwise XOR
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int xorr = n;
for (int i = 0; i < n; i++) {
xorr ^= i ^ nums[i];
}
return xorr;
}
}
Java
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int xorr = n;
for (int i = 0; i < n; i++) {
xorr ^= i ^ nums[i];
}
return xorr;
}
}
Python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
xorr = n
for i in range(n):
xorr ^= i ^ nums[i]
return xorrJavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
missingNumber(nums) {
let n = nums.length;
let xorr = n;
for (let i = 0; i < n; i++) {
xorr ^= i ^ nums[i];
}
return xorr;
}
}
4. Math
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int missingNumber(vector& nums) {
int res = nums.size();
for (int i = 0; i < nums.size(); i++) {
res += i - nums[i];
}
return res;
}
};
Java
public class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0; i < nums.length; i++) {
res += i - nums[i];
}
return res;
}
}
Python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i in range(len(nums)):
res += i - nums[i]
return res
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
missingNumber(nums) {
let res = nums.length;
for (let i = 0; i < nums.length; i++) {
res += i - nums[i];
}
return res;
}
}
