Raj - 1 year ago 89

Java Question

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];

index=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.

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--) {
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;
}
```