What is the time complexity of Contains Duplicate?

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

What data structures are used to solve Contains Duplicate?

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

What are the key insights for solving Contains Duplicate?

Insight 1: Efficiently checking for duplicates requires a data structure that allows for fast lookups (O(1) ideally). Insight 2: A hash table (or set) is an ideal choice because it provides average-case O(1) time complexity for insertion and lookup operations.

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

Contains Duplicate - LeetCode 217 Solution

Q: Which companies ask LeetCode 217. Contains Duplicate in interviews?

This problem is frequently asked at Accenture, Airbnb, Arista Networks, DE Shaw, J.P. Morgan and 9 more companies.

Contains Duplicate - Complete Solution Guide

Contains Duplicate is LeetCode problem 217, a Easy 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 , return true if any value appears at least twice in the array, and return false if every element is distinct. Example 1: Input: nums = [1,2,3,1] Output: true Explanation: The element 1 occurs at the indices 0 and 3. Example 2: Input: nums = [1,2,3,4] Output: false Explanation: All elements are distinct. Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Constraints: 1 <= nums.length <= 10 5 -10 9 <= nums[i] <= 10 9

Detailed Explanation

The problem asks whether an integer array contains any duplicate elements. The input is an array of integers (`nums`). The output is a boolean value: `true` if any element appears at least twice in the array, and `false` otherwise. The constraints specify that the array length can be up to 105 elements, and the integer values are within the range -109 to 109.

Solution Approach

The provided solutions use a hash set (or unordered_set in C++) to efficiently check for duplicates. The algorithm iterates through the input array. For each element, it checks if the element is already present in the hash set. If it is, a duplicate is found, and `true` is returned. Otherwise, the element is added to the hash set, and the iteration continues. If the loop completes without finding any duplicates, `false` is returned.

Step-by-Step Algorithm

Step 1: Initialize an empty hash set (or set) called `seen`.
Step 2: Iterate through the input array `nums`.
Step 3: For each element `num` in `nums`, check if `num` is present in the `seen` set.
Step 4: If `num` is found in `seen`, return `true` (duplicate found).
Step 5: If `num` is not found in `seen`, add `num` to the `seen` set.
Step 6: After iterating through all elements, return `false` (no duplicates found).

Key Insights

Insight 1: Efficiently checking for duplicates requires a data structure that allows for fast lookups (O(1) ideally).
Insight 2: A hash table (or set) is an ideal choice because it provides average-case O(1) time complexity for insertion and lookup operations.
Insight 3: Sorting the array is an alternative approach, but it increases the time complexity to O(n log n), which is less efficient than the hash table approach for larger datasets.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Sorting.

Companies

Asked at: Accenture, Airbnb, Arista Networks, DE Shaw, J.P. Morgan, Nagarro, Netflix, Palantir Technologies, Paycom, Siemens, Visa, Yandex, ZScaler, tcs.

Contains Duplicate | LeetCode 217

Easy

Array Hash Table Sorting

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

Solution Code

Available in:

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 217: Contains Duplicate - Detailed explanation and solution approaches.

Topics

Array Hash Table Sorting

Companies

AccentureAirbnbArista NetworksDE ShawJ.P. MorganNagarroNetflixPalantir Technologies

Stats

Difficulty:Easy

Languages:4

Companies:14

Problem #:217

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

6 steps

1
Step 1: Initialize an empty hash set (or set) called `seen`.
2
Step 2: Iterate through the input array `nums`.
3
Step 3: For each element `num` in `nums`, check if `num` is present in the `seen` set.
4
Step 4: If `num` is found in `seen`, return `true` (duplicate found).
5
Step 5: If `num` is not found in `seen`, add `num` to the `seen` set.
6
Step 6: After iterating through all elements, return `false` (no duplicates found).

💡

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(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm iterates through the array once (O(n)). Hash set operations (insertion and lookup) take average-case O(1) time. In the worst case (all elements are unique), the space used by the hash set will be proportional to the number of elements in the array (O(n)). The C solution using qsort has a time complexity of O(n log n) due to the sorting step. Space complexity for the C solution remains O(1) because it does sorting in place.

📖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

Sorting

Sort the array and then linearly scan for consecutive equal elements.

Time: O(n log n)Space: O(1) (in-place sort)

Trade-offs: This approach is less efficient than the hash set approach for large arrays because sorting takes longer than hash set lookups. However, it uses less space if in-place sorting is employed.

✨

Key Insights

1Insight 1: Efficiently checking for duplicates requires a data structure that allows for fast lookups (O(1) ideally).
2Insight 2: A hash table (or set) is an ideal choice because it provides average-case O(1) time complexity for insertion and lookup operations.
3Insight 3: Sorting the array is an alternative approach, but it increases the time complexity to O(n log n), which is less efficient than the hash table approach for larger datasets.

📚

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!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty input array. The solution handles this correctly; the loop will not execute, and `false` is returned.
Edge case 2: Array with all duplicate elements. The solution correctly identifies the duplicate on the second element and returns `true`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the empty array case correctly. A naive solution might throw an exception or produce undefined behavior.

✗Common mistake 2: Using a less efficient data structure for duplicate checking (e.g., using nested loops, resulting in O(n^2) time complexity).

✅

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. Checking for unique usernames or email addresses.

🏦Real-world scenario 2: Identifying duplicate transactions in financial systems to prevent fraud or errors.

💡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

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ 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: July 8, 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.

@InterviewProJun 24

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

@CodeNinjaJun 17

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 10

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Contains Duplicate"?

For this easy-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?