Find Duplicate in Array

Find Duplicate in Array - InterviewBitInterviewBit

Techniques

Technique	Time Complexity	Sapce Complexity
Brute Force	$O(n^2)$	$O(1)$
Sorting	$O(n\log n)$​	$O(n)$ or $O(1)$​
Set/Map	$O(n)$​	$O(n)$

Brute Force

CPP

int Solution::repeatedNumber(const vector<int> &A) {
    for(int i = 0; i < A.size(); i++)
        for(int j = i + 1; j < A.size(); j++)
            if(A[i] == A[j])
                return A[i];
                
    return -1;
}

Time Limit Exceed

JS

Time Complexity: $O(n^2)$​

Space Complexity: $O(1)$​

Using Sorting

CPP

int Solution::repeatedNumber(const vector<int> &A) {
    vector<int> copy(A.begin(), A.end());
    sort(copy.begin(), copy.end());
    int prev = copy[0];
    for(int i = 1; i < copy.size(); i++) 
        if(copy[i] == prev)    
            return copy[i];
        else
            prev = copy[i];
            
    return prev;
}

Accepted

JS

Time Complexity: $O(n \log n)$​

Space Complexity: $O(n)$​ for duplicating const array.

Using Set

CPP

int Solution::repeatedNumber(const vector<int> &A) {
    set<int> s;
    for(const int &x: A)
        if(s.count(x))
            return x;
        else
            s.insert(x);
            
    return -1;
}

Memory Limit Exceed

JS

Time Complexity: $O(n)$​

Space Complexity: $O(n)$​

Tortoise Hare

int Solution::repeatedNumber(const vector<int> &A) {
    int slow = A[0];
    int fast = A[0];
    
    do {
        slow = A[slow];
        fast = A[A[fast]];
    } while(slow != fast);
    
    slow = A[0];
    
    while(slow != fast) {
        slow = A[slow];
        fast = A[fast];
    }
    
    return slow;
}

Time Complexity: $O(n)$​

Space Complexity: $O(1)$​