40-Find-All-Duplicates-in-an-Array.md

Find All Duplicates in an Array

Problem Link

https://leetcode.com/problems/find-all-duplicates-in-an-array/

---

Pattern

• Index Marking

---

Approach

Use sign flipping or index marking: for each num, check index abs(num)-1; if already negative, it's a duplicate.

---

Time Complexity

O(n)

Space Complexity

O(1) (output excluded)

---

Java Solution

import java.util.*;
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] < 0) res.add(Math.abs(nums[i]));
            else nums[idx] = -nums[idx];
        }
        return res;
    }
}