11
\$\begingroup\$

My code returns the correct answer the first duplicate is 3 (represented as int f) . I am struggling finding a more efficient way to find the first duplicate?

My constraints are \$ 1 ≤ a.length ≤ 10^5, 1 ≤ a[i] ≤ a.length \$ .

class Program
{
  static void Main(string[] args)
  {
    int[] a = {2, 3, 3, 1, 5, 2};

    int f = FirstDuplicate(a);

    Console.ReadLine();
   }
public static int FirstDuplicate(int[] a)
{

    int[] answer = new int[2];
    answer[0] = -1;
    answer[1] = a.Length;
    for (int i = 0; i < a.Length - 1; i++)
        for (int j = i; j < a.Length; j++)
            if (a[i] == a[j] && i != j)
            {
                if (i < answer[1])
                {
                    answer[0] = a[i];
                    answer[1] = j;
                    break;

                }
            }

    return answer[0];
  }
}
\$\endgroup\$
  • \$\begingroup\$ If you aren't prevented from using a HashSet, I would think it would yield better performance without the need for the inner loop. \$\endgroup\$ – Rick Davin May 3 '18 at 22:10
  • \$\begingroup\$ Minor note. Since the constraint is all numbers must be between 1 and the array length, a value of 0 could also be used to denote no duplicates were found. \$\endgroup\$ – Rick Davin May 3 '18 at 23:31
  • \$\begingroup\$ Even after updating the array, 3 would not be the first duplicate. Wouldn't 2 be the correct answer? \$\endgroup\$ – Rick Davin May 4 '18 at 12:45
  • \$\begingroup\$ I'm voting to close this question as off-topic because the code not only does not compile but also returns the last and not the first duplicate so it's not really working. \$\endgroup\$ – t3chb0t May 4 '18 at 12:48
  • \$\begingroup\$ 3 is the first duplicate because 3 is the first one to have the 2nd number appear in the array. I hope this clarifies. \$\endgroup\$ – Andrew Mattick May 4 '18 at 12:50
14
\$\begingroup\$

For a small array or list of a handful of items, this should be very fast. But is it efficient as you would scale out? No.

Before getting on to a better way to achieve the it for a larger number of items, let's look at your current code. You have some checks that aren't needed.

if (a[i] == a[j] && i != j)

The check of i != j is not needed if you were to simply initialize j to be i + 1 as in:

for (int j = i + 1; j < a.Length; j++)
    if (a[i] == a[j])

The check of if (i < answer[1]) is totally unnecessary. In fact, answer as an array is not needed at all as you do not really do anything meaningful with answer[1].

But having 2 loops is not efficient as the input array could be larger. As mentioned in a comment, the use of a HashSet could be used. I am changing a few things.

  • The method signature is now IEnumerable<int> to allow for arrays, lists, or any collection of integers.
  • I use a HashSet to keep track of items I have already encountered.
  • The return type is a Nullable<int>, also written as int?, so that if there are no duplicates found a null is returned.

The resulting method also looks cleaner. Someone looking at this understands more readily what the code is trying to achieve:

public static int? FirstDuplicate(IEnumerable<int> items)
{

    HashSet<int> set = new HashSet<int>();
    foreach (int item in items)
    {
        if (set.Contains(item))
        {
            return item;
        }
        set.Add(item);
    }
    return null;
} 

As shown in @Denis's answer, and echoed by @Corak, is the method could be made slightly faster and shorter by reducing the logic inside the foreach loop:

if (!set.Add(item))
{
    return item;
}

While this again is slightly faster, slighter cleaner, and recommended in practice, it still lags well behind @vnp 's array solution.

UPDATED Worst Case Array

I composed a worst case array to test of 100000 items where the very last item is the first duplicate of the 2nd to last item. Your code and mine returned the correct value.

public static int[] WorstCaseArray
{
    get
    {
        int[] items = new int[(int)Math.Pow(10, 5)];
        for (int i = 0; i < items.Length; i++)
        {
            items[i] = i + 1;
        }
        items[items.Length - 1] = items[items.Length - 2];  
        return items;
    }
}

UPDATE #2 - Worst Case

Obviously we should be working with the largest array allowed.

As @PeterCordes states in a comment to @vnp's answer, the list should be randomized.

As @Denis states, the worst case for a HashSet would be if the only duplicate was the first and last item. An extremely close second would be if the last and 2nd to last item were the only duplicate. Note this second worst case for HashSet would be the worst case for @vnp's array solution, so I will use it as my worst case.

public static int[] WorstCaseArray
{
    get
    {
        // Worst case is largest allowed array ...
        int max = (int)Math.Pow(10, 5);
        int[] items = new int[max];
        for (int i = 0; i < items.Length; i++)
        {
            items[i] = i + 1;
        }
        // ... that is randomly shuffled ...
        Shuffle(items);
        // ... with the only duplicate being the last item matching the 2nd to last!
        items[items.Length - 1] = items[items.Length - 2];   
        return items;
    }
}

private static Random random = new Random();
public static void Shuffle(int[] items)
{
    //Fisher-Yates method to shuffle
    for (int i = items.Length - 1; i > 0; --i)
    {
        int randomIndex = random.Next(i + 1);
        int temp = items[i];
        items[i] = items[randomIndex];
        items[randomIndex] = temp;
    }
}

UPDATED Worst Case Timings:

  • Yours: 14.5105877 seconds
  • Mine : 00.0065640 seconds
  • vnp's: 00.0012733 seconds

Tiny array with many duplicates

However, as I said for only a handful of items yours is quite fast. The problem is - it produces the wrong answer! Using this array:

int[] array =  new[] { 1, 2, 3, 4, 5, 6, 3, 4, 5, 6 };

Where the expected answer would be 3, yours returns 6.

  • Yours: took 0.0006141 seconds but returned 6 (wrong)
  • Mine : took 0.0006162 seconds
  • vnp's : 0.0003843 seconds

Large, Random Array with No Duplicates

To round out the answer, let's look at the largest allowed array, randomized, but without any duplicates. Using the shuffle routine from above:

public static int[] NoDuplicates()
{
    int[] items = Enumerable.Range(1, (int)Math.Pow(10, 5)).ToArray();
    Shuffle(items);
    return items;
}

Timings:

  • Yours: 15.1978462 seconds
  • Mine : 00.0055364 seconds
  • vnp's : 00.0014876 seconds

BEST ANSWER

Also, since you have tagged this question with [time-limit-exceeded], vnp's answer is not just clever, but also the fastest in all tested scendarios, which makes it the best answer (regarding performance).

\$\endgroup\$
  • \$\begingroup\$ It's not wrong result, quote from OP: 1 ≤ a.length ≤ 10^5, 1 ≤ a[i] ≤ a.length. A very weird condition if you ask me but.. \$\endgroup\$ – Denis May 3 '18 at 23:09
  • 2
    \$\begingroup\$ @Denis I don't think the condition is weird. It is actually a key to the correct solution. Hint: HashMap is an overkill. \$\endgroup\$ – vnp May 3 '18 at 23:14
  • 1
    \$\begingroup\$ @Denis 1 ≤ a.length ≤ 10^5 means the array length must be between 1 and 100K (I use 10K as my worst). 1 ≤ a[i] ≤ a.length means each number in the list must range between 1 and the array length inclusively. For my array of { 1, 2, 3, 4, 5, 6, 3, 4, 5, 6 } the first duplicate encountered is 3. While 6 is a duplicate, it's not the first so it is the wrong result. \$\endgroup\$ – Rick Davin May 3 '18 at 23:24
  • 1
    \$\begingroup\$ @RickDavin You're right, I interpreted it wrong. \$\endgroup\$ – Denis May 3 '18 at 23:25
  • 1
    \$\begingroup\$ @RickDavin small note I think you should return -1 instead of Nullable<int>, at least that's how OP's code works. \$\endgroup\$ – Denis May 3 '18 at 23:30
13
\$\begingroup\$

Elaborating on my rather cryptic comment.

There is no better hash for an integer than an integer itself, which of course degenerates the HashMap into an array. The condition

1 <= a_i <= a.length

puts the bound to the array size.

The key observation is that given a helper array h of the same size as f, any element of f, say i, can be sent into the ith slot of h. If the slot is already occupied by i, we have a duplicate. In pseudocode

    int h[f.length]{0}
    for item in f:
        if h[i] == i:
            return i
        h[i] = i

Note that if we are allowed to mutate f, the algorithm can be adapted to work in-place.

UPDATED C# IMPLEMENTATION (added by Rick Davin)

public static int FirstDuplicateFast(int[] source)
{
    //Constraint: 1 <= source[i] <= source.Length
    int[] map = new int[source.Length];
    foreach (int value in source)
    {
        if (map[value - 1] != 0)
        {
            return value;
        }
        map[value - 1] = value;
    }
    return -1;
}

As noted in comments, this is 8-10X faster than a HashSet.

\$\endgroup\$
  • 1
    \$\begingroup\$ These are intriguing observations that work for special cases. I am curious as to what your approach would be if the array could contain negative values or even 0? \$\endgroup\$ – Rick Davin May 3 '18 at 23:41
  • 3
    \$\begingroup\$ This doesn't need to be an int array (unlike CountingSort); a boolean array or bitmap of seen / not-seen would be more sensible (smaller cache footprint = faster, down to 1 byte elements then it's a tradeoff between cache hits vs. ALU and RMW cost instead of writes independent of the reads). The identity function is the simplest integer -> bucket function, @RickDavin, but if your range includes negative numbers or is small but far from zero (e.g. [10000 .. 10100], adding / subtracting a constant works. e.g. seen[ i+1000 ] = true \$\endgroup\$ – Peter Cordes May 4 '18 at 1:13
  • 2
    \$\begingroup\$ This is about 8 - 10 times faster than a HashSet. \$\endgroup\$ – Rick Davin May 4 '18 at 1:17
  • 2
    \$\begingroup\$ @hellyale - How it works? Imagine a very simple case: { 1, 1 }. We know the length of the array is 2 and through the conditions, we know that all the values in the array must be between 1 and that length. So now we create another array of the same length. By default all the values of that second array are set to 0. Now we go through all the items of the first array and for each item we take the value of the item and use it as the index in the second array. If the second array has nothing yet set and that exact index, we set it to something. Here, simply the value again. \$\endgroup\$ – Corak May 4 '18 at 15:41
  • 1
    \$\begingroup\$ If we see, that the second array has something (other than zero) set at that exact index, we know we "visited" that index and thus that value already, and so we must have encountered a duplicate value. -- Now why it's faster? I don't know. Array access via index is very very fast. Starting address + (index * sizeof(itemtype)); done. Sets should work "similar", but with some overhead, probably for bucket calculation, possible resizing and whatnot. \$\endgroup\$ – Corak May 4 '18 at 15:41
5
\$\begingroup\$

Performance is not the only important thing about a piece of code. Depending on the nature of the problem you might also need to consider - readability, maintainability and flexibility. I will present you couple of solutions focusing on those different aspects.

LINQ

You could use LINQ and write it like this:

private static int FirstDuplicate(IEnumerable<int> source)
{
    foreach (var item in source)
    {
        if (source.Count(t => t == item) > 1)
        {
            return item;
        }
    }
    return -1;
}

If you could've returned 0 instead of -1 in case no duplicates are found, it could've been written like this:

private static int FirstDuplicate(IEnumerable<int> source)
{
    return source.FirstOrDefault(item => source.Count(t => t == item) > 1);
}

LINQ is usually quite readable and most C# programmers are familiar with it's syntax so it's a lot easier to just give it a glance and know what's up.

HashSet<>

The HashSet<T> is very handy when working with unique numbers as it can contain only distinct numbers. It's bool Add(T item) method will allow us to quickly check if a value was already added:

private static int FirstDuplicate(IEnumerable<int> source)
{
    var distinctItems = new HashSet<int>();
    foreach (var item in source)
    {
        if (!distinctItems.Add(item))
        {
            return item;
        }
    }
    return -1;
}

Again, if you could've returned 0 instead of -1 in case no duplicates are found, it could've been written like this:

private static int FirstDuplicate<int>(IEnumerable<int> source)
{
    var distinctItems = new HashSet<int>();
    return source.FirstOrDefault(item => !distinctItems.Add(item));
}

Your code

It's often times easy to overthink a simple problem, such is your case, you've over-complicated a simple task. You should think through the problem, before writing code. Some people prefer to write first and than improve afterwards, this also works, but it's always good to think a bit about it before-hand, especially when you're beginner you might often find yourself tunnel-visioned in a specific way of solving the problem once you're done with it, you could avoid that by thinking before-hand as you wont be so attached to specific ideas.

Missing for loop indentation is also reducing the readability of your function.

\$\endgroup\$
  • 2
    \$\begingroup\$ It's a dubious claim that the for loops are for speed. That is true for a small collection, but starts to be slower as more items are added. \$\endgroup\$ – Rick Davin May 3 '18 at 23:15
  • 3
    \$\begingroup\$ @RickDavin not necessarily the quantity of the items, but rather their position. And yes it would affect it more or less it's O(n^2) algorithm in the worst case. HashSet<> would suffer in case you have the first and last element as duplicates. But yes I agree, there are cases where HashSet<> has the upper-hand \$\endgroup\$ – Denis May 3 '18 at 23:22
  • \$\begingroup\$ Thank you for your help. Unfortunately, and it's probably my fault as I was vague I need the first duplicate so if the set is {2,3,4,3,2}. I need it to return 3 because the 2nd three is the first duplicate. If I'm not mistaken your loop will return a 2 because the first 2 appears first. \$\endgroup\$ – Andrew Mattick May 4 '18 at 16:24
  • \$\begingroup\$ @AndrewMattick you're right I've removed it from the answer. That makes hashset even more lucrative solution. Or vnp's way of doing it. \$\endgroup\$ – Denis May 4 '18 at 17:02
-2
\$\begingroup\$

Your code it O(n^2). This can be done in O(n).

int j = i can be int j = i + 1 and you can skip the if (a[i] == a[j] && i != j)

Looks like you are returning the last duplicate - not the first.

Array lookup is very fast but you should capture the value in the outer loop. See DoubleLoop below.

Array based is much faster than HashSet but if you did not have the condition 1≤a[i]≤a.length you could not use array. In the latest version of .NET I think you can pre-allocate the HashSet capacity but Array would probably still be faster.

HashSet     time    434  value 1334
Array       time     46  value 1334
Double loop time 15,321  value 1334 

.

public static void TestDup()
{
    Random rand = new Random();
    int max = 2000;
    int[] array = new int[max];
    for(int i = 0; i < max; i++)
    {
        //array[i] = rand.Next(1, max);
        array[i] = i + 1;
    }
    //array[max - 1] = max - 1; //not fair to double loop 
    array[max / 3] = array[max * 2 / 3];
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int? dup = null;
    for (int i = 0; i < max; i++)
    {
        dup = FindFirstDupicateHashSet(array);
    }
    sw.Stop();
    Debug.WriteLine($"HashSet time {sw.ElapsedMilliseconds.ToString("N0")}  value {dup}");
    sw.Restart();
    dup = null;
    for (int i = 0; i < max; i++)
    {
        dup = FindFirstDupicateArray(array);
    }
    sw.Stop();
    Debug.WriteLine($"Array time {sw.ElapsedMilliseconds.ToString("N0")}  value {dup}");
    sw.Restart();
    dup = null;
    for (int i = 0; i < max; i++)
    {
        dup = FindFirstDupicateDoubleLoop(array);
    }
    sw.Stop();
    Debug.WriteLine($"Double loop time {sw.ElapsedMilliseconds.ToString("N0")}  value {dup}");
    Debug.WriteLine("done");
}
public static int? FindFirstDupicateHashSet(int[] array)
{
    int len = array.Length;
    HashSet<int> hs = new HashSet<int>();
    foreach(int i in array)
    {
        if(!hs.Add(i))
        {
            return i;
        }
    }
    return null;
}
public static int? FindFirstDupicateArray(int[] array)
{
    int[] compute = new int[array.Length];
    foreach(int i in array)
    {
        //Debug.WriteLine($"{i} {compute[i-1]}");
        if(compute[i - 1] > 0)  // 0 is default value
        {
            return i;
        }
        compute[i - 1] = 1;
    }
    return null;
}
public static int? FindFirstDupicateDoubleLoop(int[] array)
{
    int len = array.Length;
    int iVal;
    for (int i = 0; i < len - 1; i++)
    {
        iVal = array[i];
        for (int j = i + 1; j < len; j++)
        {
            if (iVal == array[j])
            {
                return iVal;
            }
        }
    }
    return null;
}
\$\endgroup\$
  • \$\begingroup\$ I am not getting the down votes. It is the only answer with test for timing. People can test in their environment. \$\endgroup\$ – paparazzo May 4 '18 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.