Algorithm
Problem Name: 442. Find All Duplicates in an Array
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Example 2:
Input: nums = [1,1,2] Output: [1]
Example 3:
Input: nums = [1] Output: []
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= n- Each element in
numsappears once or twice.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findDuplicates(int[] nums) {
List list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[Math.abs(nums[i]) - 1] < 0) {
list.add(Math.abs(nums[i]));
}
nums[Math.abs(nums[i]) - 1] *= -1;
}
return list;
}
}
Input
nums = [4,3,2,7,8,2,3,1]
Output
[2,3]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const findDuplicates = function(nums) {
if (nums === null || nums.length <= 1) {
return [];
}
let dup = [];
for (let i = 0, n = nums.length; i < n; i++) {
let next = Math.abs(nums[i]);
nums[next - 1] < 0 ? dup.push(next) : (nums[next - 1] = -nums[next - 1]);
}
return dup;
};
console.log(findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]));
console.log(findDuplicates([10, 2, 5, 10, 9, 1, 1, 4, 3, 7]));
Input
nums = [4,3,2,7,8,2,3,1]
Output
[2,3]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
out=list()
for i in range(len(nums)):
if nums[abs(nums[i])-1]<0: out.append(abs(nums[i]))
else: nums[abs(nums[i])-1]*=-1
return out
Input
nums = [1,1,2]
Output
[1]
#4 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0442_FindAllDuplicatesInAnArray
{
public IList < int> FindDuplicates(int[] nums)
{
var result = new List<int>();
for (int i = 0; i < nums.Length; i++)
{
var num = Math.Abs(nums[i]);
if (nums[num - 1] < 0)
result.Add(num);
else
nums[num - 1] *= -1;
}
return result;
}
}
}
Input
nums = [1,1,2]
Output
[1]