Array Duplicates

JavaView on GFG

Time: O(n)

Space: O(n)

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?