448. Find All Numbers Disappeared in an Array

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

1
2
3
4
5
6
7
Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

java

https://discuss.leetcode.com/topic/65738/java-accepted-simple-solution

Java accepted simple solution

The basic idea is that we iterate through the input array and mark elements as negative using nums[nums[i] -1] = -nums[nums[i]-1]. In this way all the numbers that we have seen will be marked as negative. In the second iteration, if a value is not marked as negative, it implies we have never seen that index before, so just add it to the return list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();

for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]) - 1;
if(nums[val] > 0) {
nums[val] = -nums[val];
}
}

for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
ret.add(i+1);
}
}
return ret;
}

https://discuss.leetcode.com/topic/66063/5-line-java-easy-understanding

5-line Java Easy-understanding

1
2
3
4
5
6
7
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < nums.length; i ++) nums[(nums[i]-1) % n] += n;
for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
return res;
}

https://discuss.leetcode.com/topic/66211/2ms-o-n-in-space-java

2ms O(n) In-Space Java

Think we surely have to negate anytime we are given an array with values from 1 to the length of array. If anyone has a better idea, will be happy to hear.

The steps followed in this is:

  1. Negate each number while traversing
  2. Run again and find the index that is not negated.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
List<Integer> result = new ArrayList<Integer>();
for( int i=0;i< nums.length; i++){
int index = nums[i];
if(nums[Math.abs(index)-1] > 0){
nums[Math.abs(index)-1]= -nums[Math.abs(index)-1];
}
}

for(int j =1 ;j <= nums.length ; j++){
if(nums[j-1] > 0){
result.add(j);
}
}
return result;

https://discuss.leetcode.com/topic/66581/simple-java-in-place-sort-solution

Simple Java In-place sort solution

The idea is simple, if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1], for example, nums[0] = 4 and nums[3] = 7, then we swap nums[0] with nums[3]. So In the end the array will be sorted and if nums[i] != i + 1, then i + 1 is missing.

1
2
3
4
5
6
7
8
9
The example run as follows

[4,3,2,7,8,2,3,1]
[7,3,2,4,8,2,3,1]
[3,3,2,4,8,2,7,1]
[2,3,3,4,8,2,7,1]
[3,2,3,4,8,2,7,1]
[3,2,3,4,1,2,7,8]
[1,2,3,4,3,2,7,8]

Since every swap we put at least one number to its correct position, the time is O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
int tmp = nums[i];
nums[i] = nums[tmp - 1];
nums[tmp - 1] = tmp;
}
}
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
res.add(i + 1);
}
}
return res;
}
}

cpp

https://discuss.leetcode.com/topic/65944/c-solution-o-1-space

c++ solution O(1) space

The idea is very similar to problem 442. Find All Duplicates in an Array: https://leetcode.com/problems/find-all-duplicates-in-an-array/.

First iteration to negate values at position whose equal to values appear in array. Second iteration to collect all position whose value is positive, which are the missing values. Complexity is O(n) Time and O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int len = nums.size();
for(int i=0; i<len; i++) {
int m = abs(nums[i])-1; // index start from 0
nums[m] = nums[m]>0 ? -nums[m] : nums[m];
}
vector<int> res;
for(int i = 0; i<len; i++) {
if(nums[i] > 0) res.push_back(i+1);
}
return res;
}
};

python

https://discuss.leetcode.com/topic/68838/python-4-lines-with-short-explanation

Python 4 lines with short explanation

For each number i in nums,

we mark the number that i points as negative.

Then we filter the list, get all the indexes

who points to a positive number.

Since those indexes are not visited.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# For each number i in nums,
# we mark the number that i points as negative.
# Then we filter the list, get all the indexes
# who points to a positive number
for i in range(len(nums)):
index = abs(nums[i]) - 1
nums[index] = - abs(nums[index])

return [i + 1 for i in range(len(nums)) if nums[i] > 0]

https://discuss.leetcode.com/topic/68430/python-one-liner

Python One-liner

1
2
3
4
5
6
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return list(set(range(1, len(nums)+1)) - set(nums))
谢谢你,可爱的朋友。