Check if array contains duplicates
Program for checking duplicate in an array – Duplicate Integer Problem
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
Example 1
Input: nums = [1, 2, 3, 3]
Output: true
Output: true
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
Output: false
Program for checking duplicate in an array - Duplicate Integer Solution
Recommendation – You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.
There are mainly 4 approach to solve this problem –
- Brute Force Method
- Sorting Method
- Hash Set
- Hash Set Length
Hints for solving problems
Hint 1
A brute force solution would be to check every element against every other element in the array. This would be an O(n^2) solution. Can you think of a better way?
Hint 2
Is there a way to check if an element is a duplicate without comparing it to every other element? Maybe there's a data structure that is useful here.
Hint 3
We can use a hash data structure like a hash set or hash map to store elements we've already seen. This will allow us to check if an element is a duplicate in constant time.
1. Brute Force Method
This method iterate through each element and check it against every other element to find duplicates or fulfill specific conditions. This is usually the simplest but least efficient method.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool hasDuplicate(vector& 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;
}
};
Java
public class Solution {
public boolean hasDuplicate(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;
}
}
Python
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
hasDuplicate(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) {
return true;
}
}
}
return false;
}
}
2. Sorting Method
This method sort the elements first, then compare adjacent elements. This reduces the problem to a more manageable sequence comparison.
- Time complexity: O(nlogn)
- Space complexity: O(1) or O(n) depending on the sorting algorithm.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool hasDuplicate(vector& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
};
Java
public class Solution {
public boolean hasDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
}
Python
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
hasDuplicate(nums) {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) {
return true;
}
}
return false;
}
}
3. Hash Set Method
This method use a hash set to store elements as you iterate. This allows you to check for duplicates or existence in constant time.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool hasDuplicate(vector& nums) {
unordered_set seen;
for (int num : nums) {
if (seen.count(num)) {
return true;
}
seen.insert(num);
}
return false;
}
};
Java
public class Solution {
public boolean hasDuplicate(int[] nums) {
Set seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
return true;
}
seen.add(num);
}
return false;
}
}
Python
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
hasDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}
}
4. Hash Set Length Method
This method add elements to a hash set, then check the set’s length against the list length. If the lengths differ, duplicates exist.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool hasDuplicate(vector& nums) {
return unordered_set(nums.begin(), nums.end()).size() < nums.size();
}
};
Java
public class Solution {
public boolean hasDuplicate(int[] nums) {
return Arrays.stream(nums).distinct().count() < nums.length;
}
}
Python
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {boolean}
*/
hasDuplicate(nums) {
return new Set(nums).size < nums.length;
}
}
