CareerCup

Time: O(n) Space: O(n)
Use hashMap to mark every element encountered so far. The first element that is already in map is the output, print that number and return.

import java.util.HashMap;


public class FirstDupicate {

	public  static void main(String []args)
	{
		int []arr= {4,3,5,6,5,7,8,4};
		int duplicate=-1;
		HashMap<Integer,Integer> hm=new HashMap<Integer, Integer>();
		
		for(int i:arr){
			System.out.print(i+",");
		if(null==hm.get(i))
		{
			hm.put(i,i);
		}
		else{
			duplicate=i;
		break;
		}
		}
		System.out.println(duplicate);
	}
}

This is my C++ version with O(n) time, O(n) space.

#include <iostream>
#include <unordered_set>
#include <vector>

template <typename T>
typename std::vector<T>::iterator find_first_duplicate(std::vector<T>& arr) {
	std::unordered_set<T> set;
	for (auto it = arr.begin(); it != arr.end(); it++) {
		const T& elem = *it;
		if (set.count(elem))
			return it;
		set.insert(elem);
	}
	return arr.end();
}

int main() {
	std::vector<int> arr{4,3,1,2,5,9,5,4};
	auto it = find_first_duplicate(arr);
	if (it != arr.end())
		std::cout << "first duplicate: " << *it << std::endl;
	return 0;
}

Time O(n) Space(n). Finding a number which have Closest duplicate. Below method will return 5 as answer not 4 since 5 has closest duplicate then 4.

public static int FindClosestDuplicate(int[] arr)
        {
            if (arr == null) return -1;

            Dictionary<int, int> elePos = new Dictionary<int, int>();

            int minDiff = int.MaxValue;
            int duplicate = -1;
            for (int i = 0; i < arr.Length; i++)
            {
                if (elePos.ContainsKey(arr[i]))
                {
                    int pos = elePos[arr[i]];
                    int diff = i - pos;
                    if (diff < minDiff)
                    {
                        minDiff = diff;
                        duplicate = arr[i];
                    }
                }
                else
                    elePos.Add(arr[i], i);
            }

            return duplicate;
        }
    }

srinivas , sorting will change the index , so how will you know that which element is first repeated/duplicate .. best way is using hashing .. if there is any other way other than using hashing with o(n), i would like to know .

public class FindingFirstDuplicateElement {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] data = { 4, 3, 1, 2, 5, 9, 5, 4 };
		Map<Integer, Integer> lookup = new HashMap<Integer, Integer>();
		for (int temp : data) {
			if (lookup.containsKey(temp)) {
				System.out.println(temp);
			} else {
				lookup.put(temp, 1);
			}
		}
	}

}}

I agree that hashset should be used since it also has a method that returns false if the element being added is duplicate.Moreover for Performance both hashmap and hashset are same,but this code makes it much simpler.

import java.util.HashSet;


public class FirstDupicate {
//Use hashset because it has a function that can be used for finding the duplicates (public boolean add(obj) )
	public  static void main(String []args)
	{
		int []arr= {4,3,5,6,5,7,8,4};
		int duplicate=-1;
		HashSet<Integer> hs=new HashSet<Integer>();
		boolean isUnique=false;
		for(int i:arr){
		
			isUnique=hs.add(i);
			if(!isUnique)
			{
				duplicate=i;
				break;
			}
		}
		System.out.println(duplicate);
	}
}

For simplicity, assume that the values of the array A are all positive integers and A has length N (In the general case, hash the values of A into the positive integers). Now, count sort the values A[i] of A, starting from i=0, noting that the first bin to obtain two elements will be the first duplicate.

Let B = array of length max{ A[i] }

for i=0, i < B.length, i++
	B[i]=0

for i=0, i < N, i++
	if B[A[i]]    //returns true when B[A[i]]=1, aka A[i] has already appeared
		return i    //index of the first duplicate
	B[A[i]]++

Since we begin with i=0, we are assured to return the first duplicate.

import java.util.*;
public class Firstduplicate {
public static void main(String[] args) {
// TODO code application logic here
HashSet hs = new HashSet();
int[] array = {4,3,1,2,5,9,5,4};
int i=0;
while(hs.add(array[i]))
{
i++;
}
System.out.println(array[i]);
}
}

O(n) time and O(n) space

public static int firstDuplicate(int[] input)
{
	Set<Integer> uniqes = new HashSet<Integer>();

	for(int i=0;i<input.length;i++)
	{
		if(uniques.contains(input[i]))
			return input[i];
		uniques.put(input[i]);
	}
}

Recursive version

int getDuplicateElement(int[] numbers, int j, int dupElement, int difference)
{
       if(j + 1 == numbers.length)
       {
           return dupElement;
       }
         
       for(int i = j + 1; i < numbers.length; i++)
       {
           if(numbers[j] == numbers[i] && difference > (i - j))
           {
             dupElement = numbers[i];
             difference = i - j;
             break;
           }  
       }
         
       return getDuplicateElement(numbers, j + 1, dupElement, difference);
   }

Here is the C++ code:
	//!!!Finding first duplicate element in the array

	string strArr = "43125954";
	int cPntr = 0;
	int lPntr = 0;

	for (int i = 0; i < strArr.length(); i++)
	{
		for (int j = (i+1); j < strArr.length(); j++)
		{
			if (strArr[i] == strArr[j])
			{
			 cPntr = j;
			}
		}

		if ( cPntr < lPntr)
			lPntr = cPntr;
		else
			lPntr = cPntr;

	}
	cout << strArr[lPntr] << " is the first duplicate elements in the string";
	cout << endl;

d = []
for i in a:
if i in d:
print i
break
else:
d.append(i)

public static void fPrintDuplicate(int []arr) {

//Time complexity is more, as all elements till end needs to be worked
int asum=0;
int n = arr.length;
int esum = n*(n+1)/2; //expected sum;
for(int i=0;i<arr.length;i++)
asum += arr[i];
System.out.println("esum="+esum); //expected sum;
System.out.println("asum="+asum); //actual sum
int missing = n - (asum+1 - esum) ;
System.out.println("Missing number = "+missing);
int duplicate = missing - 1;
System.out.println("Duplicate number = "+duplicate);

}

we sort elements and compare with side element.....

int firstDup(int[] str) {
		int len = str.length;
		Map map = new HashMap();
		int loc = len;
		int lastValue = 0;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (str[i] == str[j]) {
					if (loc > j) {
						loc = j;

					}
				}
			}
		}
		return str[loc];
	}