Contains Duplicate : Check if a value appears atleast twice

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.

Example:

Example 1:
Input: nums = [1, 2, 3, 1]
Output: true.
Explanation: 1 appeared two times in the input array.

Example 2: 
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: input array does not contain any duplicate number. 

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach 1: we can easily find any duplicate in the array just by using two nested loops. The first loop will pick integers one by one from the array and the second nested loop will check if there exists any duplicate or not.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
    
bool containsDuplicate(vector<int> nums) {
 
    for(int i = 0; i < nums.size(); i++) {
        for(int j = i + 1; j < nums.size(); j++) {
            if(nums[i] == nums[j]) {
                return true;
            }
        }
    }

    return false;
}
    
int main () {
	    
    vector<int> nums {1, 2, 3, 1};
	    
    bool res = containsDuplicate(nums);
	    
    // printing the result
    if(res== 1)
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
}

Output: true

Time Complexity:  O(N*N), Because we are traversing the whole array again and again for every integer.

Space Complexity: O(1), Since, we are not using any extra space.

Java Code

import java.io.*;
import java.lang.*;
 
class Solution{
    
    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;
    }
    
    public static void main (String[] args) {
	    
	    Solution sol = new Solution();
	    
	    int nums[]= {1, 2, 3, 1};
	    
	    boolean res = sol.containsDuplicate(nums);
	    
	    // printing the result
	    System.out.println(res);
    }
}

Output: true

Time Complexity:  O(N*N), Because we are traversing the whole array again and again for every integer.

Space Complexity: O(1), Since, we are not using any extra space.

Approach 2:  If we sort the array, then all the integers will arrange in order in addition of that duplicates will also be arranged in order example: [2, 1, 3, 4, 1, 5] after sorting will be  [1, 1, 2, 3, 4, 5].

Now the problem becomes very easy. We just only need to check for adjacent or neighboring elements whether they are the same or not.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
    
bool containsDuplicate(vector<int> nums) {
 
    sort(nums.begin(),nums.end());
    
    for(int index = 1; index < nums.size(); index++) {
        if(nums[index ] == nums[index - 1]) {
            return true;
        }
    }

    return false;
}
    
int main () {
	    
    vector<int> nums {1, 2, 3, 1};
    
    bool res = containsDuplicate(nums);
    
    // printing the result
    if(res== 1)
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
}

Output: true

Time Complexity:  O(N*logN), Sorting takes N*logN. Times where N is the length of the array

Space Complexity: O(1), Since we are not using any extra space. If we are not counting extra space taken by sorting.

Java Code

import java.io.*;
import java.lang.*;
import java.util.Arrays;
 
class Solution{
    
    public boolean containsDuplicate(int[] nums) {
 
        // sorting the array
        Arrays.sort(nums);
        
        for(int index = 1; index < nums.length; index++) {
            if(nums[index ] == nums[index - 1]) {
                return true;
            }
        }
 
        return false;
    }
    
    public static void main (String[] args) {
	    
	Solution sol= new Solution();
	    
	int nums[]= {1, 2, 3, 1};
	    
	boolean res = sol.containsDuplicate(nums);
	    
	System.out.println(res);
    }
}

Output: true

Time Complexity:  O(N*logN), Sorting takes N*logN. Times where N is the length of the array

Space Complexity: O(1), Since we are not using any extra space. If we are not counting extra space taken by sorting.

Approach 3: This problem can also be solved using extra space that is by using an additional data structure that will check if the element is seen before or not if seen then we can return true.

For this, we can use any data structure like HashSet, HashTable, or ArrayList as almost all data structures have a predefined function that checks if there already exists a given integer or not.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
    
bool containsDuplicate(vector<int> nums) {
 
    unordered_set<int> set;
    
    for(int i = 0; i<nums.size();i++){
        set.insert(nums[i]);
    }
    
    // if it contains duplicate then the size of 
    // set will not equal to the length of the array
    if(set.size() < nums.size())
        return true;
    
    return false;
}
    
int main () {
	    
    vector<int> nums {1, 2, 3, 1};
    
    bool res = containsDuplicate(nums);
    
    // printing the result
    if(res== 1)
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
}

Output: true

Time Complexity:  O(N), where N is the length of the array. As searching in unorder_set takes O(1)

Space Complexity: O(N), Where N is the number of elements stored in the set

Java Code

import java.io.*;
import java.lang.*;
import java.util.*;
 
class Solution{
    
    public boolean containsDuplicate(int[] nums) {
        
        HashSet<Integer> set = new HashSet<>();
        
        for(int i = 0; i<nums.length;i++){
            set.add(nums[i]);
        }
        
        // if it contains duplicate then the size of 
        // set will not equal to the length
        // of the array
        if(set.size() < nums.length)
            return true;
        
        return false;
    }
    
	public static void main (String[] args) {
	    
	    Solution sol= new Solution();
	    
	    int nums[]= {1, 2, 3, 1};
	    
	    boolean res = sol.containsDuplicate(nums);
	    
	    System.out.println(res);
	}
}

Output: true

Time Complexity:  O(N), where N is the length of the array. As searching hash_set takes O(1)

Space Complexity: O(N), Where N is the number of elements stored in the set

Special thanks to Ishu Prabhakar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article