442. Find All Duplicates in an Array – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 442. Find All Duplicates in an Array:

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

Brute Force – O(n^2)

The simplest approach is to check every element against the remaining elements.

If I find the same number again, it’s a duplicate.

To avoid adding the same duplicate more than once, I can maintain a set of numbers I’ve already added to the answer.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        unordered_set<int> seen;

        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {

                if(nums[i] == nums[j] &&
                   seen.find(nums[i]) == seen.end()) {

                    ans.push_back(nums[i]);
                    seen.insert(nums[i]);
                }
            }
        }

        return ans;
    }
};
442. Find All Duplicates in an Array Brute Force Solution

Better O(n log n)

Can we avoid the nested loops?

What if we sort the array first?

Once sorted, all duplicate elements will be next to each other.

For example:

[4,3,2,7,8,2,3,1]

After sorting:

[1,2,2,3,3,4,7,8]

Now we just traverse the array and check whether the current element is equal to the previous one.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<int> ans;

        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == nums[i-1]) {
                ans.push_back(nums[i]);
            }
        }

        return ans;
    }
};
442. Find All Duplicates in an Array n log n solution

Optimal O(n)

Now here’s the interesting part.

The problem tells us that every number is between 1 and n.

So, we can actually use the array itself to keep track of which numbers we’ve already seen!

Think about it:

  • Number 1 corresponds to index 0.
  • Number 2 corresponds to index 1.
  • Number 3 corresponds to index 2.

And so on.

We can use the sign of the element at that index to mark whether we’ve seen a number before.

The idea:

  1. Pick a number x.
  2. Go to index x - 1.
  3. If the value there is positive, mark it negative. This is our first occurrence.
  4. If it’s already negative, we’ve seen this number before. Add it to our answer.
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;

        for(int i = 0; i < nums.size(); i++) {

            int x = abs(nums[i]);
            int idx = x - 1;

            if(nums[idx] < 0) {
                ans.push_back(x);
            }
            else {
                nums[idx] *= -1;
            }
        }

        return ans;
    }
};
442. Find All Duplicates in an Array Optimal solution

Code lines explained

  • abs(nums[i]) gets the original number because we might have already marked this position negative.
  • x - 1 gives us the index corresponding to that number.
  • If nums[idx] is already negative, we’ve encountered this number before. Add it to the answer.
  • Otherwise, make it negative to mark that we’ve seen it.

Note: This approach modifies the input array.

Leave a Reply