251. Find All Duplicates in an Array

For each number, negate the value at the corresponding index. If it's already negative, the number is a duplicate.

Approach

1. For each num, mark nums[abs(num)-1] as negative.
2. If nums[abs(num)-1] is already negative, num is a duplicate.

Complexity

• Time: O(n)
• Space: O(1)

import java.util.*;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            int idx = Math.abs(num) - 1;
            if (nums[idx] < 0) {
                result.add(Math.abs(num));
            } else {
                nums[idx] = -nums[idx];
            }
        }
        return result;
    }
}