Array Duplicates

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Find all duplicates in an array of integers 1..n.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find all duplicates in an array of integers 1..n. Mark visited by negating at index nums[i]-1.

Algorithm

1For each num: idx = abs(num)-1. If nums[idx] < 0: it is a duplicate. Else: negate nums[idx].

Common Pitfalls

• Classic O(n) time O(1) space using sign-flip trick. Restore if needed after.

Array Duplicates.java

Java

// Approach: Use a HashSet to track seen elements, collect duplicates.
// Alternatively use index marking: for each num, negate arr[|num|-1] and check sign.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> findDuplicates(int[] arr) {
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int index = Math.abs(arr[i]) - 1;

            // If already visited, it's a duplicate
            if (arr[index] < 0)
                result.add(index + 1);
            else
                // Mark as visited
                arr[index] = -arr[index];
        }

        return result;
    }
}

Was this solution helpful?