Code Implementation

class Solution:
    def findDuplicates(self, nums):
        res = []
        for num in nums:
            idx = abs(num) - 1
            if nums[idx] < 0:
                res.append(abs(num))
            else:
                nums[idx] = -nums[idx]
        return res
      

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            int idx = abs(nums[i]) - 1;
            if (nums[idx] < 0) {
                res.push_back(abs(nums[i]));
            } else {
                nums[idx] = -nums[idx];
            }
        }
        return res;
    }
};
      

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;
    }
}
      

var findDuplicates = function(nums) {
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        let idx = Math.abs(nums[i]) - 1;
        if (nums[idx] < 0) {
            res.push(Math.abs(nums[i]));
        } else {
            nums[idx] = -nums[idx];
        }
    }
    return res;
};
      

Problem Description

Given an array of integers nums where each integer is in the range 1 to n (where n is the length of the array), some elements appear twice and others appear once. Your task is to find all the elements that appear exactly twice in this array, and return them as a list. You must solve this without using extra space (except for the output list), and in linear time.

• You may not modify the input array permanently unless allowed.
• Each element in nums appears either once or twice.
• Return the answer in any order.

Thought Process

At first glance, the simplest way to find duplicates is to use a hash table (such as a Python set or dict) to record numbers we've seen so far. As we iterate, if we see a number again, we know it's a duplicate. However, the problem restricts us from using extra space beyond the output list, so we need to find a more efficient approach.

Since all numbers are in the range 1 to n, we can cleverly use this property to mark which numbers we've seen by modifying the input array in-place. This avoids the need for extra storage, and allows us to detect duplicates by checking the sign of elements at certain indices.

The key insight is to use the value as an index and flip the sign of the number at that index. If we encounter a value whose corresponding index is already negative, that means we've seen this number before.

Solution Approach

Here's a step-by-step breakdown of the optimized solution:

1. Iterate over each number in nums: For each number, take its absolute value (since we might have negated it earlier).
2. Use value as index: Subtract 1 from the absolute value to get a zero-based index (idx = abs(num) - 1).
3. Check the sign: If nums[idx] is already negative, it means we've seen this number before, so add the absolute value to the result list.
4. Mark as seen: Otherwise, negate nums[idx] to mark this value as seen.
5. Return result: At the end, the result list contains all numbers that appeared twice.

This approach leverages the fact that the numbers map directly to indices, and that flipping the sign is a reversible way to mark presence.

Example Walkthrough

Let's take the array [4,3,2,7,8,2,3,1] as an example.

1. Start with res = [].
2. First number is 4. Index is 3. nums[3] is 7 (positive), so flip to -7. Array becomes [4,3,2,-7,8,2,3,1].
3. Next is 3. Index is 2. nums[2] is 2 (positive), flip to -2. Array: [4,3,-2,-7,8,2,3,1].
4. Next is -2. Absolute value is 2. Index is 1. nums[1] is 3 (positive), flip to -3. Array: [4,-3,-2,-7,8,2,3,1].
5. Next is -7. Absolute value is 7. Index is 6. nums[6] is 3 (positive), flip to -3. Array: [4,-3,-2,-7,8,2,-3,1].
6. Next is 8. Index is 7. nums[7] is 1 (positive), flip to -1. Array: [4,-3,-2,-7,8,2,-3,-1].
7. Next is 2. Index is 1. nums[1] is -3 (negative), so 2 is a duplicate! Add 2 to result.
8. Next is -3. Absolute value is 3. Index is 2. nums[2] is -2 (negative), so 3 is a duplicate! Add 3 to result.
9. Next is -1. Absolute value is 1. Index is 0. nums[0] is 4 (positive), flip to -4.

Final result: [2, 3], which are the numbers that appear twice.

Time and Space Complexity

• Brute-force:
  • Time: O(n^2) if you use nested loops to check for duplicates.
  • Space: O(1), but very slow.
• Hash Table Approach:
  • Time: O(n) because lookups and insertions are constant time.
  • Space: O(n) for the hash table.
• Optimized In-place Approach (used above):
  • Time: O(n) since we visit each element once.
  • Space: O(1) extra space (excluding the output list), because we're only modifying the input array.

Summary

By leveraging the constraints of the problem—that all numbers are in the range 1 to n—we can use the input array itself to track which numbers have been seen by flipping the sign at their corresponding indices. This in-place marking allows us to find all duplicates in a single linear pass, using constant extra space. This solution is both efficient and elegant, and demonstrates how understanding problem constraints can lead to creative optimizations.