Contains Duplicate

12 May 2026 0 Likes

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.

The problem focuses on identifying whether the array contains any duplicate element. If the same number occurs more than once, the answer should be true.
Example 1:
Input: nums = [1, 2, 3, 1]
 Output: true
Explanation: The element 1 appears more than once in the array.
Example 2:
Input: nums = [1, 2, 3, 4]
 Output: false
Explanation: All elements are distinct, so no duplicate exists.
Example 3:
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
 Output: true
Explanation: Multiple elements appear more than once, so the array contains duplicates.

Constraints

The array contains at least 1 element and may contain large input sizes depending on platform limits. The value of each integer inside nums may be positive, negative, or zero.

The output should be:

true ā†’ if any duplicate exists
false ā†’ if all elements are distinct

An optimal solution is expected to run in linear time complexity using additional space for hashing.

Understanding the Problem

The problem is asking us to determine whether any element appears more than once inside the array.

A simple way to understand the problem is by using a brute-force approach. We can compare every element with all other elements appearing after it in the array.

For example, in the array [1, 2, 3, 1], we first compare 1 with all remaining elements:

1 == 2 ā†’ false
1 == 3 ā†’ false
1 == 1 ā†’ true

Since a matching value is found, we can conclude that the array contains a duplicate element.

In general, for every element nums[i], we check whether the same value exists again at any later index. This direct comparison approach helps in clearly understanding the actual requirement of the problem.

Hints

The first hint is to think about how we can quickly determine whether an element has already been seen earlier while traversing the array.

Instead of repeatedly comparing the current element with all remaining elements, try storing previously visited values for faster lookup.

A HashSet can help efficiently track unique elements because searching inside a set is performed in constant time.

If an element already exists in the set while traversing the array, it means a duplicate has been found immediately.

Solutions

BETTER

Sorting Based Duplicate Detection Solution

In this approach, we first sort the array so that all duplicate elements become placed next to each other.

After sorting, we traverse the array once and compare every element with its adjacent element.

If two consecutive elements are equal, it means a duplicate element exists in the array, and we immediately return true.

If no adjacent duplicate is found after completing the traversal, we return false.

This approach is more efficient than the brute-force solution because sorting reduces the need for repeated pair comparisons.
public class B_Sorting {

    public boolean containsDuplicate(int[] nums) {

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 1; i++) {

            if (nums[i] == nums[i + 1])
                return true;

        }

        return false;
    }
}
class Solution:

    def containsDuplicate(self, nums):

        nums.sort()

        for i in range(len(nums) - 1):

            if nums[i] == nums[i + 1]:
                return True

        return False
Time Complexity
O(n log n)
Space Complexity
O(1)
BRUTE FORCE

Nested Loop Duplicate Checking Solution

This approach checks every possible pair of elements present in the array using nested loops.

For each element, we compare it with all elements appearing after it. If any two elements are found to be equal, it means the array contains a duplicate value, and we immediately return true.

If no matching pair is found after checking all combinations, we return false.

Although this solution is straightforward and easy to understand, it becomes inefficient for large arrays because many unnecessary comparisons are performed.
public class A_BruteForce {

    public boolean containsDuplicate(int[] nums) {

        for (int i = 0; i < nums.length; i++) {

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] == nums[j])
                    return true;

            }

        }

        return false;
    }

}
class Solution:

    def containsDuplicate(self, nums):

        for i in range(len(nums)):

            for j in range(i + 1, len(nums)):

                if nums[i] == nums[j]:
                    return True

        return False
Time Complexity
O(nĀ²)
Space Complexity
O(1)
OPTIMAL

Optimal HashSet Solution

This approach uses a HashSet to efficiently track elements that have already been seen while traversing the array.

We iterate through each element one by one and check whether the current value already exists inside the set.

If the value is already present, it means the array contains a duplicate element, so we immediately return true. Otherwise, we insert the current element into the set and continue the traversal.

If the entire array is processed without finding any repeated value, we return false.

This solution avoids unnecessary comparisons and provides optimal performance using constant-time lookup operations.
public class C_Set {

    public boolean containsDuplicate(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {

            if (set.contains(nums[i])) {
                return true;
            }

            set.add(nums[i]);

        }

        return false;
    }
}
class Solution:

    def containsDuplicate(self, nums):

        seen = set()

        for num in nums:

            if num in seen:
                return True

            seen.add(num)

        return False
Time Complexity
O(n)
Space Complexity
O(n)

Conclusion

The Contains Duplicate problem is a fundamental array problem that teaches efficient data lookup using hashing techniques.

Although checking every possible pair works correctly, using a HashSet significantly improves performance by avoiding unnecessary comparisons.

Mastering this problem helps build a strong understanding of sets, duplicate detection, and efficient searching, which are commonly used in coding interviews and real-world applications.

šŸ’¬ Comments