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

module.exports = { 
 //param A : array of integers
 //return an integer
    repeatedNumber : function(A){
        for(let i = 0; i < A.length; i++)
            for(let j = i + 1; j < A.length; j++)
                if(A[i] == A[j])
                    return A[i];
                    
        return -1;
    }
};

Time Limit Exceed

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

module.exports = { 
  //param A : array of integers
  //return an integer
  repeatedNumber : function(A){
    A.sort()
    
    prev = A[0]
    for(let i = 1; i < A.length; i++)
      if(A[i] == prev)
        return A[i]
      else
        prev = A[i]
  }
};

Accepted

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

module.exports = { 
    //param A : array of integersa
    //return an integer
    repeatedNumber : function(A){
        let s = new Set()
        
        for(let x of A)
            if(s.has(x))
                return x
            else
                s.add(x)
    }
};

Accepted

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)$​