How can I find the smallest covering prefix of an array in Java?

Find the first covering prefix of a given array.

A non-empty zero-indexed array A consisting of N integers is given. The first covering prefix of array A is the smallest integer P such that and such that every value that occurs in array A also occurs in sequence.

For example, the first covering prefix of array A with A[0]=2, A[1]=2, A[2]=1, A[3]=0, A[4]=1 is 3, because sequence A[0], A[1], A[2], A[3] equal to 2, 2, 1, 0 contains all values that occur in array A.

My solution is

int ps ( int[] A ) 
{
    int largestvalue=0;
    int index=0;   

    for(each element in Array){
        if(A[i]>largestvalue)
        {
            largestvalue=A[i];
            ind开发者_开发知识库ex=i;
        }
    }

    for(each element in Array)
    {
        if(A[i]==index)
            index=i; 
    }   
    return index;
}

But this only works for this input, this is not a generalized solution.

---

Got 100% with the below.

public int ps (int[] a)
    {
        var length = a.Length;
        var temp = new HashSet<int>();
        var result = 0;

        for (int i=0; i<length; i++)
        {
            if (!temp.Contains(a[i]))
            {
                temp.Add(a[i]);
                result = i;
            }
        }
        return result;
    }

---

I would do this

int coveringPrefixIndex(final int[] arr) {
    Map<Integer,Integer> indexes = new HashMap<Integer,Integer>();
    // start from the back
    for(int i = arr.length - 1; i >= 0; i--) {
        indexes.put(arr[i],i);
    }
    // now find the highest value in the map
    int highestIndex = 0;
    for(Integer i : indexes.values()) {
        if(highestIndex < i.intValue()) highestIndex = i.intValue();
    }
    return highestIndex;
}

---

Your question is from Alpha 2010 Start Challenge of Codility platform. And here is my solution which got score of 100. The idea is simple, I track an array of counters for the input array. Traversing the input array backwards, decrement the respective counter, if that counter becomes zero it means we have found the first covering prefix.

public static int solution(int[] A) {
    int size = A.length;
    int[] counters = new int[size];

    for (int a : A)
        counters[a]++;

    for (int i = size - 1; i >= 0; i--) {
        if (--counters[A[i]] == 0)
            return i;
    }

    return 0;
}

---

here's my solution in C#:

public static int CoveringPrefix(int[] Array1)
    {
        // Step 1. Get length of Array1
        int Array1Length = 0;
        foreach (int i in Array1) Array1Length++;
        // Step 2. Create a second array with the highest value of the first array as its length
        int highestNum = 0;
        for (int i = 0; i < Array1Length; i++)
        {
            if (Array1[i] > highestNum) highestNum = Array1[i];
        }
        highestNum++;   // Make array compatible for our operation
        int[] Array2 = new int[highestNum];
        for (int i = 0; i < highestNum; i++) Array2[i] = 0; // Fill values with zeros
        // Step 3. Final operation will determine unique values in Array1 and return the index of the highest unique value
        int highestIndex = 0;
        for (int i = 0; i < Array1Length; i++)
        {
            if (Array2[Array1[i]] < 1)
            {
                Array2[Array1[i]]++;
                highestIndex = i;
            }
        }
        return highestIndex;
    }

---

100p

public static int ps(int[] a) {
    Set<Integer> temp = new HashSet<Integer>();
    int p = 0;
    for (int i = 0; i < a.length; i++) {
        if (temp.add(a[i])) {
            p = i+1;
        }
    }
    return p;
}

---

You can try this solution as well

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int ps ( int[] A ) {
        Set set = new HashSet();
        int index =-1;

        for(int i=0;i<A.length;i++){
            if(set.contains(A[i])){
                if(index==-1)
                    index = i;
            }else{
                index = i;
                set.add(A[i]);
            }         
        }
        return index;
    }
}

---

Without using any Collection:
search the index of the first occurrence of each element,
the prefix is the maximum of that index. Do it backwards to finish early:

private static int prefix(int[] array) {
    int max = -1;
    int i = array.length - 1;
    while (i > max) {
        for (int j = 0; j <= i; j++) { // include i
            if (array[i] == array[j]) {
                if (j > max) {
                    max = j;
                }
                break;
            }
        }
        i--;
    }
    return max;
}

// TEST

private static void test(int... array) {
    int prefix = prefix(array);
    int[] segment = Arrays.copyOf(array, prefix+1);
    System.out.printf("%s = %d = %s%n", Arrays.toString(array), prefix, Arrays.toString(segment));
}

public static void main(String[] args) {
    test(2, 2, 1, 0, 1);
    test(2, 2, 1, 0, 4);
    test(2, 0, 1, 0, 1, 2);
    test(1, 1, 1);
    test(1, 2, 3);
    test(4);
    test();  // empty array
}

---

This is what I tried first. I got 24%

public int ps ( int[] A ) {
int n = A.length, i = 0, r = 0,j = 0;

for (i=0;i<n;i++) {
    for (j=0;j<n;j++) {
        if ((long) A[i] == (long) A[j]) {
            r += 1;
        }
        if (r == n) return i;
    }
}
return -1;
}

---

    //method must be public for codility to access
public int solution(int A[]){
    Set<Integer> set = new HashSet<Integer>(A.length);
    int index= A[0];
    for (int i = 0; i < A.length; i++) {
        if( set.contains(A[i])) continue;
        index = i;
        set.add(A[i]);
    }   
    return index;
}

this got 100%, however detected time was O(N * log N) due to the HashSet. your solutions without hashsets i don't really follow...

---

shortest code possible in java:

    public static int solution(int A[]){
    Set<Integer> set = new HashSet<Integer>(A.length);//avoid resizing
    int index= -1; //value does not matter;
    for (int i = 0; i < A.length; i++) 
        if( !set.contains(A[i])) set.add(A[index = i]); //assignment + eval     
    return index;
}

---

I got 100% with this one:

public int solution (int A[]){
    int index = -1;
    boolean found[] = new boolean[A.length];

    for (int i = 0; i < A.length; i++)
        if (!found [A[i]] ){
            index = i;
            found [A[i]] = true;
        }

    return index;    
}

I used a boolean array which keeps track of the read elements.

---

This is what I did in Java to achieve 100% correctness and 81% performance, using a list to store and compare the values with.

It wasn't quick enough to pass random_n_log_100000 random_n_10000 or random_n_100000 tests, but it is a correct answer.

public int solution(int[] A) {
    int N = A.length;
    ArrayList<Integer> temp = new ArrayList<Integer>();

    for(int i=0; i<N; i++){
        if(!temp.contains(A[i])){
            temp.add(A[i]);
        }
    }

    for(int j=0; j<N; j++){
        if(temp.contains(A[j])){
            temp.remove((Object)A[j]);
        }
        if(temp.isEmpty()){
            return j;
        }
    }

    return -1;
}

---

Correctness and Performance: 100%:

import java.util.HashMap;
class Solution {

   public int solution(int[] inputArray)
   {
      int covering;
      int[] A = inputArray;
      int N = A.length;
      HashMap<Integer, Integer> map = new HashMap<>();
      covering = 0;

      for (int i = 0; i < N; i++)
      {
          if (map.get(A[i]) == null)
          {
              map.put(A[i], A[i]);
              covering = i;
          }
      }
      return covering;
  }
}

---

Here is my Objective-C Solution to PrefixSet from Codility. 100% correctness and performance.

What can be changed to make it even more efficient? (without out using c code).

HOW IT WORKS:

Everytime I come across a number in the array I check to see if I have added it to the dictionary yet.

If it is in the dictionary then I know it is not a new number so not important in relation to the problem. If it is a new number that we haven't come across already, then I need to update the indexOftheLastPrefix to this array position and add it to the dictionary as a key.

It only used one for loop so takes just one pass. Objective-c code is quiet heavy so would like to hear of any tweaks to make this go faster. It did get 100% for performance though.

int solution(NSMutableArray *A)

{

NSUInteger arraySize = [A count];
NSUInteger indexOflastPrefix=0;

NSMutableDictionary *myDict = [[NSMutableDictionary alloc] init];

for (int i=0; i<arraySize; i++)
{
    if ([myDict objectForKey:[[A objectAtIndex:i]stringValue]])
    {

    }
    else
    {
        [myDict setValue:@"YES" forKey:[[A objectAtIndex:i]stringValue]];
        indexOflastPrefix = i;
    }
}

return indexOflastPrefix;

}

---

int solution(vector &A) { // write your code in C++11 (g++ 4.8.2)

int max = 0, min = -1;

int maxindex =0,minindex = 0;

min = max =A[0];

for(unsigned int i=1;i<A.size();i++)
{

    if(max < A[i] )
    {
      max = A[i];
      maxindex =i;

    } 
     if(min > A[i])
     {
         min =A[i];
         minindex = i;
     }

}

if(maxindex > minindex)
       return maxindex;
else
    return minindex;

}

---

fwiw: Also gets 100% on codility and it's easy to understand with only one HashMap

public static int solution(int[] A) {
    // write your code in Java SE 8

    int firstCoveringPrefix = 0;
    //HashMap stores unique keys
    HashMap hm = new HashMap();

    for(int i = 0; i < A.length; i++){
        if(!hm.containsKey(A[i])){
            hm.put( A[i] , i );
            firstCoveringPrefix = i;
        }
    }
    return  firstCoveringPrefix;
}

---

I was looking for the this answer in JavaScript but didn't find it so I convert the Java answer to javascript and got 93%

function solution(A) {
  result=0;
  temp = [];
  for(i=0;i<A.length;i++){
    if (!temp.includes(A[i])){
        temp.push(A[i]);
        result=i;
    }
  }
  return result;
}

---

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

    class Solution {
        public int solution(int[] A) {
            // write your code in Java SE 8
            Set<Integer> s = new HashSet<Integer>(); 
            int index = 0;
            for (int i = 0; i < A.length; i++) {
                if (!s.contains(A[i])) {
                    s.add(A[i]);
                    index = i;
                }
            }
            return index;
        }
    }