Duplicate Element Identification — Problem Statement & Solution Guide
Problem Description
Given an array of integers containing elements from 1 to n, where n is the length of the array, identify all elements that appear exactly twice in the array and return them in a list.
Examples
Input
[4, 3, 2, 7, 8, 2, 3, 1]
Output
[2, 3]
Explanation: Step-by-step: with input [4, 3, 2, 7, 8, 2, 3, 1], we count the occurrences of each element. We find that 2 and 3 appear exactly twice, so we return [2, 3].
Input
[1, 2, 3, 4, 5, 6, 7, 8]
Output
[]
Explanation: Step-by-step: with input [1, 2, 3, 4, 5, 6, 7, 8], we count the occurrences of each element. We find that no elements appear exactly twice, so we return an empty list.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= n
Optimal Approach & Strategy
Iterate array. For each num, take absolute value as index. If value at that index is negative, num is a duplicate. Else, negate the value at that index. Time O(N), Space O(1).
Brute Force Approach
Use HashSet to find duplicates. Space O(N).
Verified Code Solutions
function solution(nums) { let count = {}; for (let num of nums) { if (count[num]) { count[num]++; } else { count[num] = 1; } } let result = []; for (let num in count) { if (count[num] === 2) { result.push(parseInt(num)); } } return result; }class Solution { public: vector<int> solution(vector<int>& nums) { unordered_map<int, int> count; for (int num : nums) { count[num]++; } vector<int> result; for (auto& pair : count) { if (pair.second == 2) { result.push_back(pair.first); } } return result; } }import java.util.HashMap; import java.util.ArrayList; class Solution { public int[] solution(int[] nums) { HashMap<Integer, Integer> count = new HashMap<>(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } ArrayList<Integer> result = new ArrayList<>(); for (int num : count.keySet()) { if (count.get(num) == 2) { result.add(num); } } int[] arr = new int[result.size()]; for (int i = 0; i < result.size(); i++) { arr[i] = result.get(i); } return arr; } }def solution(nums): count = {}; for num in nums: if num in count: count[num] += 1; else: count[num] = 1; result = [int(num) for num in count if count[num] == 2]; return resultfunction solution(nums) { let count = {}; for (let num of nums) { if (count[num]) { count[num]++; } else { count[num] = 1; } } let result = []; for (let num in count) { if (count[num] === 2) { result.push(parseInt(num)); } } return result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.