Find the first duplicated element

Thomas A. Anderson 08/25/2017. 30 answers, 2.717 views
code-golf array-manipulation

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, your program / function may result in undefined behaviour.

Example:

For a = [2, 3, 3, 1, 5, 2], the output should befirstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should befirstDuplicate(a) = -1.

This is , so shortest answer in bytes wins.

BONUS: Can you solve it in O(n) time complexity and O(1) additional space complexity?

5 Comments
1 beaker 07/30/2017
@ThomasA.Anderson You should search for duplicates (this question has probably already been answered) before asking on SO. If you don't find any, be sure to read stackoverflow.com/help/how-to-ask for help on asking good questions.
1 Stephen 07/30/2017
I made this code-golf, since you didn't have a winning criterion. If you would like to make the time complexity part of the challenge instead of a bonus, see restricted-complexity.
3 musicman523 07/30/2017
We typically have pretty lax I/O on our challenges; is it okay to throw an exception instead of returning -1?
1 Stephen 07/30/2017
@musicman523 first example has no 4, so I'd assume no
9 Luis Mendo 07/30/2017
More test cases please

30 Answers


musicman523 08/01/2017.

Python 2, 34 bytes

O(n2) time, O(n) space

Saved 3 bytes thanks to @vaultah, and 3 more from @xnor!

lambda l:l[map(l.remove,set(l))<0]

Try it online!

5 comments
1 vaultah 07/30/2017
lambda l:map(l.remove,set(l))and l[0] is shorter.
1 xnor 07/31/2017
It looks like lambda l:l[map(l.remove,set(l))<0] works, even though the order of evaluation is weird.
Chris_Rands 07/31/2017
This doesn't return -1 when no duplicates are found without the 'footer code', does that code not count towards the bytes? I'm new to code golf, sorry if it's a basic question!
LiefdeWen 07/31/2017
@Chris_Rands Beneath the question musicman did ask if exception is okay instead of -1 and OP said its okay and musicman's answer throws exception.
Thoth19 07/31/2017
That took me a while to figure out. Well played. Getting the 0th element of l using the conditional after modifying it is really clever.

Arnauld 07/30/2017.

JavaScript (ES6), 47 36 31 25 bytes

Saved 6 bytes thanks to ThePirateBay

Returns undefined if no solution exists.

Time complexity: O(n) :-)
Space complexity: O(n) :-(

a=>a.find(c=>!(a[-c]^=1))

How?

We keep track of already encountered values by saving them as new properties of the original array a by using negative numbers. This way, they can't possibly interfere with the original entries.

Demo

let f =

a=>a.find(c=>!(a[-c]^=1))

console.log(f([2, 3, 3, 1, 5, 2]))
console.log(f([2, 4, 3, 5, 1]))
console.log(f([1, 2, 3, 4, 1]))

3 comments
ThePirateBay 07/30/2017
25 bytes: a=>a.find(c=>!(a[-c]^=1))
Arnauld 07/30/2017
@ThePirateBay Oh, of course. Thanks!
tsh 08/01/2017
Just notice that Objects in JavaScript may not be implemented as hash table. Time complexity of accessing keys of some object may not be O(1).

JungHwan Min 07/30/2017.

Mathematica, 24 bytes

#/.{h=___,a_,h,a_,h}:>a&

Mathematica's pattern matching capability is so cool!

Returns the original List for invalid input.

Explanation

#/.

In the input, replace...

{h=___,a_,h,a_,h}

A List with a duplicate element, with 0 or more elements before, between, and after the duplicates...

... :>a

With the duplicate element.


Dennis 07/31/2017.

Jelly, 5 bytes

Ṛœ-QṪ

Try it online!

How it works

Ṛœ-QṪ  Main link. Argument: A (array)

Ṛ      Yield A, reversed.
   Q   Unique; yield A, deduplicated.
 œ-    Perform multiset subtraction.
       This removes the rightmost occurrence of each unique element from reversed
       A, which corresponds to the leftmost occurrence in A.
    Ṫ  Take; take the rightmost remaining element, i.e., the first duplicate of A.
2 comments
Erik the Outgolfer 07/31/2017
œ- removes the rightmost occurrences? TIL
Erik the Outgolfer 07/31/2017
This doesn't seem to return -1 for no duplicates. Throwing an exception is okay as per OP but I'm not sure if 0 is even though it's not in the range.

miles 07/30/2017.

Jelly, 6 bytes

xŒQ¬$Ḣ

Try it online!

Returns the first duplicate, or 0 if there is no duplicate.

Explanation

xŒQ¬$Ḣ  Input: array M
    $   Operate on M
 ŒQ       Distinct sieve - Returns a boolean mask where an index is truthy
          for the first occurrence of an element
   ¬      Logical NOT
x       Copy each value in M that many times
     Ḣ  Head
2 comments
Erik the Outgolfer 07/31/2017
It's golfier to use indexing like this: ŒQi0ị.
miles 07/31/2017
@EriktheOutgolfer If there are no duplicates, i0 would return 0, where would index and return the last value of the input instead of 0.

ETHproductions 07/30/2017.

Japt, 7 bytes

æ@bX ¦Y

Test it online!

Explanation

 æ@   bX ¦ Y
UæXY{UbX !=Y}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     UbX         the first index of X in U
         !=Y     is not equal to Y.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression

Alternatively:

æ@¯Y øX

Test it online!

Explanation

 æ@   ¯ Y øX
UæXY{Us0Y øX}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     Us0Y        the first Y items of U (literally U.slice(0, Y))
          øX     contains X.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression

isaacg 07/31/2017.

Pyth, 5 bytes

h.-Q{

Test suite

Remove from Q the first appearance of every element in Q, then return the first element.

2 comments
Mr. Xcoder 07/31/2017
@LuisMendo Ok thanks. Sorry for creating confusion, I should learn to read...
Luis Mendo 07/31/2017
@Mr.Xcoder No, it's the OP's fault. That information should be in the challenge text, but just in a comment

Lynn 08/01/2017.

Haskell, 35 bytes

f s(h:t)|h`elem`s=h|1<2=f(h:s)t
f[]

Try it online! Crashes if no duplicate is found.


Zacharý 08/04/2017.

Dyalog APL, 27 24 20 19 13 12 11 bytes

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Now modified to not depend on v16! Try it online!

How? (With input N)

  • ⊢⊃⍨... - N at this index:
    • ⍴↑∪ - N with duplicates removed, right-padded with 0 to fit N
    • ⊢= - Element-wise equality with N
    • 0⍳⍨ - Index of the first 0. `
5 comments
Uriel 07/30/2017
nevermind, I misread the question. not enough test cases though...
miles 07/30/2017
Sorry for misleading you, I also misread the question.
Adám 07/31/2017
Looks like 36 bytes to me.
Zacharý 07/31/2017
Oh god, iota underbar isn't in ⎕AV, is it?
Adám 08/04/2017
@Zacharý Right, Classic translates it to ⎕U2378  when loading. Try it online!

Adám 08/04/2017.

APL (Dyalog), 20 bytes

⊃n/⍨(,≢∪)¨,\n←⎕,2⍴¯1

Try it online!

2⍴¯1 negative one reshaped into a length-two list

⎕, get input (mnemonic: console box) and prepend to that

n← store that in n

,\ prefixes of n (lit. cumulative concatenation)

( apply the following tacit function to each prefix

, [is] the ravel (just ensures that the prefix is a list)

 different from

 the unique elements[?] (i.e. is does the prefix have duplicates?)

n/⍨ use that to filter n (removes all elements until the first for which a duplicate was found)

 pick the first element from that

3 comments
Zacharý 08/03/2017
Wow, you got beat three times. Still, +1. And can you add an explanation of how this works?
Adám 08/04/2017
@Zacharý Apparently I just needed to get the ball rolling. Here you go.
Adám 08/04/2017
@Zacharý Eventually, I managed to beat them all.

Neil 08/04/2017.

Retina, 26 24 bytes

1!`\b(\d+)\b(?<=\b\1 .*)

Try it online! Explanation: \b(\d+)\b matches each number in turn, and then the lookbehind looks to see whether the number is a duplicate; if it is the 1st match is ! output, rather than the count of matches. Unfortunately putting the lookbehind first doesn't seem to work, otherwise it would save several bytes. Edit: Added 7 bytes to comply with the -1 return value on no match. Saved 2 bytes thanks to @MartinEnder.

4 comments
2 FryAmTheEggman 07/31/2017
For the record, the lookaround won't backtrack. This prevents this from working if you try to put it before. I've made this mistake many times, and Martin always corrects me.
Value Ink 08/04/2017
I got 30 bytes by using a lookahead instead of a lookbehind. Also, the rules now say you don't need to return -1.
Neil 08/04/2017
@ValueInk But the correct answer for that test case is 3...
Value Ink 08/04/2017
OH. I misread the challenge, whoops

Luis Mendo 07/30/2017.

MATL, 8 bytes

&=Rsqf1)

Gives an error (without output) if no duplicate exists.

Try at MATL Online!

Explanation

&=   % Implict input. Matrix of all pairwise equality comparisons
R    % Keep the upper triangular part (i.e. set lower part to false)
s    % Sum of each column
q    % Subtract 1
f    % Indices of nonzero values
1)   % Get first. Gives an error is there is none. Implictly display

Leaky Nun 07/31/2017.

Python 3, 94 92 bytes

O(n) time and O(1) extra memory.

def f(a):
 r=-1
 for i in range(len(a)):t=abs(a[i])-1;r=[r,i+1][a[t]<0>r];a[t]*=-1
 return r

Try it online!

Source of the algorithm.

Explanation

The basic idea of the algorithm is to run through each element from left to right, keep track of the numbers that have appeared, and returning the number upon reaching a number that has already appeared, and return -1 after traversing each element.

However, it uses a clever way to store the numbers that have appeared without using extra memory: to store them as the sign of the element indexed by the number. For example, I can represent the fact that 2 and 3 has already appeared by having a[2] and a[3] negative, if the array is 1-indexed.

5 comments
Downgoat 07/31/2017
What would this do for i where a[i] > n?
Leaky Nun 07/31/2017
@Downgoat read the question again.
Downgoat 07/31/2017
The question says 1 to a.length but for a[i]= a.length wouldn't this go out of bounds?
Leaky Nun 07/31/2017
@Downgoat t=abs(a[i])-1=a.length-1

RoryT 07/31/2017.

R, 34 bytes

c((x=scan())[duplicated(x)],-1)[1]

Cut a few characters off the answer from @djhurio, don't have enough reputation to comment though.

1 comments
Giuseppe 07/31/2017
oh...I didn't see this answer; this is good for the prior spec when missing values required -1 but with the new spec, I managed to golf it down even more. This is still solid and it's a different approach from the way he did it, so I'll give you a +1!

bob 07/31/2017.

J, 17 16 bytes

(*/{_1,~i.&0)@~:

How?

(*/{_1,~i.&0)@~:

             @~: returns the nub sieve which is a vector with 1 for the first occurrence of an element in the argument and 0 otherwise

        i.&0     returns the first index of duplication

    _1,~         appends _1 to the index

 */              returns 0 with duplicates (product across nub sieve)

     {           select _1 if no duplicates, otherwise return the index

djhurio 07/31/2017.

R, 28 bytes

(x=scan())[duplicated(x)][1]

Try it online!

1 comments
Giuseppe 07/31/2017
I think you can now return NA for missing values since the spec has changed; so (x=scan())[duplicated(x)][1] is perfectly valid.

Perl 6, 13 bytes

*.repeated[0]

Try it


Explanation

  • The * is in a Term position so the whole statement is a WhateverCode lambda.

  • The .repeated is a method that results in every value except for the first time each value was seen.

    say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
    #   (      3, 3,       2, 3).Seq
  • [0] just returns the first value in the Seq.
    If there is no value Nil is returned.
    (Nil is the base of the Failure types, and all types are their own undefined value, so Nil different than an undefined value in most other languages)


Note that since the implementation of .repeated generates a Seq that means it doesn't start doing any work until you ask for a value, and it only does enough work to generate what you ask for.
So it would be easy to argue this has at worst O(n) time complexity, and at best O(2) time complexity if the second value is a repeat of the first.
Similar can probably be said of memory complexity.


lstefano 08/02/2017.

Dyalog APL Classic, 18 chars

Only works in ⎕IO←0.

     w[⊃(⍳∘≢~⍳⍨)w←¯1,⎕]

Remove from the list of indices of the elements of the argument with a prepended "-1" the list indices of its nub and then pick the first of what's left. If after the removal there only remains an empty vector, its first element is by definition 0 which is used to index the extended argument producing the desired -1.

2 comments
Zacharý 08/03/2017
Um... what's with the random leading spaces? +1 for outgolfing me by one byte.
Adám 08/04/2017
You may throw an error instead of returning ¯1, so you can remove ¯1, and use ⎕IO←1.

Adám 08/04/2017.

APL (Dyalog), 11 bytes

As per the new rules, throws an error if no duplicates exist.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Try it online!

⍳⍨ the indices of the first occurrence of each element

~ removed from

⍳∘≢ of all the indices

⍬⍴ reshape that into a scalar (gives zero if no data is available)

⊃⍨ use that to pick from (gives error on zero)

 the argument

2 comments
Zacharý 08/04/2017
Well, yeah, when the rules are changed, of course you can beat them all!
Zacharý 08/04/2017
Well, I tied you.

Moris Zucca 08/04/2017.

APL, 15

{⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}

Seems like we can return 0 instead of -1 when there are no duplicates, (thanks Adám for the comment). So 3 bytes less.

A bit of description:

⍵⍳⍵         search the argument in itself: returns for  each element the index of it's first occurrence
(⍳⍴⍵)~⍵⍳⍵   create a list of all indexes, remove those found in ⍵⍳⍵; i.e. remove all first elements
⊃⍵[...]     of all remaining elements, take the first. If the array is empty, APL returns zero

For reference, old solution added -1 to the list at the end, so if the list ended up empty, it would contain -1 instead and the first element would be -1.

{⊃⍵[(⍳⍴⍵)~⍵⍳⍵],¯1}

Try it on tryapl.org

1 comments
Adám 08/04/2017
You may return a zero instead of ¯1, so {⊃⍵[(⍳⍴⍵)~⍵⍳⍵]} should do.

Value Ink 08/04/2017.

Ruby, 28 36 bytes

Misunderstood the challenge the first time. O(n) time, O(n) space.

->a{d={};a.find{|e|b=d[e];d[e]=1;b}}

Try it online!


aross 08/14/2017.

PHP, 56 44 38 32 bytes

for(;!${$argv[++$x]}++;);echo$x;

Run like this:

php -nr 'for(;!${$argv[++$x]}++;);echo$x;' -- 2 3 3 1 5 2;echo
> 3

Explanation

for(
  ;
  !${                 // Loop until current value as a variable is truthy
    $argv[++$x]       // The item to check for is the next item from input
  }++;                // Post increment, the var is now truthy
);
echo $x;              // Echo the index of the duplicate.

Tweaks

  • Saved 12 bytes by using variables instead of an array
  • Saved 6 bytes by making use of the "undefined behavior" rule for when there is no match.
  • Saved 6 bytes by using post-increment instead of setting to 1 after each loop

Complexity

As can be seen from the commented version of the code, the time complexity is linear O(n). In terms of memory, a maximum of n+1 variables will be assigned. So that's O(n).

5 comments
Titus 08/11/2017
Thanks for not using a weird encoding. But you should add the error_reporting option to the byte count (or use -n, which is free).
aross 08/11/2017
We've been here before. PHP notices and warnings are ignorable. I might as well pipe them to /dev/null, which is the same.
Titus 08/11/2017
I tend to remember the wrong comments. :) Isn´t this O(n)?
aross 08/11/2017
Yes it's linear
Xanderhall 08/11/2017
How is that O(1) for additional space? You're literally assigning a new variable per n, which is O(n)

TheLethalCoder 07/31/2017.

C#, 145 bytes

using System.Linq;a=>{var d=a.Where(n=>a.Count(t=>t==n)>1);return d.Select((n,i)=>new{n,i}).FirstOrDefault(o=>d.Take(o.i).Contains(o.n))?.n??-1;}

Probably a lot shorter way to do this in C# with a simple loop but I wanted to try it with Linq.

Try it online!

Full/Formatted version:

namespace System.Linq
{
    class P
    {
        static void Main()
        {
            Func<int[], int> f = a =>
            {
                var d = a.Where(n => a.Count(t => t == n) > 1);
                return d.Select((n, i) => new { n, i }).FirstOrDefault(o => d.Take(o.i).Contains(o.n))?.n ?? -1;
            };

            Console.WriteLine(f(new[] { 2, 3, 3, 1, 5, 2 }));
            Console.WriteLine(f(new[] { 2, 4, 3, 5, 1 }));

            Console.ReadLine();
        }
    }
}
3 comments
LiefdeWen 07/31/2017
Here is the simple loop version. But I like the Linq version much more.
TheLethalCoder 07/31/2017
@LiefdeWen Post it as an answer :) Though I do usually like Linq better too :) Might be able to get it shorter with Linq too but I'm now sure.
LiefdeWen 07/31/2017
Nah, this question is overpopulated and I would rather you get the up-votes for this question.

miles 08/01/2017.

J, 12 bytes

,&_1{~~:i.0:

Try it online!

Explanation

,&_1{~~:i.0:  Input: array M
      ~:      Nub-sieve
          0:  The constant 0
        i.    Find the index of the first occurrence of 0 (the first duplicate)
,&_1          Append -1 to M
    {~        Select the value from the previous at the index of the first duplicate

jferard 08/01/2017.

Haskell, 78 69 bytes

 fst.foldl(\(i,a)(j,x)->(last$i:[j|i<0,elem x a],x:a))(-1,[]).zip[1..]

Try it online!

Saved 9 bytes thanks to @nimi

A basic path through the list. If the current element has not yet been seen (i<0) and is in the accumulator list (elem x a) then store the current index. Else, keep the index -1. In any case, add the current element to the accumulator list.

EDIT: I did not read the question carefully enough: this code outputs the index of the second element of a duplicate element.

2 comments
nimi 07/31/2017
You can use the "Shorter Conditional" from our "Tips for golfing in Haskell": \ ... ->(last$i:[j|i<0,elem x a],x:a). Also: no need for the f=, because unnamed functions are allowed.
jferard 07/31/2017
@nimi thanks for the tip!

Halvard Hummel 08/10/2017.

Python 2, 71 65 bytes

Returns None if there is no duplicate element

Edit: -6 bytes thanks to @musicman523

def f(n):
 for a in n:
	u=-abs(a)
	if n[u]<0:return-u
	n[u]=-n[u]

Try it online!

O(n) time complexity, O(n) space complexity, O(1) auxiliary space.

As the input list uses O(n) space, the space complexity is bound by this. Meaning we cannot have a lower space complexity than O(n)

Does modify the original list, if this is not allowed we could do it in the same complexity with 129 bytes

Explanation

Since every element is greater than 0 and less than or equal to the size of the list, the list has for each element a, an element on index a - 1 (0 indexed). We exploit this by saying that if the element at index i is negative, we have seen it before.

For each element a in the list n, we let u be negative the absolute value of a. (We let it be negative since python can index lists with negative indices, and we would otherwise need to do u=abs(a)-1) If the element at index u in the list is negative, we have seen it before and can therefore return -u (to get the absolute value of a, as all elements are positive). Else we set the element at index u to be negative, to remember that we have seen an element of value a before.

5 comments
musicman523 08/10/2017
Nice job! 65 bytes
Halvard Hummel 08/10/2017
Thanks @musicman523
Wheat Wizard 08/10/2017
Are you sure this is O(1) in memory? You are still using n bits of memory to store what numbers have already been visited, even though the bits are in the sign. It seems to me that this is O(n) in disguise
Oliver Ni 08/10/2017
Technically this uses O(n) space - the n sign bits. If the array can only hold values between 1 and n, like how it was given, then it obviously doesn't work.
Halvard Hummel 08/10/2017
This really just comes down to the representation you choose for the numbers. If unsigned numbers are used, then this is O(n) auxiliary space. If signed numbers are used, then the sign bit is already there, meaning O(1) auxiliary space.

Xanderhall 08/11/2017.

Java (OpenJDK 8), 65 117 109 bytes

Previous 65 byte solution:

r->{for(int a,b=0,z,i=0;;b=a)if((a=b|1<<(z=r[i++]))==b)return z;}

New solution. 19 bytes are included for import java.math.*;

-8 bytes thanks to @Nevay

r->{int z,i=0;for(BigInteger c=BigInteger.ZERO;c.min(c=c.setBit(z=r[i++]))!=c;);return z;}

Try it online!

Edit

The algorithm in my original program was fine, but the static size of the datatype used meant that it broke fairly quickly once the size went above a certain threshold.

I have changed the datatype used in the calculation to increase the memory limit of the program to accommodate this (using BigInteger for arbitrary precision instead of int or long). However, this makes it debatable whether or not this counts as O(1) space complexity.

I will leave my explanation below intact, but I wish to add that I now believe it is impossible to achieve O(1) space complexity without making some assumptions.

Proof

Define N as an integer such that 2 <= N .

Let S be a list representing a series of random integers [x{1}, ..., x{N}], where x{i} has the constraint 1 <= x{i} <= N.

The time complexity (in Big-O notation) required to iterate through this list exactly once per element is O(n)

The challenge given is to find the first duplicated value in the list. More specifically, we are searching for the first value in S that is a duplicate of a previous item on the list.

Let p and q be the positions of two elements in the list such that p < q and x{p} == x{q}. Our challenge becomes finding the smallest q that satisfies those conditions.

The obvious approach to this problem is to iterate through S and check if our x{i} exists in another list T: If x{i} does not exist in T, we store it in T. If x{i} does exist in T, it is the first duplicate value and therefore the smallest q, and as such we return it. This space efficiency is O(n).

In order to achieve O(1) space complexity while maintaining O(n) time complexity, we have to store unique information about each object in the list in a finite amount of space. Because of this, the only way any algorithm could perform at O(1) space complexity is if: 1. N is given an upper bound corresponding to the memory required to store the maximum number of possible values for a particular finite datatype. 2. The re-assignment of a single immutable variable is not counted against the complexity, only the number of variables (a list being multiple variables). 3. (Based on other answers) The list is (or at least, the elements of the list are) mutable, and the datatype of the list is preset as a signed integer, allowing for changes to be made to elements further in the list without using additional memory.

1 and 3 both require assumptions and specifications about the datatype, while 2 requires that only the number of variables be considered for the calculation of space complexity, rather than the size of those variables. If none of these assumptions are accepted, it would be impossible to achieve both O(n) time complexity and O(1) space complexity.

Explanation

Whoo boy, this one took an embarrassingly long time to think up a bit of brain power.

So, going for the bonus is difficult. We need both to operate over the entire list exactly once and track which values we've already iterated over without additional space complexity.

Bit manipulation solves those problems. We initialize our O(1) 'storage', a pair of integers, then iterate through the list, OR-ing the ith bit in our first integer and storing that result to the second.

For instance, if we have 1101, and we perform an OR operation with 10, we get 1111. If we do another OR with 10, we still have 1101.

Ergo, once we perform the OR operation and end up with the same number, we've found our duplicate. No duplicates in the array causes the program to run over and throw an exception.

5 comments
SchoolBoy 08/10/2017
Also, your second test includes the number 100, but thats impossible since the array itself is only 5 long
SchoolBoy 08/10/2017
Also, this fails since an int doesn't have enough storage.
Xanderhall 08/10/2017
@SchoolBoy Good catch. My only problem is that there doesn't seem to be any upper limit on the size of the array, so I can't realistically change my code to solve memory issues.
SchoolBoy 08/10/2017
@Xanderhall True, but i feel like 32 (or if you use a long, 64) numbers is too little :p. Either way, imposing a limit on the input, and then allocating the maximum memory needed and calling it O(1) memory is just a cheat. It is still O(n) since if the size of the input increased, so would this upper bound to the memory. Which is also why I think it is impossible to create an O(n) O(1) algorithm
SchoolBoy 08/10/2017
@Xanderhall P.S. I'm getting close to your 65, I'm at 67 bytes :p

SchoolBoy 08/14/2017.

Java 8, 82 78 76 bytes No longer viable, 75 67 64 bytes below in edit

As a lambda function:

a->{Set<Long>s=new HashSet<>();for(long i:a)if(!s.add(i))return i;return-1;}

Probably can be made much smaller, this was very quick.

Explanation:

a->{                                //New lambda function with 'a' as input
    Set<Long>s=new HashSet<>();     //New set
    for(long i:a)                   //Iterate over a
        if(!s.add(i))               //If can't add to s, already exists
            return i;               //Return current value
        return-1;                   //No dupes, return -1
}

*Edit*

75 67 64 bytes using the negation strategy:

a->{int i=0,j;while((a[j=Math.abs(a[i++])-1]*=-1)<0);return++j;}

Try it online!

(-3 bytes thanks to @Nevay)

Explanation:

a->{                                         //New lambda expression with 'a' as input
    int i=0,j;                               //Initialise i and declare j
    while((a[j=Math.abs(a[i++])-1]*=-1)<0);  //Negate to keep track of current val until a negative is found
    return++j;                               //Return value
}

Loops over the array, negating to keep track. If no dupes, just runs over and throws an error.

Both of these work on O(n) time and O(n) space complexity.

5 comments
Jakob 08/10/2017
It's worth noting that this will need to be assigned to a lambda returning Number, since i is a long and -1 is an int.
SchoolBoy 08/10/2017
@Jakob Not necessary, -1 being an int will automatically be cast to a long without explicitly specifying the cast
Jakob 08/10/2017
It will cast implicitly to long, but not to Long as required for the lambda to be assigned to a Function. Did you test it? Regardless, that solution can be replaced with your new one.
Nevay 08/11/2017
You can use raw types Set s=new HashSet(); to save 7 bytes. (Besides: afaik the import of java.util.*; has to be included into the byte count -> +19 bytes.) The return statement can be return++j, the if-statement can be removed a->{int i=0,j;for(;(a[j=Math.abs(a[i++])-1]*=-1)<0;);return++j;} (-3 bytes).
SchoolBoy 08/12/2017
@Nevay edited, thanks :)

RosLuP 07/31/2017.

Axiom 96, bytes

g(a:List INT):INT==(for i in 2..#a repeat(for j in 1..i-1 repeat if a.i=a.j then return a.i);-1)

it is O(n^2)


SuperStormer 07/31/2017.

Javascript, 54 bytes

a=>(b=[],a.find(e=>b.includes(e)?e:(b.push(e),0))||-1)

Uses another array to keep track of the already encountered values.


HighResolutionMusic.com - Download Hi-Res Songs

1 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
2 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
3 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
4 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
5 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
6 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
7 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
8 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
9 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
10 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
11 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
12 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
13 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
14 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
15 Deep Chills

Run Free flac

Deep Chills. 2018.
16 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
17 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.
18 Khalid

Better flac

Khalid. 2018. Writer: Charlie Handsome;Jamil Chammas;Denis Kosiak;Tor Erik Hermansen;Mikkel Stoleer Eriksen;Khalid.
19 Diplo

Electricity flac

Diplo. 2018. Writer: Diplo;Mark Ronson;Picard Brothers;Wynter Gordon;Romy Madley Croft;Florence Welch.
20 Julia Michaels

There's No Way flac

Julia Michaels. 2018. Writer: Ian Kirkpatrick;Justin Tranter;Julia Michaels;Lauv.

Related questions

Hot questions

Language

Popular Tags