Contains duplicates

We need to check if a given array has some duplicate values.

Example: [1,1,2] = True [1,2,3] = False

Option 1:

We can just loop over the list twice and compare each value. This would give us a runtime of Time: O(n^2) and Space: O(n)

bool contains_duplicates(std::vector<int> &input) {
  for (int i = 0; i < input.size(); i++) {
    for (int j = i + 1; j < input.size(); j++) {
      if (input[i] == input[j]) {
        std::cout << "Found duplicates " << input[i] << " and " << input[j]
                  << std::endl;
        return true;
      }
    }
  }

  return false;
}

def contains_duplicates(input: List[int]) -> bool:
    for i in range(len(input)):
        for j in range(i+1,len(input)):
            if input[i] == input[j]:
                return True
    return False

Better Solution:

We can keep track of already seen values in a set. A set has a runtime of O(1) for finding an item by a key. This would give us a runtime of Time: O(n) and Space: O(n)

bool contains_duplicates(std::vector<int> &input) { 
    std::unordered_set<int> seen;
    for(auto &i :input){
        if(seen.find(i) != seen.end()) return true;
        seen.insert(i);
    }
    return false;

}

def contains_duplicates(input: List[int]) -> bool:
    seen = set()
    for num in input:
        if num in seen:
            return True
        seen.add(num)
    return False