Find All Duplicates in an Array — Editorial

Opening the reading…

Intuitionthe array stores its own visited marks

A value v can appear only when 1 <= v <= n, so it naturally identifies one position: index v - 1. That makes the array a built-in address table. Instead of allocating a separate record for every value, you use the cell at index v - 1 to remember whether v has already appeared.

The sign of that cell supplies one extra bit of information without changing its magnitude. When you process a number v, inspect nums[v - 1]. A positive cell means v has not been marked yet, so negate it. A negative cell means an earlier occurrence already marked v, so v is exactly a duplicate. Taking the absolute value first keeps the current number readable even after earlier marks have changed signs.

Approachone pass, one sign bit per possible value

Create an empty result vector and scan nums from left to right, because every value must be processed and the result is the only storage the problem allows you to allocate.

For each nums[i], compute idx = abs(nums[i]) - 1, because an earlier iteration may have negated the current cell and the original magnitude is still the value's address.

Inspect nums[idx]. If it is negative, append abs(nums[i]) to the result because this value has already been marked once and each value appears at most twice.

If nums[idx] is nonnegative, negate it to record the first occurrence; without this mark, the second occurrence would look identical to the first.

Do not mark using index i. The position being visited in the scan is unrelated to the value being counted, while idx is the position reserved for that value.

Return the result after the scan. Every duplicate is appended on its second encounter, so no sorting or second pass is needed.

Complexitythe input array is the constant-space hash table

MEASURE	BOUND	WHY
Time	O(n)	The loop performs one constant-time address calculation, sign check, and possible negation for each of the n input positions. No value causes a nested scan, so the total number of operations grows directly with the number of elements.
Space	O(1) extra	Apart from the returned output vector, the solution stores only a few scalar variables. It reuses nums for all visited marks, so the working-memory bound stays constant even in the worst case where every value appears twice and the output has size n / 2.

Here n is the length of nums. The returned result is output storage and is excluded from the extra-space bound.

Annotated solutionC++ · in-place sign marking · complete judge-ready class

CPPScan once, recover each value with its absolute magnitude, and use the addressed cell's sign as the visited flag.

#include <cstdlib>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            int value = abs(nums[i]);
            int idx = value - 1;

            if (nums[idx] < 0) {
                res.push_back(value);
            } else {
                nums[idx] = -nums[idx];
            }
        }

        return res;
    }
};

The two assignments that carry the whole idea are value = abs(nums[i]) and nums[idx] = -nums[idx]. The first prevents a previous mark from corrupting the address; the second makes the next occurrence observable. The duplicate branch does not negate the cell again, because it only needs to report the value and leaving the existing negative mark unchanged keeps the state consistent.