CODEWITHSUNDEEP
arraysalgorithmlanguage-agnostic
h4ck3d
h4ck3d

Reputation: 6364

Find the Ninja Index of an array

It is an interesting puzzle I came across , according to which , given an array , we need to find the ninja index in it.

A Ninja index is defined by these rules :

An index K such that all elements with smaller indexes have values lower or equal to A[K] and all elements with greater indexes have values greater or equal to A[K].

For example , consider :

A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.

In this case, 5 is a ninja index , since A[r]<=A[5] for r = [0,k] and A[5]<=A[r] r = [k,n].

What algorithm shall we follow to find it in O(n) . I already have a brute force O(n^2) solution.

EDIT : There can be more than 1 ninja index , but we need to find the first one preferably. And in case there is no NI , then we shall return -1.

Upvotes: 8

Views: 465

Answers (4)

tobias_k
tobias_k

Reputation: 82929

Another Python solution, following the same general approach. Maybe a bit shorter.

def ninja(lst):
    maxs = lst[::]
    mins = lst[::]
    for i in range(1, len(lst)):
        maxs[   i] = max(maxs[   i], maxs[ i-1])
        mins[-1-i] = min(mins[-1-i], mins[-i  ])
    return [i for i in range(len(lst)) if maxs[i] <= lst[i] <= mins[i]]

I guess it could be optimized a bit w.r.t that list-copying-action, but this way it's more concise.

Upvotes: 2

Victor Sorokin
Victor Sorokin

Reputation: 12006

This straight-forward Java code calculates leftmost index that has property "all elements rightwards are not lesser":

private static int fwd(int[] a) {
    int i = -1;
    for (int j = 0; j < a.length - 1; j++) {
        if (a[j + 1] >= a[j] && i == -1) {
            i = j + 1;
        } else if (i != -1 && a[j + 1] < a[i]) {
            i = -1;
        }
    }
    return i;
}

Almost same code calculates leftmost index that has property "all elements leftwards are not greater":

private static int bwd(int[] a) {
    int i = -1;
    for (int j = 0; j < a.length - 1; j++) {
        if (a[j + 1] >= a[j] && i == -1) {
            i = j + 1;
        } else if (i != -1 && a[j + 1] < a[i]) {
            i = -1;
        }
    }
    return i;
}

If results are the same, leftmost Ninja index is found.

Upvotes: 0

etzourid
etzourid

Reputation: 21

A python solution that will take O(3n) operations

def n_index1(a):
    max_i = []
    maxx = a[0]
    for j in range(len(a)):
        i=a[j]

        if maxx<=i and j!=0:
            maxx=i
            max_i.append(1)

        else:
            max_i.append(-1)



    return max_i

def n_index2(a):
    max_i = []
    maxx = -a[len(a)-1]
    for j in range(len(a)-1,-1,-1):
        i=-a[j] # mind the minus

        if maxx<=i and j!=len(a)-1:         
            maxx=i
            max_i.append(1)

        else:
            max_i.append(-1)

    return max_i

def parse_both(a,b):
    for i in range(len(a)):
        if a[i]==1 and b[len(b)-1-i]==1:
            return i

    return -1


def ninja_index(v):
    a = n_index1(v)
    b = n_index2(v)

    return parse_both(a,b)

Upvotes: 2

Rafał Dowgird
Rafał Dowgird

Reputation: 45131

Precompute minimum values for all the suffixes of the array and maximum values for all prefixes. With this data every element can be checked for Ninja in O(1).

Upvotes: 8

Related Questions