Find All Duplicates in an Array

Interview Problem Interview Medium In-place Index Mapping Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findDuplicates(nums). Every value is in [1,len(nums)] and appears once or twice. Return the values that appear twice using O(1) auxiliary space excluding the result.

Starter code

class Solution:
    def findDuplicates(self, nums):
        pass

Test cases

two-duplicates

Expected: [2,3]

Wizard outline

Step 1: Initialize Solution.findDuplicates
Replace the empty starter with the first real state owned by Solution.findDuplicates. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Two Duplicates case
Complete the readable core algorithm for one representative Interview case. Map value v to index v-1 and use the sign at that index as a visited bit.
Step 4: Harden the Duplicate Maximum boundary
Repair the reviewed boundary and pass the complete submission contract. Every allowed value maps to one valid array index. The first occurrence makes its mapped slot negative, and the second observes that negative sign and is emitted exactly once. Values appearing once are never emitted.

Footguns and prerequisites

Read abs(value) because earlier iterations may already have negated the current slot.
arrays strings two pointers sliding window

Reviewed references

LeetCode 442 — Find All Duplicates in an Array

Practice prerequisites

Mark Seen Indices(opens in a new tab)
Mark Seen Indices isolates after reading a value v, result[v - 1] is true and every previously marked position stays true. That focused state discipline is required when implementing find all duplicates array as a complete Interview Problem.

Recommended approach and implementation

For each value, inspect the slot at abs(value)-1. A negative slot means the value was seen before; otherwise negate that slot to mark it seen.

Why it works: Every allowed value maps to one valid array index. The first occurrence makes its mapped slot negative, and the second observes that negative sign and is emitted exactly once. Values appearing once are never emitted.

class Solution:
    def findDuplicates(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        duplicates = []
        for value in nums:
            index = abs(value) - 1
            if nums[index] < 0:
                duplicates.append(index + 1)
            else:
                nums[index] = -nums[index]
        return duplicates

Similar exercises

Find the Duplicate Number(opens in a new tab)