Find All Duplicates in an Array solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 442. Find All Duplicates in an Array (Solution Explained)Nick White · 12:37 · 154K views
Find All Duplicates in an Array - Leetcode 442 - PythonNeetCodeIO · 9:40 · 39K views
Find all Duplicates in an Array (LeetCode 442) | Full solution with no Extra SpaceNikhil Lohia · 15:38 · 37K views
Find All Duplicates in an Array | Clean | Easy | Leetcode 442 | codestorywithMIKcodestorywithMIK · 12:11 · 14K views
Find All Duplicates in an Array without using any Extra Space | LeetCode 442Programming Tutorials · 6:45 · 4K views
FIND ALL DUPLICATES IN AN ARRAY | LEETCODE # 442 | PYTHON SOLUTIONCracking FAANG · 10:42 · 2K views
LeetCode 442. Find All Duplicates in an Array (Solution Explained)Engineering Digest · 10:38 · 1K views
442. Find All Duplicates in an Array | Leetcode MediumJOY of LIFE · 15:27 · 795 views
Leetcode | 442. Find All Duplicates in an Array | Medium | Java Solution [3 Methods]Developer Docs · 13:25 · 724 views
Python - Find All Duplicates In An Array | LeetCode 442Wrt Tech · 11:08 · 392 views
The problem
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most 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 auxiliary space, excluding the space needed to store the output
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.
Approach overview
Problem Overview: Given an integer array where 1 ≤ nums[i] ≤ n and n = nums.length, some values appear twice while others appear once. Return all elements that appear exactly twice. The constraint that values map directly to array indices allows clever in-place tricks using the array itself as a bookkeeping structure.
Approach 1: Negation Marking (O(n) time, O(1) space)
This technique treats the array as a presence map. Iterate through the array and use the absolute value of each number as an index. When visiting value x, check position x-1. If the number at that index is positive, negate it to mark that x has been seen. If it's already negative, the value x has appeared before, so it is a duplicate. This works because each number falls within the range 1..n, guaranteeing a valid index. The algorithm performs a single pass and modifies the array in-place, making it both time-efficient and memory-efficient compared to using a hash table.
Approach 2: Index-Based Value Reordering (O(n) time, O(1) space)
This method reorders numbers so each value ideally sits at its correct index (value - 1). Iterate through the array and repeatedly swap elements until the current value is either already in the correct position or a duplicate blocks the placement. If you encounter a value x where nums[x-1] already equals x, then x must be duplicated. The technique resembles cyclic placement and ensures each number moves at most once or twice, keeping the total runtime linear. This approach is useful when you prefer explicit index positioning rather than sign manipulation.
Recommended for interviews: Negation marking is typically the expected optimal solution. It demonstrates awareness of how to exploit the 1..n constraint and use the array as an in-place visited structure. Index-based reordering also achieves O(n) time and O(1) space, but involves more swaps and edge-case handling. Interviewers usually expect candidates to first recognize that a brute-force or hash map approach would require O(n) extra space, then optimize by converting the array itself into the tracking structure.
Approach 1: Negation Marking
Negation Marking: This approach leverages the integer constraints (1 to n) to use the input array itself to track occurrences. Every time an index is visited based on an element's value, we negate the number at that index if it's positive. If we encounter that index again and the number is already negative, it means the number corresponding to this index has been seen before.
def find_duplicates(nums):
duplicates = []
for num in nums:
index = abs(num) - 1
if nums[index] < 0:
duplicates.append(abs(num))
else:
nums[index] = -nums[index]
return duplicatesimport java.util.ArrayList;
import java.util.List;
public class DuplicatesFinder {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] < 0) {
duplicates.add(Math.abs(nums[i]));
} else {
nums[index] = -nums[index];
}
}
return duplicates;
}
}#include <vector>
#include <cmath>
std::vector<int> findDuplicates(std::vector<int>& nums) {
std::vector<int> duplicates;
for (int i = 0; i < nums.size(); ++i) {
int index = abs(nums[i]) - 1;
if (nums[index] < 0) {
duplicates.push_back(abs(nums[i]));
} else {
nums[index] = -nums[index];
}
}
return duplicates;
}function findDuplicates(nums) {
let duplicates = [];
nums.forEach(num => {
let index = Math.abs(num) - 1;
if (nums[index] < 0) {
duplicates.push(Math.abs(num));
} else {
nums[index] = -nums[index];
}
});
return duplicates;
}#include <stdio.h>
#include <stdlib.h>
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
int *duplicates = (int *)malloc(numsSize * sizeof(int));
*returnSize = 0;
for (int i = 0; i < numsSize; i++) {
int index = abs(nums[i]) - 1;
if (nums[index] < 0) {
duplicates[(*returnSize)++] = abs(nums[i]);
} else {
nums[index] = -nums[index];
}
}
return duplicates;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
List<int> duplicates = new List<int>();
for (int i = 0; i < nums.Length; i++) {
int index = Math.Abs(nums[i]) - 1;
if (nums[index] < 0) {
duplicates.Add(Math.Abs(nums[i]));
} else {
nums[index] = -nums[index];
}
}
return duplicates;
}
}This Python solution iterates through the list, converting the number at the index derived from each element into its negative. If an index points to an already negative number, it indicates the presence of a duplicate, and hence, the number is added to the duplicates list.
Time Complexity: O(n) as it traverses the list once.
Space Complexity: O(1) as it uses no additional space apart from the output list.
Approach 2: Index-Based Value Reordering
Index-Based Value Reordering: In this approach, we aim to place each number at the position corresponding to its value. If a position already holds the correct number, it signifies a duplicate, since we're attempting to place a number in its designated index. This allows us to directly identify duplicates while keeping the array order in check.
def find_duplicates(nums):
duplicates = []
for i in range(len(nums)):
while nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(len(nums)):
if nums[i] != i + 1:
duplicates.append(nums[i])
return duplicatesimport java.util.ArrayList;
import java.util.List;
public class DuplicatesFinder {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
duplicates.add(nums[i]);
}
}
return duplicates;
}
}#include <vector>
std::vector<int> findDuplicates(std::vector<int>& nums) {
std::vector<int> duplicates;
for (int i = 0; i < nums.size(); i++) {
while (nums[i] != nums[nums[i] - 1]) {
std::swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != i + 1) {
duplicates.push_back(nums[i]);
}
}
return duplicates;
}function findDuplicates(nums) {
let duplicates = [];
nums.forEach((_, i) => {
while (nums[i] !== nums[nums[i] - 1]) {
let temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
});
nums.forEach((num, i) => {
if (num !== i + 1) duplicates.push(num);
});
return duplicates;
}#include <stdio.h>
#include <stdlib.h>
int* findDuplicates(int* nums, int numsSize, int* returnSize) {
int *duplicates = (int *)malloc(numsSize * sizeof(int));
*returnSize = 0;
for (int i = 0; i < numsSize; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < numsSize; i++) {
if (nums[i] != i + 1) {
duplicates[(*returnSize)++] = nums[i];
}
}
return duplicates;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
List<int> duplicates = new List<int>();
for (int i = 0; i < nums.Length; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < nums.Length; i++) {
if (nums[i] != i + 1) {
duplicates.Add(nums[i]);
}
}
return duplicates;
}
}This Python solution places each number at its correct index (e.g., 1 at index 0). If a correct position is already occupied by the number, a duplicate is detected.
Time Complexity: O(n) due to swapping.
Space Complexity: O(1) as no extra space except for output.
Approach 3: Default Approach
function findDuplicates(nums: number[]): number[] {
for (let i = 0; i < nums.length; i++) {
while (nums[i] !== nums[nums[i] - 1]) {
const temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
const ans: number[] = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== i + 1) {
ans.push(nums[i]);
}
}
return ans;
}func findDuplicates(nums []int) []int {
for i := range nums {
for nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
var ans []int
for i, v := range nums {
if v != i+1 {
ans = append(ans, v)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Negation Marking | Time Complexity: O(n) as it traverses the list once. |
| Index-Based Value Reordering | Time Complexity: O(n) due to swapping. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Negation Marking | O(n) | O(1) | Best general solution when array values are in range 1..n and modification of the array is allowed |
| Index-Based Value Reordering | O(n) | O(1) | Useful when you prefer placing elements at their correct indices (cyclic placement style problems) |
Frequently asked questions
Is Find All Duplicates in an Array easy or hard?
The problem is generally classified as Medium difficulty. The challenge comes from recognizing that the value range 1..n allows in-place marking or index placement, enabling an O(n) time and O(1) space solution instead of using extra memory.
Find All Duplicates in an Array Python/Java solution
In Python or Java, the typical implementation iterates through the array and uses negation marking. For each number x, compute index x-1 and flip the sign of nums[index]. If nums[index] is already negative, x is a duplicate and should be added to the result list.
How to solve Find All Duplicates in an Array in O(n)?
Use the negation marking technique. Iterate through the array, compute the index as abs(nums[i]) - 1, and negate the value at that index if it is positive. If the value at that index is already negative, the number has appeared before and should be added to the result list.
What is the best approach for Find All Duplicates in an Array?
Negation marking is the most efficient and commonly expected approach. It runs in O(n) time and O(1) extra space by using the array itself as a visitation map. Each number marks its corresponding index by flipping the sign, and encountering an already negative value indicates a duplicate.
Is Find All Duplicates in an Array asked at Google/Amazon/Meta?
Array manipulation and in-place marking problems like this appear frequently in interviews at companies such as Amazon, Meta, and Google. The question tests understanding of array indexing tricks, space optimization, and recognizing constraints like values limited to 1..n.
What data structure is used in Find All Duplicates in an Array?
The optimized solutions primarily rely on the array itself as the tracking structure. Instead of allocating a hash set or hash map, the algorithm marks visited indices by modifying the array values. This reduces auxiliary memory usage while preserving linear time complexity.
What is the time complexity of Find All Duplicates in an Array?
The optimal solutions run in O(n) time because each element is processed at most once or twice. Both negation marking and index-based value reordering achieve linear traversal of the array. Space complexity can be reduced to O(1) by modifying the array in-place.