Contains Duplicate

LeetCode 217 | Difficulty: Easy

Easy

Problem Description

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`

Topics: Array, Hash Table, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 179 ms)

Metric	Value
Runtime	179 ms
Memory	N/A
Date	2017-11-09

Solution

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
 if (nums.Length == 0) return false;
    Array.Sort(nums);
    for (int i = 1; i < nums.Length; i++)
    {
        if(nums[i] == nums[i-1]) return true;
    }
    return false;
    }
}

📜 1 more C# submission(s)

Submission (2017-11-09) — 232 ms, N/A

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
var duplicatenumsList = nums.GroupBy(x=>x).Where(g=>g.Count()>1).ToList();
    if(duplicatenumsList.Count > 0) return true; else return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.