LeetCode 442: Find All Duplicates in an Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 442: Find All Duplicates in an Array?

In LeetCode 442: Find All Duplicates in an Array, you’re given an array of integers nums where each number is between 1 and n (the array’s length), and some numbers appear twice while others appear once. Your task is to return a list of all numbers that appear twice, without using extra space beyond the output array and in O(n) time. For example, with [4, 3, 2, 7, 8, 2, 3, 1], the duplicates are 2 and 3. It’s like finding the repeat offenders in a lineup where everyone should be unique.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: List[int]—all numbers appearing twice.
• Rules:
• 1 ≤ nums[i] ≤ n (n = len(nums)).
• Each number appears once or twice.
• O(n) time, no extra space (beyond output).

Constraints

• 1 <= nums.length <= 10^5.
• 1 <= nums[i] <= nums.length.

Examples to Get Us Started

• Input: nums = [4,3,2,7,8,2,3,1]
• Output: [2,3] (2 and 3 appear twice).
• Input: nums = [1,1,2]
• Output: [1] (1 appears twice).
• Input: nums = [1]
• Output: [] (No duplicates).

Understanding the Problem: Spotting the Repeat Offenders

To solve LeetCode 442: Find All Duplicates in an Array in Python, we need to identify numbers that appear twice in an array where values range from 1 to n. A naive approach—counting each number’s frequency—works but uses O(n) extra space, breaking the problem’s rules. The key insight? The numbers align with array indices (1 to n), so we can use the array itself as a marker. We’ll explore:

• Best Solution (In-Place Marking): O(n) time, O(1) space—ingenious and efficient.
• Alternative Solution (Hash Map): O(n) time, O(n) space—simple but space-heavy.

Let’s dive into the in-place marking solution—it’s the detective trick we need.

Best Solution: In-Place Marking with Array Indices

Why This Is the Best Solution

The in-place marking approach is the top pick because it’s O(n) time and O(1) space (excluding output), meeting the problem’s strict requirements. It uses the array’s indices as a natural hash table, marking numbers as seen by negating values at corresponding positions. When we see a number twice, its “marked” spot is already negative—bingo, a duplicate! It’s like leaving fingerprints on the array itself to catch the culprits red-handed!

How It Works

Here’s the strategy:

• Step 1: Iterate through nums.
• Step 2: For each number x:
• Use abs(x) - 1 as an index (since nums are 1 to n, indices are 0 to n-1).
• If nums[index] > 0, mark it negative (first visit).
• If nums[index] < 0, x is a duplicate—add to result.
• Step 3: Return duplicates.
• Why It Works:
• Numbers map to unique indices.
• Negating tracks visits without extra space.
• Second visit = duplicate.

Step-by-Step Example

Example: nums = [4,3,2,7,8,2,3,1]

• Initial: [4, 3, 2, 7, 8, 2, 3, 1], result = [].
• Process:
• 4: index = 3, [4, 3, 2, -7, 8, 2, 3, 1].
• 3: index = 2, [4, 3, -2, -7, 8, 2, 3, 1].
• 2: index = 1, [4, -3, -2, -7, 8, 2, 3, 1].
• 7: index = 6, [4, -3, -2, -7, 8, 2, -3, 1].
• 8: index = 7, [4, -3, -2, -7, 8, 2, -3, -1].
• 2: index = 1, nums[1] = -3 < 0, duplicate 2, result = [2].
• 3: index = 2, nums[2] = -2 < 0, duplicate 3, result = [2, 3].
• 1: index = 0, [ -4, -3, -2, -7, 8, 2, -3, -1].
• Result: [2, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        result = []

        # Iterate through array
        for num in nums:
            # Get index from absolute value (1-based to 0-based)
            index = abs(num) - 1

            # If positive, mark as negative (first visit)
            if nums[index] > 0:
                nums[index] = -nums[index]
            # If negative, it's a duplicate
            else:
                result.append(abs(num))

        return result

• Line 3: Initialize result list.
• Line 6-7: For each num, compute index (e.g., 4 → 3).
• Line 10-11: If nums[index] > 0, negate it (mark seen).
• Line 13-14: If already negative, num is a duplicate, add to result.
• Line 16: Return duplicates.
• Time Complexity: O(n)—one pass.
• Space Complexity: O(1)—only output space.

It’s like turning the array into a crime scene map!

Alternative Solution: Hash Map Counting

Why an Alternative Approach?

The hash map method counts each number’s frequency—O(n) time, O(n) space—making duplicates obvious. It’s intuitive, like tallying suspects in a notebook, but violates the no-extra-space rule. Great for learning or when space isn’t a constraint!

How It Works

• Step 1: Build a frequency map.
• Step 2: Collect numbers with count = 2.
• Step 3: Return duplicates.

Step-by-Step Example

Example: nums = [4,3,2,7,8,2,3,1]

• Map: {4:1, 3:2, 2:2, 7:1, 8:1, 1:1}.
• Check: 3 → 2, 2 → 2.
• Result: [2, 3] (order may vary).

Code for Hash Map Approach

Copy codeclass Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        freq = {}
        result = []

        # Count frequencies
        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        # Find duplicates
        for num, count in freq.items():
            if count == 2:
                result.append(num)

        return result

• Time Complexity: O(n)—two passes.
• Space Complexity: O(n)—hash map.

It’s a straightforward suspect lineup!

Comparing the Two Solutions

• In-Place Marking (Best):
• Pros: O(n), O(1) space, meets constraints.
• Cons: Modifies input.
• Hash Map (Alternative):
• Pros: O(n), easy to understand.
• Cons: O(n) space, breaks rules.

In-place wins for efficiency.

Edge Cases and More Examples

• Input: [1] → [].
• Input: [1,1] → [1].
• Input: [1,2,3,1] → [1].

Both handle these well.

Complexity Recap

• In-Place: Time O(n), Space O(1).
• Hash Map: Time O(n), Space O(n).

In-place is the champ.

Key Takeaways

• In-Place: Use the array as a map.
• Hash Map: Count and conquer.
• Python Tip: Arrays can multitask—see [Python Basics](/python/basics).

Final Thoughts: Nab Those Duplicates

LeetCode 442: Find All Duplicates in an Array in Python is a clever array puzzle. In-place marking is your stealthy detective tool, while hash maps offer a clear backup. Want more array challenges? Try LeetCode 448: Find All Numbers Disappeared in an Array or LeetCode 287: Find the Duplicate Number. Ready to catch some duplicates? Head to Solve LeetCode 442 on LeetCode and crack the case today—your coding skills are on the case!