Find all duplicate elements in a limited range array

Find the duplicate numbers in an integer array of size n that contains elements between 1 and n, at least one of which repeats.

For example,

Input: nums[] = [5, 3, 4, 2, 5, 1, 2]
Output: [5, 2]

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

1. Using Frequency Map

A simple solution is to store the count of each element present in the input array in a map. Then iterate through the map and collect elements having a frequency of two or more.

The algorithm can be implemented as follows in C++, Java, and Python. We can also use a count array instead of a map, since using a map does not take advantage of the fact that all array elements lie in the range 1 and n.

C++

#include <iostream>

#include <vector>

#include <unordered_set>

#include <unordered_map>

using namespace std;

unordered_set<int> findDuplicates(vector<int> const &nums)

{

// create an empty map to store the count of each array element

unordered_map<int, int> freq;

// traverse the input array and update the frequency of each element

for (int i: nums) {

freq[i]++;

}

unordered_set<int> result;

// iterate through the frequency map and collect elements having a count of two or more

for (auto &it: freq)

{

if (it.second >= 2) {

result.insert(it.first);

}

return result;

}

int main()

{

vector<int> nums = { 5, 3, 4, 2, 5, 1, 2 };

unordered_set<int> result = findDuplicates(nums);

for (auto &i: result) {

cout << i << ' ';

}

return 0;

}

Download Run Code

Output:

5 2

Java

import java.util.HashMap;

import java.util.Map;

import java.util.Set;

import java.util.stream.Collectors;

class Main

{

public static Set<Integer> findDuplicates(int[] nums)

{

// create an empty map to store the count of each array element

Map<Integer, Integer> freqMap = new HashMap<>();

// traverse the input array and update the frequency of each element

for (int i: nums) {

freqMap.put(i, freqMap.getOrDefault(i, 0) + 1);

}

// iterate through the frequency map and collect elements

// having a count of two or more

return freqMap.keySet().stream()

.filter(key -> freqMap.get(key) >= 2)

.collect(Collectors.toSet());

}

public static void main(String[] args)

{

int[] nums = { 5, 3, 4, 2, 5, 1, 2 };

Set<Integer> result = findDuplicates(nums);

System.out.println(result);

}

Download Run Code

Output:

[5, 2]

Python

def findDuplicates(nums):

# create an empty map to store the count of each array element

freq = {}

# traverse the input array and update the frequency of each element

for i in nums:

freq[i] = freq.setdefault(i, 0) + 1

# iterate through the frequency map and collect elements having a count of two or more

return {key for key in freq.keys() if freq[key] >= 2}

if __name__ == '__main__':

nums = [5, 3, 4, 2, 5, 1, 2]

result = findDuplicates(nums)

print(result)

Download Run Code

Output:

{2, 5}

The time complexity of the above solution is O(n) and requires O(n) extra space for Map data structure, where n is the length of the array.

2. Using Array Indices

Since all of the array’s elements lie within the range [1,n], we can check for duplicate elements by marking array elements as negative using the array index as a key. For each element in the array nums[i], invert the sign of the element present at the index i-1. However, if the element at the index i-1 is already negative, then it is repeated.

Following is the C++, Java, and Python implementation based on the idea:

C++

#include <iostream>

#include <vector>

#include <unordered_set>

using namespace std;

unordered_set<int> findDuplicates(vector<int> nums) // no-const, no-ref

{

unordered_set<int> result;

// do for each element of the array

for (int i: nums)

{

// consider index `i-1` for the current element `i`

// take absolute value since `i` is positive in the input array

int index = abs(i) - 1;

// if the element at index `i-1` is negative, the current element is repeated

if (nums[index] < 0) {

result.insert(abs(i));

}

// invert the sign of the element at index `i-1`

nums[index] = -nums[index];

}

return result;

}

int main()

{

vector<int> nums = { 5, 3, 4, 2, 5, 1, 2 };

unordered_set<int> result = findDuplicates(nums);

for (auto &i: result) {

cout << i << ' ';

}

return 0;

}

Download Run Code

Output:

5 2

Java

import java.util.HashSet;

import java.util.Set;

class Main

{

public static Set<Integer> findDuplicates(int[] nums)

{

Set<Integer> result = new HashSet<>();

// do for each element of the array

for (int i: nums)

{

// consider index `i-1` for the current element `i`

// take absolute value since `i` is positive in the input array

int index = Math.abs(i) - 1;

// if the element at index `i-1` is negative, the current element is repeated

if (nums[index] < 0) {

result.add(Math.abs(i));

}

// invert the sign of the element at index `i-1`

nums[index] = -nums[index];

}

// restore the original array before returning

for (int i = 0; i < nums.length; i++)

{

// make negative elements positive

if (nums[i] < 0) {

nums[i] = -nums[i];

}

return result;

}

public static void main(String[] args)

{

int[] nums = { 5, 3, 4, 2, 5, 1, 2 };

Set<Integer> result = findDuplicates(nums);

System.out.println(result);

}

Download Run Code

Output:

[5, 2]

Python

def findDuplicates(nums):

result = set()

# do for each element of the array

for i in nums:

# consider index `i-1` for the current element `i`

# take absolute value since `i` is positive in the input array

index = abs(i) - 1

# if the element at index `i-1` is negative, the current element is repeated

if nums[index] < 0:

result.add(abs(i))

# invert the sign of the element at index `i-1`

nums[index] = -nums[index]

# restore the original list before returning

for i in range(len(nums)):

# make negative elements positive

if nums[i] < 0:

nums[i] = -nums[i]

return result

if __name__ == '__main__':

nums = [5, 3, 4, 2, 5, 1, 2]

result = findDuplicates(nums)

print(result)

Download Run Code

Output:

{2, 5}

The time complexity of the above solution is O(n) and requires O(1) extra space, where n is the length of the array.