Array - Dupe Scanner and runtime of algorithm

Question

I got two tasks to do:

1.) Create an algorithm so it detects if there are duplicates (= same numbers) in an array (the better its runtime is, the more points I get).

2.) Analyze the runtime of your algorithm.

Here is my code for the first task (I had to sort the array so the algorithm works faster / works at all. For this I used import instead of coding it myself.):

import java.util.Arrays;

public class Dupescanner
{
    public static void main(String[] args)
    {
        int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};
        Arrays.sort(A);
        System.out.println("Following numbers are duplicates:");
        for (int n = 1; n < A.length; n++)
        {
            if (A[n] == A[n - 1])
            {
                System.out.println(A[n]);
            }
        }
    }
}

Output:

Following numbers are duplicates:
1
2
8

Is that algorithm fine? I couldn't think of anything that is faster than this one. Or maybe I mis understood the task and it's enough if you just say: true - there is / are duplicates. false - not...

For the runtime analysis, I wasn't sure but I gave it a try as well:

int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};

costs 1

the for loop costs n and the if costs n too. Result would be n^2 + 1. Also I'm not sure if the array sort counts, I excluded it.

@mariusz2108 That has nothing to do with this question though. — Kayaman, Apr 26 '16 at 18:42
@tenepolis The array sort does count. You can't exclude it just because you didn't write the code for it. — Kayaman, Apr 26 '16 at 18:44
Why did you exclude the array sort? It should be included if it's used in duplicate detection. Also, you state the result would be `n^2 + 1`. This is incorrect as you iterate across all elements only once. — Clark Kent, Apr 26 '16 at 18:46

score 2 · Answer 1 · edited May 23 '17 at 12:14

Your algorithm is O(nlogn), the bottleneck in here is the sorting.

Your loop runs in linear time.

This is in fact the element distinctness problem.

It can be solved more efficiently (in terms of asymptotic complexity) only if you allow hashing and extra space, by populating a hash table (HashSet), and inserting all elements into it while iterating, and if you find a dupe while iterating - print it.

int[] array = {1, 2, 3, 4, 5, 1, 2, 8, 8};
Set<Integer> set = new HashSet<>();
System.out.println("Following numbers are duplicates:");
for (int e : array) { 
  if (!set.add(e)) System.out.println("" + e);
}

This thread discusses lower bounds for the problem.

Array - Dupe Scanner and runtime of algorithm

1 Answers1