LeetCode 442: Find All Duplicates in an Array Solution

Master LeetCode problem 442 (Find All Duplicates in an Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

442. Find All Duplicates in an Array

Medium

Array Hash Table

Problem Explanation

Explanation

To solve this problem, we can utilize the fact that all integers are in the range [1, n] and each integer appears at most twice. We can iterate through the array and for each number num, we can negate the value at index num-1 (as the values are in the range [1, n]). If we encounter a negative value at index num-1, it means that num has already been encountered before and it is a duplicate.

Algorithm

Initialize an empty list result to store the duplicates.
Iterate through the array nums.
For each number num, calculate the index as abs(num) - 1.
If nums[index] is negative, add abs(num) to result.
Otherwise, negate the value at index index.
Return the list result containing all duplicates.

Time Complexity

The time complexity of this algorithm is O(n) where n is the length of the input array nums.

Space Complexity

The space complexity of this algorithm is O(1) as we are using constant auxiliary space.

Solution Code

import java.util.ArrayList;
import java.util.List;

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 442 (Find All Duplicates in an Array)?

This page provides optimized solutions for LeetCode problem 442 (Find All Duplicates in an Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 442 (Find All Duplicates in an Array)?

The time complexity for LeetCode 442 (Find All Duplicates in an Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 442 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 442 in Java, C++, or Python.

Back to LeetCode Solutions