firstDuplicate

//furstDuplicate 
//1) n^2 double for loop solution it's bad! we can do much better 
//update minimum index everytime finds smaller 
//access of array of index 

int firstDuplicate(int [] a){
	int min_index = a.length; 
  	for(int i=0; i<a.length; i++){
		for(int j= i+1; j<a.length; j++){
    		if(a[i] == a[j]){ // find duplicate 
            	min_index = Math.min(min_index);
       	 	}
   		}
    }
  
  	if(min_index = a.length) return -1; 
 	else return a[min_index]; 
	
}

//space complexity can be used to speed up time complexity 
//good solution. fast enough. but we don't want to waste space. 
//2) hashshet - no time to access data. constant time (no time at all) putting things in 

int firstDuplicate(int []a){
	Hashset <Integer> set = new HashSet(); 
    for(int i=0; i<a.length; i++){
        if(!set.contains(a[i]){
            set.add(a[i]);
        }else return a[i];
    }
    return -1;
}

//think about inputs constraints has to 1 to length of the array 
//cannot go out of the length of array 

//find 2 then go to that index-1 and mark as negative 
//when that is already negative then we found duplicate
//Math.abs(); 

int firstDuplicate(int [] a){
    for(int i=0; i<a.length; i++){
    	//have to use absolute value cuz index cannot be negative! 
        if(a[Math.abs(a[i])-1] < 0 ){ //not just a[i-1] 
            return a[Math.abs(a[i])-1] ; //not just a[i]
        }else{
        	a[Math.abs(a[i]-1]) = -a[Math.abs([a[i]-1]); // a[i] starts from 1 so no worry out of index
        }
    }
    return -1; 
}