Problem 36 - Contains Duplicate

Explore our archive for previous posts.

Problem 35 - Majority Element

Problem 34 - Interleaving String

Question

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

Example 2:

Input: nums = [1,2,3,4]
Output: false

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

Approach

The high-level approach to solving this problem is to use a HashSet data structure. We iterate through the input array of numbers, and for each number, we check if it is already present in the HashSet. If it is, we've found a duplicate, and we can return true. If not, we add the number to the HashSet to keep track of it. If we complete the loop without finding any duplicates, we return false. This approach efficiently identifies duplicates by taking advantage of the constant-time lookup operation provided by HashSets.

Solution

Solve it here

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            // Duplicate element found
            if (set.contains(num)) {
                return true;
            }
            
            // Otherwise, add the number to the set.
            set.add(num);
        }
        
        // No duplicates were found.
        return false;
    }
}

Time and space complexity

Time Complexity: The loop runs in O(n) time, where n is the length of the input array. The HashSet's contains and add operations are O(1) on average, so the overall time complexity is O(n).

Space Complexity: The space used by the HashSet is O(n) in the worst case, where all elements are unique.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!