Find Duplicate Element

Problem statement

Given an array of integers A, find one number that repeats. Find the repeated element and return it. If there are no duplicate elements present in the input array, return -1.

Examples

Example 01:

Input: A = [3, 4, 1, 4, 2]

Output: 4

Example 02:

Input: A = [-7, 19, 1, 4, 2]

Output: -1

Example 03:

Input: A = [1, 1, 4, 2, 1]

Output: 1 // 1 appeared 3 times in the array

Thought process

Before writing pseudo code, come up with questions and ask the interviewer.

1. Is the input array sorted?
2. Should we return -1, when the input array is empty?

Algorithm

1. Create a HashSet and store the first element.
2. Iterate through all the elements.
3. Check if they exist in the HashSet; if yes, return the element. If not, store the element in the HashSet.
4. Continue the process until the last iteration. If there is no repeating element, return -1.

Solution

import java.util.HashSet;

public class FindDuplicateElement {
  public static void main(String[] args) {
    int[] A = {-7, 5, 1, 4, 2, 2};

    System.out.println(findDuplicate(A));
  }

  private static int findDuplicate(int[] A) {
    HashSet<Integer> uniqueElements = new HashSet<>();

    for (int el : A) {
      if (uniqueElements.contains(el)) {
        return el;
      }

      uniqueElements.add(el);
    }
    return -1;
  }
}

Complexity analysis

Time complexity: O(n), we need to traverse all the elements in the array. If there are n items, then the time complexity to run the algorithm takes O(n).

Space complexity: O(n), this is because we are storing n elements in the HashSet.