CodeFights - issues with time limit when writing FirstDuplicate method

Question

I'm trying to solve the problem below from CodeFights. I left my answer in Java after the question. The code works for all the problems, except the last one. Time limit exception is reported. What could I do to make it run below 3000ms (CodeFights requirement)?

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

Input/Output

[time limit] 3000ms (java) [input] array.integer a

Guaranteed constraints: 1 ≤ a.length ≤ 105, 1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

    int storedLeastValue = -1;
    int indexDistances = Integer.MAX_VALUE;
    int indexPosition = Integer.MAX_VALUE;

    for (int i = 0; i < a.length; i++) 
    {   
            int tempValue = a[i];

            for (int j = i+1; j < a.length; j++) {
                if(tempValue == a[j])
                {
                    if(Math.abs(i-j) < indexDistances && 
                      j < indexPosition)
                    {
                        storedLeastValue = tempValue;
                        indexDistances = Math.abs(i-j);
                        indexPosition = j;
                        break;
                    }
                }
            }
        }

        return storedLeastValue;

Answer 1

Your solution has two nested for loops which implies O(n^2) while the question explicitly asks for O(n). Since you also have a space restriction you can't use an additional Set (which can provide a simple solution as well).

This question is good for people that have strong algorithms/graph theory background. The solution is sophisticated and includes finding an entry point for a cycle in a directed graph. If you're not familiar with these terms I'd recommend that you'll leave it and move to other questions.

Answer 2

Check this one, it's also O(n) , but without additional array.

    int firstDuplicate(int[] a) {
        if (a.length <= 1) return -1;
        for (int i = 0; i < a.length; i++) {
            int pos = Math.abs(a[i]) - 1;
            if (a[pos] < 0) return pos + 1;
            else a[pos] = -a[pos];
        }
        return -1;
    }

Answer 3

The accepted answer does not work with the task. It would work if the input array would indeed contain no bigger value than its length. But it does, eg.: [5,5].

So, we have to define which number is the biggest.

int firstDuplicate(int[] a) {

    int size = 0;
    for(int i = 0; i < a.length; i++) {
        if(a[i] > size) {
            size = a[i];
        }
    }

    int[] t = new int[size+1];

    for(int i = 0; i < a.length; i++) {
        if(t[a[i]] == 0) {
            t[a[i]]++;
        } else {
            return a[i];
        }
    }
    return -1;
}

Answer 4

What about this:

       public static void main(String args[]) {

            int [] a = new int[] {2, 3, 3, 1, 5, 2};
            // Each element of cntarray will hold the number of occurrences of each potential number in the input (cntarray[n] = occurrences of n)
            // Default initialization to zero's 
            int [] cntarray = new int[a.length + 1]; // need +1 in order to prevent index out of bounds errors, cntarray[0] is just an empty element

            int min = -1;
            for (int i=0;i < a.length ;i++) {
                if (cntarray[a[i]] == 0) {
                    cntarray[a[i]]++;
                } else {
                    min = a[i];
                    // no need to go further
                    break;
                }
            }
            System.out.println(min);
        }

Answer 5

You can store array values in hashSet. Check if value is already present in hashSet if not present then add it in hashSet else that will be your answer. Below is code which passes all test cases:-

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

Answer 6

My simple solution with a HashMap

int solution(int[] a) {
HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
int min = -1;
for (int i=0; i < a.length; i++) {
    if (!(countMap.containsKey(a[i]))) {
        countMap.put(a[i],1);
    }
    else {
        return a[i];
    }
}  
return min;
}

Answer 7

Solution is very simple:

1. Create a hashset
2. keep iterating over the array
3. if element is already not in the set, add it.
4. else element will be in the set, then it mean this is minimal index of first/second the duplicate

  int solution(int[] a) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int i=0; i<a.length; i++){
            if(set.contains(a[i])){
                // as soon as minimal index duplicate found where first one was already in the set, return it
                return a[i];
            }
            
            set.add(a[i]);
        }
        
        return -1;
    }

Answer 8

A good answer for this exercise can be found here - https://forum.thecoders.org/t/an-interesting-coding-problem-in-codefights/163 - Everything is done in-place, and it has O(1) solution.