Home
Algorithms to Check if Array Contains Duplicate Elements
Tags:, , , , , , ,

Algorithms to Check if Array Contains Duplicate Elements

January 16, 2020 2 Comments algorithms, c / c++, java, javascript, python

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
Example 2:

Input: [1,2,3,4]
Output: false
Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Bruteforce Algorithm to Check If Array Contains Duplicates

The bruteforce algorithm: We can iterate over all pairs of numbers, then compare for equality. This takes O(N^2) quadric time, at the cost of a constant space.

Python:

1
2
3
4
5
6
7

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i] == nums[j]:
                    return True
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[i] == nums[j]:
                    return True
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 1; i < nums.length; ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
} 
class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 1; i < nums.length; ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    for (let i = 0; i < nums.length; ++ i) {
        for (let j = 0; j < i; ++ j) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    for (let i = 0; i < nums.length; ++ i) {
        for (let j = 0; j < i; ++ j) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
};

Check If Array Contains Duplicate After Sorting

If we sort the array (which will require O(N LogN)), then we can do a linear scan to check the two consecutive elements to find out if there are duplicates. The overall time complexity is improved to O(N LogN) and we are still using the O(1) constant space.

Python:

1
2
3
4
5
6
7

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
} 
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(begin(nums), end(nums));
        for (int i = 1; i < nums.size(); ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(begin(nums), end(nums));
        for (int i = 1; i < nums.size(); ++ i) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for (let i = 1; i < nums.length; ++ i) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for (let i = 1; i < nums.length; ++ i) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }
    return false;
};

Use Hash Set to Check the Duplicates

Further optimisation can be done via using a Hash Set. The complexity will be O(N) as we only need to conduct a linear scan. However, the space requirement is O(N) as we are using a Hash Set that complexity grows linear with the data set.

Python:

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        data = set()
        for i in nums:
            if i in data:
                return True
            data.add(i)
        return False
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        data = set()
        for i in nums:
            if i in data:
                return True
            data.add(i)
        return False

Java:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (Integer x: nums) {
            if (set.contains(x)) {
                return true;
            }
            set.add(x);
        }
        return false;
    }
}
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (Integer x: nums) {
            if (set.contains(x)) {
                return true;
            }
            set.add(x);
        }
        return false;
    }
}

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (cache.count(nums[i])) {
                return true;
            }
            cache.insert(nums[i]);
        }
        return false;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (cache.count(nums[i])) {
                return true;
            }
            cache.insert(nums[i]);
        }
        return false;
    }
};

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let data = new Set();
    for (let x of nums) {
        if (data.has(x)) {
            return true;
        }
        data.add(x);
    }
    return false;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let data = new Set();
    for (let x of nums) {
        if (data.has(x)) {
            return true;
        }
        data.add(x);
    }
    return false;
};

This problem is the foundamental (basics) for Computer Science Interviews. In this post, we have listed 3 solutions that are implemented in four languages: C++, Java, Python and Javascript.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
758 words
Last Post: Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree
Next Post: Algorithm to Compute the Fraction to Recurring Decimal of the Two Integer Division

The Permanent URL is: Algorithms to Check if Array Contains Duplicate Elements

Related posts:

  1. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  2. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  3. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  4. The C++ Function using STL to Check Duplicate Elements/Characters in Array/Vector/String Let’s say we want to implement a C++ function based on STL containers to check...
  5. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  6. How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)? Given a binary search tree and the lowest and highest boundaries as L and R,...
  7. A Simple Function to Perform Integer/Float Arithmetic Calculation via AWK The inbuilt BASH does not support floating point arithmetic calculations but we can easily declare...
  8. Depth First Search Algorithm to Check If Two Expression Trees are Equivalent A binary expression tree is a kind of binary tree used to represent arithmetic expressions....

2 Comments

  1. Rajesh

    you forget to write “static” in Java code.

    Reply
    • ACMer

      well, depends on the case. “static” methods are only recommended in helper static class because they don’t obey the OOP rules/principles.

      Reply

Leave a Reply