Contains Duplicate

Array, Hash Table

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

Solutions

The key insight to solve this problem is to realize that we need to keep track of the elements we have already encountered as we iterate through the array. If we encounter an element that we have seen before, we can immediately return true because we have found a duplicate. If we finish iterating through the array without finding any duplicates, we return false.

Approach – Brute Force Technique

The brute force approach involves checking each pair of elements in the array. If any pair is equal, return true. If no pairs are equal, return false.

Steps

1. Iterate over the array: The outer loop (index i from 0 to nums.Length - 1) iterates over each element in the array.

2. Check for duplicates: For each element nums[i], the inner loop (index j from i + 1 to nums.Length - 1) checks all the following elements in the array to see if they are equal to nums[i].

3. Return true if a duplicate is found: If nums[i] is equal to nums[j], it means we have found a duplicate, so we immediately return true.

4. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

public class Solution {
    public bool 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

• Time Complexity: O(n^2)

• Auxiliary Space: O(1)

Approach – Sorting Technique

This approach involves sorting the array first, then checking each pair of adjacent elements. If any pair is equal, return true. If no pairs are equal, return false.

Steps

1. Sort the array: The Array.Sort(nums) function sorts the array in ascending order. This operation has a time complexity of O(n log n), where n is the number of elements in the array.

2. Iterate over the array: The loop for (int i = 0; i < nums.Length - 1; i++) iterates over each element in the array, except the last one. This is because we're comparing each element with its next neighbor, and the last element doesn't have a next neighbor.

3. Check for duplicates: Inside the loop, the if (nums[i] == nums[i + 1]) statement checks if the current element is equal to the next element. Because the array is sorted, any duplicate elements will be adjacent to each other. So, if the current element is equal to the next element, it means we have found a duplicate, and we immediately return true.

4. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

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

Complexity

• Time Complexity: O(n log n)

• Auxiliary Space: O(1)

Approach – Hash Table Technique

We can use a data structure like a HashSet that allows for efficient insertions and lookups. We iterate through the array and insert each element into the HashSet. If an element is already in the HashSet, we return true. If we finish iterating through the array without finding any duplicates in the HashSet, we return false.

Steps

1. Initialize: Create a new HashSet set. A HashSet is a collection of unique elements.

2. Iterate over the array: The foreach loop iterates over each element num in the array nums.

3. Check for duplicates: Inside the loop, the if (set.Contains(num)) statement checks if num is already in the HashSet set. If it is, it means we have found a duplicate, so we immediately return true.

4. Add element to the set: If num is not in the set, we add it to the set using set.Add(num). This step is done for each element in the array.

5. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> set = new HashSet<int>();
        foreach (int num in nums) {
            if (set.Contains(num)) {
                return true;
            }
            set.Add(num);
        }
        return false;
    }
}

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(n)