Practice › Hashing & Two Pointers
Contains Duplicate
Easy · Hashing & Two Pointers · Asked at Amazon, Microsoft, Apple, TCS, Infosys
Print YES if any value appears at least twice in the array, otherwise NO.
Input
First line: n. Second line: n integers.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
Example 1
Input
4 1 2 3 1
Output
YES
Example 2
Input
4 1 2 3 4
Output
NO
Hints
- Comparing every pair is O(n²).
- Insert values into a hash set; if a value is already there, you found a duplicate.
Approach
Walk the array with a hash set. If the current value is already in the set, answer YES. Otherwise insert it. Reaching the end means every value is unique. Sorting and checking neighbours is the O(1)-extra-space alternative.
Complexity: O(n) average time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<long long> seen;
bool dup = false;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (!seen.insert(x).second) dup = true;
}
cout << (dup ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1 : n + 1]]
print("YES" if len(set(a)) < n else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> seen = new HashSet<>();
boolean dup = false;
for (int i = 0; i < n; i++)
if (!seen.add(sc.nextLong())) dup = true;
System.out.println(dup ? "YES" : "NO");
}
}