Contains Duplicate

Problem Link

Contains Duplicate - LeetCode

Problem: Contains Duplicate

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.

Examples

Example 1
Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs more than once (indices 0 and 3).

Example 2
Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are unique.

Example 3
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: Multiple elements occur more than once.

Constraints

• 1 <= nums.length <= 10⁵

• -10⁹ <= nums[i] <= 10⁹

Intuition

To detect if any element appears more than once, we can utilize a HashMap or HashSet to track the elements we've seen so far. If we encounter an element that already exists in the map or set, we immediately return true.

Approach

1. Initialize an empty HashMap<Integer, Integer> or HashSet<Integer>.

2. Iterate through the array nums.

3. For each element:

   • If it is already in the map/set, return true.

   • Otherwise, add it to the map/set.

4. After the loop, return false if no duplicates were found.

Code (Java)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            if (map.containsKey(i)) return true;
            map.put(i, 1);
        }
        return false;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  We iterate through the array once, and each operation on the map takes constant time on average.

• Space Complexity: O(n)
  In the worst case (all unique elements), we store all n elements in the map.

Dry Run

Input: nums = [1, 2, 3, 1]

• Initialize empty map: {}

• 1 not in map → insert → {1}

• 2 not in map → insert → {1, 2}

• 3 not in map → insert → {1, 2, 3}

• 1 already in map → return true

Conclusion

This problem is a direct application of using a hash-based data structure to detect duplicates efficiently. The use of a HashMap or HashSet ensures linear time complexity, making it suitable for large input sizes.