firstDuplicate of array This question has been asked for other languages, but I haven't seen it for C++.  Most notably here and here.


  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, return -1.


My tests are running correctly, but I'm getting a timeout from the website codesignalDotCom.  I'm wondering what I'm doing that could be taking so much time, and what could be done to fix it.

int firstDuplicate(std::vector&lt;int&gt; a) {
    std::vector&lt;int&gt; newVector;  
    std::cout &lt;&lt; a.size() &lt;&lt; std::endl;
    for(int i = 0; i &lt; a.size(); i++) {
        if(std::find(newVector.begin(), newVector.end(), a.at(i)) != newVector.end()){
            return a.at(i);
        }
        newVector.push_back(a.at(i));
    }
    return -1;
}
Find more appropriate data structures


  This question has been asked for other languages, but I haven't seen it for C++.


Getting timeout usually indicates an inefficient algorithm.
The language doesn't matter, because algorithms are language agnostic.
Some of the posts you linked mention the word "performance",
and they shed light to the problem,
with suggestions that could be applied here too,
even if the language is different.

The first thing to ask when a solution is too slow,
what's the time complexity of the algorithm?


   quadratic: \$O(n^2)\$


That's not so good. Looping over all elements is a linear operation (\$O(n)\$),
and checking if an element is in a vector is also a linear operation.

In other words, the weak spot is using a vector to store the elements already seen.
A vector doesn't provide a fast way to search for random elements.
Other data structures can provide faster than linear performance to lookup elements:
a tree set can do it in logarithmic time (\$O(\log n)\$, making the overall complexity of your algorithm log-linear \$O(n \log n)\$),
or a hash set can do it in constant time (\$O(1)\$, making the overall complexity of your algorithm linear \$O(n)\$).

Coding style

The name newVector is not great, for several reasons:


What's "new" about it?
Including the name of the data structure in the name of the variable usually doesn't give much new information to the reader, and therefore doesn't help understand its purpose.


This vector is used to store elements already seen. I would have called it seen.



The name a is even worse: it tells nothing to the reader about what it is.



The main loop goes over indexes of the input vector.
You could loop over the values of the input,
which would read more natural:

for (int value : a) {
    if (std::find(newVector.begin(), newVector.end(), value) != newVector.end()){
        return value;
    }
    newVector.push_back(value);
}