algoadvance

Leetcode 442. Find All Duplicates in an Array

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Clarifying Questions

1. Input Constraints: Can nums be empty?
   • If yes, should we return an empty array?
2. Range and Input Validity: Are we guaranteed that all elements in nums are within the range [1, n]?
3. Return Order: Does the order of the duplicates in the returned array matter?

Strategy

Since the problem requires O(n) time complexity and O(1) (constant) extra space, we can’t use additional data structures like hash maps or sets which would not satisfy the space constraint.

Instead, we can use the input array itself to keep track of numbers that we’ve seen before. Here’s the plan:

1. Iterate through each number in the array.
2. For each number, treat its absolute value as an index and make the element at that index negative.
3. If we encounter an index that has already been marked negative, it means the number corresponding to that index is a duplicate.
4. Collect all such duplicate numbers and return them at the end.

This approach works because we are utilizing the existing array to keep track of the numbers we’ve seen and leveraging the fact that the indices fall within a predictable range [1, n].

Code

#include <vector>
#include <cmath>

using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        int index = abs(nums[i]) - 1;
        
        // If the value at this index is already negative, it means we have seen the number before
        if (nums[index] < 0) {
            result.push_back(abs(nums[i]));
        } else {
            nums[index] = -nums[index];
        }
    }

    return result;
}

Time Complexity

The time complexity of this solution is O(n) because:

• We iterate through the list once to process each element, marking corresponding indices as negative or identifying duplicates.

Space Complexity

The space complexity is O(1) (constant space):

• We are reusing the input list for marking visited elements.
• The additional space used by the result vector to store duplicates can be considered as O(D), where D is the number of duplicates. However, since D can at most be n/2, it is often acceptable to consider it as constant space relative to the input size (n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?