Contains Duplicate

EASY

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⁵
-10⁹ <= nums[i] <= 10⁹

Approaches

Checkout 3 different approaches to solve Contains Duplicate. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Compare each element with every other element in the array using nested loops to find duplicates.

Algorithm

Iterate through the array with index i from 0 to n-1
For each i, iterate with index j from i+1 to n-1
If nums[i] equals nums[j], return true
If no duplicates found, return false

This approach involves using two nested loops to compare each element with every other element in the array. For each element at index i, we compare it with all elements at indices j > i. If we find any match, we return true indicating a duplicate was found. If no duplicates are found after checking all pairs, we return false.

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;
}

Complexity Analysis

Time Complexity: O(n²) where n is the length of the array as we use nested loopsSpace Complexity: O(1) as we only use a constant amount of extra space

Pros and Cons

Pros:

Simple to implement
No extra space required
Works well for very small arrays

Cons:

Very inefficient for large arrays
Time complexity is quadratic
Not suitable for large scale applications

Code Solutions

Checking out 5 solutions in different languages for Contains Duplicate. Click on different languages to view the code.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        return nums.Distinct().Count() < nums.Length;
    }
}

Video Solution

Watch the video walkthrough for Contains Duplicate

Algorithms:

Sorting

Data Structures:

ArrayHash Table

Companies:

Accenture |Airbnb |J.P. Morgan |Nagarro |