Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

4
1 2 3 1

Output

YES

Example 2

Input

4
1 2 3 4

Output

NO

Hints

  1. Comparing every pair is O(n²).
  2. 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");
    }
}

Solve Contains Duplicate online · All practice problems