Problem statement
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Example 1
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2
Input: nums = [1,1]
Output: [2]
Constraints
n == nums.length.
1 <= n <= 10^5.
1 <= nums[i] <= n.
Follow up
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Solution 1: Marking the appearances
You can use a vector of bool to mark which value appeared in the array.
Code
#include <vector>
#include <iostream>
using namespace std;
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<bool> exist(nums.size() + 1, false);
for (auto& i : nums) {
exist[i] = true;
}
vector<int> result;
for (int i = 1; i <= nums.size(); i++) {
if (!exist[i]) {
result.push_back(i);
}
}
return result;
}
void print(vector<int>& nums) {
cout << "[";
for (auto& n : nums) {
cout << n << ",";
}
cout << "]\n";
}
int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
auto result = findDisappearedNumbers(nums);
print(result);
nums = {1,1};
result = findDisappearedNumbers(nums);
print(result);
}
Output:
[5,6,]
[2,]
Complexity
Runtime: O(n), where n = nums.length.
Extra space: much less than O(n). vector<bool> is optimized for space efficiency; it stores single bits.
Solution 2: Follow up
You could use the indices of the array nums to mark the appearances of its elements because they are identical ([1, n] vs. [0, n-1]).
One way of marking the appearance of an index j is making the element nums[j] to be negative. Then the indices j's whose nums[j] are unchanged (still positive) are the ones that do not appear in nums.
Code
#include <vector>
#include <iostream>
using namespace std;
vector<int> findDisappearedNumbers(vector<int>& nums) {
int j;
for (int i{0}; i < nums.size(); i++) {
j = abs(nums[i]);
nums[j - 1] = -abs(nums[j - 1]);
}
vector<int> result;
for (int i{1}; i <= nums.size(); i++) {
if (nums[i - 1] > 0) {
result.push_back(i);
}
}
return result;
}
void print(vector<int>& nums) {
cout << "[";
for (auto& n : nums) {
cout << n << ",";
}
cout << "]\n";
}
int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
auto result = findDisappearedNumbers(nums);
print(result);
nums = {1,1};
result = findDisappearedNumbers(nums);
print(result);
}
Output:
[5,6,]
[2,]
Complexity
Runtime: O(N), where N = nums.length.
Extra space: O(1) (the returned list does not count as extra space).
Conclusion
Solution 2 helps to avoid allocating extra memory but it is not straightforward to understand.
Though Solution 1 requires some extra space, that memory is not much since vector<bool> is optimized for space efficiency. Moreover, it is easier to understand than Solution 2.
What is your approach? The problem was picked from leetcode.com, where you can submit your solution in any programming language and check the performance.
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.
