What is the time complexity of Find All Duplicates in an Array?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Find All Duplicates in an Array?

This problem uses Array, Hash Table. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find All Duplicates in an Array?

Insight 1: The problem leverages the fact that the numbers are within the range [1, n] to use the input array itself as a hash table. This allows us to achieve constant extra space. Insight 2: By negating the number at the index corresponding to the current number's value (minus 1), we can mark that number as visited. If we encounter the same number again, the corresponding index will already have a negative value, indicating a duplicate.

Which companies ask LeetCode 442. Find All Duplicates in an Array in interviews?

This problem is frequently asked at Pocket Gems.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find All Duplicates in an Array - LeetCode 442 Solution

Find All Duplicates in an Array - Complete Solution Guide

Find All Duplicates in an Array is LeetCode problem 442, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice , return an array of all the integers that appears twice . You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output Example 1: Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3] Example 2: Input: nums = [1,1,2] Output: [1] Example 3: Input: nums = [1] Output: [] Constraints: n == nums.leng

Detailed Explanation

The problem asks us to find all duplicate numbers in an integer array `nums` where each number is within the range [1, n], and each number appears either once or twice. We need to return an array containing the numbers that appear twice. The critical constraint is to achieve O(n) time complexity and constant auxiliary space complexity, excluding the output array's space.

Solution Approach

The solution iterates through the input array `nums`. For each number `num`, it calculates the index `index` as `abs(num) - 1`. It then checks the sign of `nums[index]`. If `nums[index]` is negative, it means that the number `abs(num)` has been encountered before, and therefore, it's a duplicate. The duplicate is added to the result array. If `nums[index]` is positive, it means the number `abs(num)` is encountered for the first time, and we negate `nums[index]` to mark it as visited. This effectively uses the array itself as a hash table to detect duplicates without requiring additional space.

Step-by-Step Algorithm

Step 1: Initialize an empty list `result` to store the duplicate numbers.
Step 2: Iterate through the input array `nums` using a loop.
Step 3: For each number `num` in `nums`, calculate the index `index = abs(num) - 1`.
Step 4: Check the sign of `nums[index]`:
- If `nums[index] < 0`, it means the number `abs(num)` is a duplicate. Add `abs(num)` to the `result` list.
- If `nums[index] >= 0`, it means the number `abs(num)` is encountered for the first time. Negate `nums[index]` to mark it as visited: `nums[index] = -nums[index]`.
Step 5: After iterating through all the numbers in `nums`, return the `result` list.

Key Insights

Insight 1: The problem leverages the fact that the numbers are within the range [1, n] to use the input array itself as a hash table. This allows us to achieve constant extra space.
Insight 2: By negating the number at the index corresponding to the current number's value (minus 1), we can mark that number as visited. If we encounter the same number again, the corresponding index will already have a negative value, indicating a duplicate.
Insight 3: The absolute value of the number is used to determine the index to avoid issues with negative indices. The sign of the number at the index indicates whether the number has been seen before.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Hash Table.

Companies

Asked at: Pocket Gems.

Find All Duplicates in an Array | LeetCode 442

Medium

Array Hash Table

Time: O(n)Space: O(1)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            if (nums[index] < 0) {
                result.add(Math.abs(num));
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 442: Find All Duplicates in an Array - Detailed explanation and solution approaches.

Topics

Array Hash Table

Companies

Pocket Gems

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:442

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize an empty list `result` to store the duplicate numbers.
2
Step 2: Iterate through the input array `nums` using a loop.
3
Step 3: For each number `num` in `nums`, calculate the index `index = abs(num) - 1`.
4
Step 4: Check the sign of `nums[index]`:
5
- If `nums[index] < 0`, it means the number `abs(num)` is a duplicate. Add `abs(num)` to the `result` list.
6
- If `nums[index] >= 0`, it means the number `abs(num)` is encountered for the first time. Negate `nums[index]` to mark it as visited: `nums[index] = -nums[index]`.
7
Step 5: After iterating through all the numbers in `nums`, return the `result` list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because we iterate through the array only once. The space complexity is O(1) because we are modifying the input array in place and using a fixed amount of extra space regardless of the input size. The output list is not counted as auxiliary space, based on the problem description.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Hash Table

Use a hash table (dictionary in Python, HashMap in Java) to store the frequency of each number in the array. Iterate through the array and increment the count for each number. If a number's count becomes 2, add it to the result.

Time: O(n)Space: O(n)

Trade-offs: This approach uses O(n) extra space, which violates the problem constraint of constant auxiliary space. However, it's a simpler and more intuitive solution if the space constraint is not a concern.

Sorting

Sort the array. Then, iterate through the sorted array and check for adjacent elements that are equal. If two adjacent elements are equal, it's a duplicate.

Time: O(n log n) due to sorting.Space: O(1) if an in-place sorting algorithm is used, otherwise O(n).

Trade-offs: The time complexity is higher than the O(n) requirement. It modifies the input array (if sorting is done in place).

✨

Key Insights

1Insight 1: The problem leverages the fact that the numbers are within the range [1, n] to use the input array itself as a hash table. This allows us to achieve constant extra space.
2Insight 2: By negating the number at the index corresponding to the current number's value (minus 1), we can mark that number as visited. If we encounter the same number again, the corresponding index will already have a negative value, indicating a duplicate.
3Insight 3: The absolute value of the number is used to determine the index to avoid issues with negative indices. The sign of the number at the index indicates whether the number has been seen before.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Empty input array (nums = []). The code handles this correctly because the loop won't execute, and an empty result list will be returned.
Edge case 2: Array with only one element (nums = [1]). The code will still work correctly; the loop will execute once, and the index will be 0. The value at nums[0] will be negated, and no duplicate will be added to the result.
Edge case 3: Array with all same elements (nums = [1, 1, 1]). The solution correctly identifies the first duplicate '1' and marks the element at index 0 as negative. The next time '1' is encountered, it is correctly identified as a duplicate.
Edge case 4: Array containing n different elements from 1 to n (nums = [1, 2, 3, ..., n]). The code will correctly negate each element without adding anything to the result, as there are no duplicates.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the absolute value when calculating the index. This can lead to incorrect indexing and potentially out-of-bounds access.

✗Common mistake 2: Failing to negate the value at the index, which prevents the algorithm from correctly identifying duplicates.

✗Common mistake 3: Using extra space. The problem specifically requires a solution with O(1) auxiliary space.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting duplicate entries in a database or spreadsheet, especially when memory usage is a concern.

🏦Real-world scenario 2: Identifying duplicate files in a file system based on their content or metadata. While full file comparison is common, this approach could be adapted to check for duplicated identifiers within a smaller data structure related to file metadata.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find All Duplicates in an Array"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?