DSA SheetMedium
EditorialPractice

HASHING › IMPLEMENTARY PROBLEMS

Find All Duplicates in an Array

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

An array used as a sign-marked value tableShow an array of cells indexed from 0 to n - 1, with a value v associated with the cell at index v - 1. One value points to a positive cell; the algorithm negates that cell to mark the first occurrence. A later occurrence of the same value points to the same cell, now negative, and adds the value to the output. The picture makes the value-to-index mapping and the sign change represent a visited flag.value vindex v − 112−3456positive cellfirst occurrencenegative cellsecond occurrence → resultmaps to012345At index v − 1, the sign records whether v was seen before; its magnitude remains v.

Approachone pass, one sign bit per possible value

  1. 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.
  2. 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.
  3. 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.
  4. If nums[idx] is nonnegative, negate it to record the first occurrence; without this mark, the second occurrence would look identical to the first.
  5. 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.
  6. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraApart 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.

Common mistakestwo wrong code shapes that look plausible

Previous · Sum of Unique Elements