Problem - Find Duplicate Element In An Array

Problem

Coder Raco is working on flight seat booking application. He used an array to store booked seat numbers. A logic must be applied in the application to ensure a seat is not booked twice or thrice. Let’s help Coder Raco to write the code:

Duplicate number is: 5

Another example:

Duplicate number is: 3

Solution Approach

Brute Force

Raco has a naive approach that compares each array element to every other element, and if they match, the number is identified.

Hint

1. Run nested loop, outer loop 0 to n-1 and inner loop 1 to n.
2. Compare the outer index element to the inner index element.

Algorithm

• Initialize a ‘duplicate’ variable with zero value to store the duplicate number.
• Start a for loop where the ‘currentElementIndex’ is from 0 to N - 1.
• Assign the value in ‘currentElement’ = arr[currentElementIndex].
• Start a for loop where the ‘index’ is from (currentElementIndex + 1) to N - 1.
• Check if currentElement == arr[index].
• Assign the value in duplicate = currentElement.
• Break Loop.
• Break Loop if a ‘duplicate’ has value.

MainLoop	Inner Loop

Use Sorting With Linear Search

Hint

1. It is easy to find the duplicate number after sorting the array.

Algorithm

• Sort the array using quicksort.
• Start a for loop where the ‘index’ is from 0 to N - 2.
• Check if arr[index] == arr[index+1].
• return arr[index].
• EndLoop.
• return -1.

Code Examples (C)

Brute Force

int findDuplicate(int *integerArray, int arrayCount) {
    for (int currentIndex = 0; currentIndex < arrayCount; currentIndex++) {
        int currentElement = integerArray[currentIndex];
        for (int index = currentIndex + 1; index < arrayCount; index++) {
            if (integerArray[index] == currentElement) {
                return integerArray[index];  // Return the first duplicate found
            }
        }
    }
    return -1; // No duplicate found
}

Complexity

Time Complexity O(n2)

Since using nested loops to compare each element with every other element. This approach has a time complexity of O(n2).

Space Complexity O(1)

A constant space is required to store variables, so the space complexity is O(1).

Use Sorting With Linear Search

int findDuplicateWithSort(int *integerArray, int arrayCount) {
    qsort(integerArray, arrayCount, sizeof(int), compare); // Sort array in O(n log n)
    for (int i = 0; i < (arrayCount - 1); i++) {
        if (integerArray[i] == integerArray[i + 1]) { // If adjacent elements are equal, duplicate found
            return integerArray[i];
        }
    }
    return -1; // No duplicate found
}

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

Complexity

Time Complexity O(nlogn)

Using quick sort to sort the array has the complexity of O(nlogn). Then, a linear search to find a duplicate number has the complexity of O(n). So the overall complexity is:

**O(nlogn)+O(n)=O(nlogn)**

As the dominant term is O(n log n).

Space Complexity O(1)

A constant space is required to store variables, so the space complexity is O(1).

Bonus Solution (Hashing)

The hashing (extra space) approach works by keeping track of the elements we have seen using an auxiliary array (or hash table). This allows us to efficiently detect duplicates in O(n) time while using O(n) additional space. Most of the programming language provides an inbuilt Hash map that can be used to solve this problem.