Log inSign up
mediumLeetCodeNot Started

Find All Duplicates in an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 appear twice.

You must write an algorithm that runs in O(n) time and uses only O(1) extra space (excluding the output array).

Example 1 · Standard Case with Duplicates:

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]
Explanation: 2 and 3 appear twice in the array.

Example 2 · Two Distinct Duplicates:

Input: nums = [1, 1, 2]
Output: [1]
Explanation: 1 appears twice and 2 appears once.

Example 3 · No Duplicates:

Input: nums = [1]
Output: []
Explanation: Array contains only 1 element with no duplicates.

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Understanding array 0-based indexing
  • Concept of using values as indices within range [1, n]

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Learn the in-place sign negation pattern for 1-to-N bounded arrays.
  • Understand why taking abs(nums[i]) is necessary when traversing previously negated numbers.
  • Formulate in-place state tracking with zero extra memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Elements are bounded in range [1, n] for an array of size n.
  • Problem requires O(N) time and O(1) auxiliary space.
  • Need to detect duplicates or missing numbers in-place.

Algorithmic Decision Tree:

  • Whenever numbers are within [1, n], consider Sign Negation (nums[abs(x)-1] *= -1) or Cyclic Sort (swap(nums[i], nums[nums[i]-1])).

Connected Patterns:

Find the Duplicate NumberFirst Missing PositiveFind All Numbers Disappeared in an Array

1. Nested Loops Pair Check (Brute Force)

Intuition

Run two nested loops: for each i from 0 to n-1, scan j from i+1 to n-1. If nums[i] == nums[j], add to duplicate list.

When to apply: Use to illustrate the baseline search without extra space.

Nested Loops Duplicate Check (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
4 appears only once
Visual state
Values and pointers at this exact step
pointers
S
4
3
2
7
8
2
3
1
0
↑ i=0
1
2
3
4
5
6
7
Variables at this step
i
0
val
4
duplicates
[]
Check / comparison
i = 0 (val 4): Scan indices 1..7 for another 4
Decision / next transition
No duplicate 4. Continue.
Why this step matters

4 appears only once.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> findDuplicates(int[] nums) {
6 List<Integer> res = new ArrayList<>();
7 for (int i = 0; i < nums.length; i++) {
8 for (int j = i + 1; j < nums.length; j++) {
9 if (nums[i] == nums[j]) {
10 res.add(nums[i]);
11 break;
12 }
13 }
14 }
15 return res;
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
22 System.out.println("Duplicates: " + sol.findDuplicates(nums));
23 }
24}

Time & Space Complexity

  • Time complexity: O(n^2) — Nested loops examine all n*(n-1)/2 pairs.
  • Space complexity: O(1) auxiliary — O(1) extra space outside the returned list.

Why Brute Force Doesn't Scale:

For embedded or memory-constrained environments with N = 100,000, allocating 100,000 hash nodes consumes several megabytes.

Sign negation modifies the sign bits in-place with 0 additional memory allocation.

2. Hash Set / Frequency Array (Linear Time with Extra Space)

Intuition

Initialize an empty hash set. Iterate through nums: if num is already in the set, it is a duplicate, so add it to results. Otherwise, add num to the set.

When to apply: Use when extra memory is permitted or modifying the input array is forbidden.

Hash Set Membership (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First occurrences are added to hash set
Visual state
Values and pointers at this exact step
hashmap
Input array
S
4
3
2
0
↑ seen
1
2
Hash map state
3 stored entries
key
4
maps to index
seen
key
3
maps to index
seen
key
2
maps to index
seen
Insert 4, 3, 2 into seen. seen = { 4, 3, 2 }.
Variables at this step
map state
4: seen, 3: seen, 2: seen
duplicates
[]
Check / comparison
Process 4, 3, 2: none are in seen
Decision / next transition
Insert 4, 3, 2 into seen. seen = { 4, 3, 2 }.
Why this step matters

First occurrences are added to hash set.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> findDuplicates(int[] nums) {
6 List<Integer> res = new ArrayList<>();
7 Set<Integer> seen = new HashSet<>();
8 for (int num : nums) {
9 if (seen.contains(num)) {
10 res.add(num);
11 } else {
12 seen.add(num);
13 }
14 }
15 return res;
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
22 System.out.println("Duplicates: " + sol.findDuplicates(nums));
23 }
24}

Time & Space Complexity

  • Time complexity: O(n) — Single pass of n elements with O(1) hash set operations.
  • Space complexity: O(n) — Hash set stores up to n distinct elements.

3. In-Place Sign Negation Marking (Optimal & O(1) Space)

Intuition

Since 1 <= nums[i] <= n, each value maps to a valid index: idx = abs(nums[i]) - 1. If nums[idx] is already negative, we have visited this number before, meaning abs(nums[i]) is a duplicate! Otherwise, negate nums[idx] to mark it as visited.

When to apply: Use whenever elements are in the range 1 <= nums[i] <= n and O(1) extra space is required.

In-Place Sign Negation (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Negating the slot serves as an in-place visited flag without allocating memory
Visual state
Values and pointers at this exact step
pointers
S
4
3
2
-7
8
2
3
1
0
↑ curr
1
2
3
↑ mark
4
5
6
7
Variables at this step
i
0
val
4
targetIdx
3
markedNeg
-7
Check / comparison
i = 0 (val 4): target index is abs(4) - 1 = 3. Check nums[3] (7)
Decision / next transition
nums[3] is positive. First time seeing 4! Negate nums[3] to -7.
Why this step matters

Negating the slot serves as an in-place visited flag without allocating memory.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public List<Integer> findDuplicates(int[] nums) {
6 List<Integer> res = new ArrayList<>();
7 for (int i = 0; i < nums.length; i++) {
8 int idx = Math.abs(nums[i]) - 1;
9 if (nums[idx] < 0) {
10 res.add(Math.abs(nums[i]));
11 } else {
12 nums[idx] = -nums[idx];
13 }
14 }
15 return res;
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
22 System.out.println("Duplicates: " + sol.findDuplicates(nums));
23 }
24}

Time & Space Complexity

  • Time complexity: O(n) — Single linear pass visiting each element once.
  • Space complexity: O(1) auxiliary — Modifications are made in-place using sign bits; no extra data structures are used.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set / Frequency MapO(N)O(N)Maintain a Hash Set to track seen numbers. If a number is already in the set, add it to result.Hash Set allocation for N elements.
2.Better — Sorting the ArrayO(N log N)O(1)Sort the array in-place. Then iterate from index 0 to n - 2; if nums[i] == nums[i + 1], append nums[i].Sorting comparison operations.
3.Optimal — In-place Sign Negation MarkingOptimalO(N)O(1)Iterate through nums. For each x = abs(nums[i]), check nums[x - 1]. If nums[x - 1] < 0, x is a duplicate. Else, negate nums[x - 1].None; optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Find All Duplicates in an Array?

2.Why is the brute force approach suboptimal for large inputs in Find All Duplicates in an Array?

3.Which data structure or technique enables the optimal solution for Find All Duplicates in an Array?

Back to DSA Sheet