Raj Raj - 1 year ago 134
Java Question

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){

for(each element in Array)
return index;

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

Answer Source

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--) {
    // 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;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download