CodeSignal: Execution time limit exceeded with c++

Question

I am trying to solve the programming problem firstDuplicate on codesignal. The problem is "Given an array a that contains only numbers in the range 1 to a.length, find the first duplicate number for which the second occurrence has minimal index".

Example: For a = [2, 1, 3, 5, 3, 2] the output should be firstDuplicate(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.

With this code I pass 21/23 tests, but then it tells me that the program exceeded the execution time limit on test 22. How would I go about making it faster so that it passes the remaining two tests?

#include <algorithm>

int firstDuplicate(vector<int> a) {
    vector<int> seen;
    
    for (size_t i = 0; i < a.size(); ++i){
        if (std::find(seen.begin(), seen.end(), a[i]) != seen.end()){
            return a[i];
        }else{
            seen.push_back(a[i]);
        }
    }
    
    if (seen == a){
        return -1;
    }
    
}

Answer 1

Anytime you get asked a question about "find the duplicate", "find the missing element", or "find the thing that should be there", your first instinct should be use a hash table. In C++, there are the unordered_map and unordered_set classes that are for such types of coding exercises. The unordered_set is effectively a map of keys to bools.

Also, pass you vector by reference, not value. Passing by value incurs the overhead of copying the entire vector.

Also, that comparison seems costly and unnecessary at the end.

This is probably closer to what you want:

#include <unordered_set>


int firstDuplicate(const vector<int>& a) {
    std::unordered_set<int> seen;
    
    for (int i : a) {
       auto result_pair = seen.insert(i);
       bool duplicate = (result_pair.second == false);
       if (duplicate) {
          return (i);
       }
    }

    return -1;
   
}