NINJA'S JUMP
Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.

So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.

For jumping you have to follow below instructions:

You may jump forward from index ‘i’ to index ‘j’ (with i

Question

NINJA'S JUMP

Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.

So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.

For jumping you have to follow below instructions:

You may jump forward from index ‘i’ to index ‘j’ (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index ‘j’ such that ‘arr[i] <= arr[j]’ and ‘arr[j]’ is the smallest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index j.

During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index ‘j’ such that ‘arr[i] >= arr[j]’ and ‘arr[j]’ is the largest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index ‘j’.

It may be the case that for some index ‘i’, there are no legal jumps.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘arr’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.

Output Format:

For each test case, print a single line containing the number of starting indices, from where Ninja can reach the end by following the required jump conditions.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6

Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘arr[i]’ represents the elements of the array.

Time Limit: 1 sec

Accepted Answer

BRUTE APPROACH

The idea here is to use the brute force approach and to travel the whole array for each index we will check if we can reach the last index of the array by following the given conditions.

So we start from our first index and look for the elements which are greater than that element and we choose minimum from that.
After choosing the minimum element now we check do we need an even-numbered count for reaching that element or an odd-numbered count for reaching the element.
Now from that element, we check if we take the same jump the element is smaller than that or not.
- If it is not smaller then the index is not a good starting index.
- Else we repeat the above steps until we reach the end of the array.
Now if we reach the end we increase our ‘ans’ variable by ‘1’.
In this way, we checked for each index of our array.
In the last, we return our ‘ans’ variable.

Space Complexity: O(1)Explanation:

O(1).

As no extra space is required.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ represents the size of the given array.

As for each index, we are traversing the whole array so we have to run two nested loops which make the complexity O(N ^ 2).

Java (SE 1.8)

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(1) 

    Where 'N' represents the size of given array.
*/

import java.util.ArrayList;

public class Solution 
{
    static int findGreater(ArrayList arr, int value, int from, int to)
    {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = from; i < to; i++)
        {
            if (arr.get(i) == value)
            {
                return i;
            }

            if (arr.get(i) > value && min > arr.get(i))
            {
                min = arr.get(i);
                minIndex = i;
            }
        }

        return minIndex;
    }

    static int findSmaller(ArrayList arr, int value, int from, int to)
    {
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;

        for (int i = from; i < to; i++)
        {
            if (arr.get(i) == value)
            {
                return i;
            }

            if (arr.get(i) < value && max < arr.get(i))
            {
                max = arr.get(i);
                maxIndex = i;
            }
        }

        return maxIndex;
    }


    public static int ninjaJump(ArrayList x, int n) 
    {
        if (n < 1)
        {
            return 0;
        }

        int ans = 0;

        for (int i = 0; i < n; i++)
        {
            
            // If we reached the end we exit from the loop.
            if (i == n - 1)
            {
                ans++;
                break;
            }

            int value = x.get(i);
            int index = i;

            while (index < n)
            {
                value = x.get(index);
            
                // We are calling this function to find greater element index.
                index = findGreater(x, value, index + 1, n);

                if (index == n - 1)
                {
                    ans++;
                    break;
                }

                else if (index == -1)
                {
                    break;
                }

                value = x.get(index);
            
                // We are calling this function to find smaller element index.
                index = findSmaller(x, value, index + 1, n);

                if (index == n - 1)
                {
                    ans++;
                    break;
                }

                else if (index == -1)
                {
                    break;
                }
            } 
        }
        
        return ans;
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(1) 

    Where 'N' represents the size of given array.
*/

#include

int findGreater(vector &arr, int value, int from, int to)
{
    int min = INT_MAX;
    int minIndex = -1;

    for (int i = from; i < to; i++)
    {
        if (arr[i] == value)
        {
            return i;
        }

        if (arr[i] > value && min > arr[i])
        {
            min = arr[i];
            minIndex = i;
        }
    }

    return minIndex;
}

int findSmaller(vector &arr, int value, int from, int to)
{
    int max = INT_MIN;
    int maxIndex = -1;

    for (int i = from; i < to; i++)
    {
        if (arr[i] == value)
        {
            return i;
        }

        if (arr[i] < value && max < arr[i])
        {
            max = arr[i];
            maxIndex = i;
        }
    }

    return maxIndex;
}

int ninjaJump(vector &arr, int n)
{
    if (n < 1)
    {
        return 0;
    }

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        
        // If we reached the end we exit from the loop.
        if (i == n - 1)
        {
            ans++;
            break;
        }

        int value = arr[i];
        int index = i;

        while (index < n)
        {
            value = arr[index];
            
            // We are calling this function to find greater element index.
            index = findGreater(arr, value, index + 1, n);

            if (index == n - 1)
            {
                ans++;
                break;
            }
            else if (index == -1)
            {
                break;
            }

            value = arr[index];
            
            // We are calling this function to find smaller element index.
            index = findSmaller(arr, value, index + 1, n);

            if (index == n - 1)
            {
                ans++;
                break;
            }
            else if (index == -1)
            {
                break;
            }
        } 
    }
    
    return ans;
}

Python (3.5)

'''
    Time complexity: O(N ^ 2)
    Space complexity: O(1)

    Where 'N' represents the size of given array.
'''

def findGreater(arr, value, start, end):
    minElement = 10**9
    minIndex = -1

    for i in range(start,end): 
        if (arr[i] == value):
            return i

        if (arr[i] > value and minElement > arr[i]):
            minElement = arr[i]
            minIndex = i
        
    return minIndex

def findSmaller(arr, value, start, end):
    maxElement = 10**9
    maxElement *= -1
    maxIndex = -1

    for i in range(start, end):
        if (arr[i] == value):
            return i

        if (arr[i] < value and maxElement < arr[i]):
            maxElement = arr[i]
            maxIndex = i
        
    return maxIndex

def ninjaJump(arr, n):
    if (n < 1):
        return 0

    ans = 0

    for i in range(n):

        # If we reached the end we exit start the loop.
        if (i == n - 1):
            ans += 1
            break

        value = arr[i]
        index = i

        while (index < n):
            value = arr[index]

            # We are calling this function to find greater element index.
            index = findGreater(arr, value, index + 1, n)

            if (index == n - 1):
                ans += 1
                break

            elif (index == -1):
                break

            value = arr[index]

            # We are calling this function to find smaller element index.
            index = findSmaller(arr, value, index + 1, n)

            if (index == n - 1):
                ans += 1
                break

            elif (index == -1):
                break
                
    return ans

Accepted Answer

MONOTONIC STACK

The idea here is to use the stack as we know that we want to find out the current index and the jump type whether we are taking an even jump or an odd jump. For each index, there are two options either we can make the jump or not. So if we knew these jumps, we can be able to find out the answer in a single traversal.

Firstly we create a 2-D array ‘index’ for storing index and the value of given array as we want to do sorting so that order remains maintained.
Now we sort our ‘index’ array and we start with storing the indices ‘i’ of the processed values v = arr[i] in the stack and try to maintain the invariant that this is monotone decreasing. Whenever we add a new index ‘j’, we pop all the smaller indices ‘i < j’ from the stack, which all jump to ‘j’.
Then, we know ‘oddnext[i]’, the index where ‘i’ jumps to if this is an odd-numbered jump or we can say if the next possible index coming can be possible through odd jump we fill our oddnext and if comes out to be even we fill evennext.
So we repeat the same above steps and store all the possible reachable indices.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ represents the size of the array

As we are using a stack of size ‘N’ also we are using two bool arrays each of size ‘N’.

Time Complexity: O(nlogn)Explanation:

O(N * log(N) ), where ‘N’ represents the size of the given array.

As for each index, we have to pop all the indices which are smaller than the current index takes O(logN) time, and searching in bool takes O(N) time.

Python (3.5)

'''
    Time complexity: O(N * log(N))
    Space complexity: O(N)

    Where 'N' represents the size of given array.
'''

def find_next(index):
    
    nextElement = [0 for i in range(len(index))]

    stk = []

    # Build monotonous stack.
    for i in range(len(index)):

        while(len(stk) > 0 == False and stk[-1] < index[i][0]):
            nextElement[stk[-1]] = index[i][0]

            # Pop the element from stack.
            stk.pop()
        stk.append(index[i][0])

    return nextElement


def ninjaJump(arr, n):
    index = []

    # Initializing the index array.
    for i in range(n):
        index.append([i, arr[i]])

    # Sorting our array.
    index.sort(key = lambda x : (x[1],x[0]))

    # Finding index of next odd element.
    oddNext = find_next(index);
    index.sort(key = lambda x : (-x[1],x[0]))

    # Finding index of next even element.
    evenNext = find_next(index)

    dp =[ [False for j in range(2)] for i in range(n)]
    dp[n - 1][0] = True
    dp[n - 1][1] = True

    # Building dp array.
    for i in range(n-2, -1, -1):
        idx = oddNext[i]
        if (oddNext[i] != 0):
            dp[i][0] = dp[idx][1]

        idx = evenNext[i]
        if (evenNext[i] != 0):
            dp[i][1] = dp[evenNext[i]][0]

    ans = 0

    # Calculating answer.
    for i in range(n):
        ans += dp[i][0]

    return ans

C++ (g++ 5.4)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(N) 

    Where 'N' represents the size of given array.
*/

#include 
#include 

vector find_next(vector> &index)
{
    vector next(index.size());

    // Declared a stack.
    stack stk;

    for (int i = 0; i < index.size(); ++i)
    {
        while (stk.empty() == false && stk.top() < index[i][0])
        {
            next[stk.top()] = index[i][0];

            // Pop the element from stack
            stk.pop();
        }

        stk.push(index[i][0]);
    }

    return next;
}

bool compOdd(vector &a, vector &b) 
{
    if (a[1] < b[1])
    {
        return true;
    }
    
    if(a[1] == b[1] && a[0] < b[0])
    {
        return true;
    }
     
    return false;
}

bool compEven(vector &a, vector &b) 
{
    if (a[1] > b[1])
    {
        return true;
    }
    
    if(a[1] == b[1] && a[0] < b[0])
    {
        return true;
    }
     
    return false;
}



int ninjaJump(vector &arr,int n)
{
    vector> index(n, vector(2));

    // Initializing the index array.
    for (int i = 0; i < n; i++)
    {
        index[i] = {i, arr[i]};
    }

    // Sorting our array.
    sort(index.begin(), index.end(), compOdd);

    // Finding index of next odd element.
    vector oddNext = find_next(index);
    sort(index.begin(), index.end(), compEven);

    // Finding index of next even element.
    vector evenNext = find_next(index);

    vector> dp(n, vector(2,0));
    dp[n - 1][0] = dp[n - 1][1] = true;

    // Iterating through odd and even array.
    for (int i = n - 2; i >= 0; i--)
    {
        if (oddNext[i] != 0)
        {
            dp[i][0] = dp[oddNext[i]][1];
        }

        if (evenNext[i] != 0)
        {
            dp[i][1] = dp[evenNext[i]][0];
        }
    }

    int ans = 0;

    // Iterating the loop.
    for (int i = 0; i < n; ++i)
    {
        ans += dp[i][0];
    }

    return ans;
}

Java (SE 1.8)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(N) 

    Where 'N' represents the size of given array.
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Solution 
{
    static int[] sortArray(ArrayList A,Boolean increase)
    {
        Integer[] idx = new Integer[A.size()];
        for (int i = 0; i < A.size(); i++) idx[i] = i;

        // Sorting array based on even and odd condition.
        if (increase) {
            Arrays.sort(idx, (i, j) -> A.get(i) == A.get(j) ? i - j : A.get(i) - A.get(j));
        }
        else {
            Arrays.sort(idx, (i, j) -> A.get(i) == A.get(j) ? i - j : A.get(j) - A.get(i));
        }
        
        int[] ret = new int[A.size()];
        Arrays.fill(ret, A.size());

        // Declared Stack.
        Stack stack = new Stack<>();
        
        for (int i = 0; i < A.size(); i++) {
            while (!stack.isEmpty() && idx[i] > stack.peek())
            {
                ret[stack.pop()] = idx[i];
            }

            stack.push(idx[i]);
        }
        
        return ret;
    }
    
    public static int ninjaJump(ArrayList x, int n) 
    {
        if (n == 1) return 1;

        int[] odd = sortArray(x, true);
        int[] even = sortArray(x, false);
        

        boolean[][] dp = new boolean[2][n];
        dp[0][n - 1] = true;
        dp[1][n - 1] = true;

        for (int i = n - 2; i >= 0; i--)
        {
            dp[0][i] = odd[i] != n && dp[1][odd[i]];
            dp[1][i] = even[i] != n && dp[0][even[i]];
        }

        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (dp[0][i])
            {
                cnt++;
            }
        }
        
        return cnt;
    }
}

Accepted Answer

Optimized Approach

The idea here is to use the map as a map to help in reducing the time complexity as now we think of starting from right to left and try to check by using the property of map lower_bound and upper_bound, so basically there are two functions which can be called using a map and they can tell whether the larger element is present than the element we pass in this function or smaller element is present.

So first we declare two bool arrays ‘even’ and ‘odd’ for storing that whether we reached that index by an odd jump or even jump and we initialize our odd and even array for ‘n - 1’ as true as we reached there by both even and odd jumps.
Now we start iterating our array and for each element, we check the lower_bound of the current element as we are traversing from right to left so to check whether the greater element is present or not.
- If it comes out true then we will check whether it is possible to go to that element using an even jump or odd jump and update our array accordingly.
- Else we repeat the same steps for the next element.
If we reached the starting element we use upper_bound for checking whether a smaller number is present or not.
Now we count the true in our bool array and that is our required answer,

Space Complexity: O(n)Explanation:

O(N), where ‘N’ represents the size of the given array

As we are using a map of size ‘N’ also we are using two bool arrays each of size ‘N’.

Time Complexity: O(nlogn)Explanation:

O(N * log(N) ), where ‘N’ represents the size of the given array.

As for each index, we are using the map function which uses log(N) time as we are using lower_bound and upper_bound function, and traversing the bool array takes 0(N) time.

C++ (g++ 5.4)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(N) 

    Where 'N' represents the size of given array.
*/

#include 

int ninjaJump(vector &arr, int n)
{
    int ans = 1;

    // Declaring bool arrays.
    vector> dp(n, vector(2,0));

    map umap;

    for (int i = n - 1; i >= 0; i--)
    {

        if (i == n - 1)
        {
            dp[n - 1][0] = dp[n - 1][1] = true;
            umap[arr[n - 1]] = n - 1;
            continue;
        }

        // Finding higher element from map.
        map:: iterator high = umap.lower_bound(arr[i]);

        // Finding lower element from map.
        map:: iterator low = umap.upper_bound(arr[i]);

        if (high != umap.end())
        {
            dp[i][0] = dp[high->second][1];
        }

        if (low != umap.begin())
        {
            --low;
            dp[i][1] = dp[low->second][0];
        }

        if (dp[i][0] == true)
        {
            ans = ans + 1;
        }

        umap[arr[i]] = i;
    }
    
    return ans;
}

Python (3.5)

'''
    Time complexity: O(N * log(N))
    Space complexity: O(N)

    Where 'N' represents the size of given array.
'''

# Balanced Binary search Tree to implement ordered Set.
class orderedSet:

    # TreeNode of BST.
    class TreeNode:
        def height(curNode):
            if curNode == None:
                return 0
            else:
                return curNode.height

        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
            self.height = 1
     
    # Rotate left.
    def rotateLeft(curNode):
        
        node2, node1, node4 = curNode, curNode.left, curNode.right
        node3, node5 = node4.left, node4.right
        node2.right = node3
        node2.height = 1 + max(orderedSet.TreeNode.height(node1), orderedSet.TreeNode.height(node3))
        
        node4.left = node2
        node4.height = 1 + max(orderedSet.TreeNode.height(node2), orderedSet.TreeNode.height(node5))
        
        return node4

    # Rotate Right.
    def rotateRight(curNode):
        node4, node2, node5 = curNode, curNode.left, curNode.right
        node1, node3 = node2.left, node2.right
        node4.left = node3
        node4.height = 1 + max(orderedSet.TreeNode.height(node3), orderedSet.TreeNode.height(node5))
        
        node2.right = node4
        node2.height = 1 + max(orderedSet.TreeNode.height(node1), orderedSet.TreeNode.height(node4))
        
        return node2

    def __init__(self):
        self.root = None

    '''
        Insert Node and Rotate BST to maintain height,
        So that cost of insertion will be O(log(N)).
    '''
    def insert(self, root, data):
        
        # Insert curNode.
        if root == None:
            return orderedSet.TreeNode(data)
        if data < root.data:
            root.left = self.insert(root.left, data)
        elif data > root.data:
            root.right = self.insert(root.right, data)
        
        # Don't add duplicate nodes.
        else:  
            return root
        
        # Rotate BST to maintain height.
        if orderedSet.TreeNode.height(root.left) - orderedSet.TreeNode.height(root.right) >= 2:
            
            if data > root.left.data:
                root.left = orderedSet.rotateLeft(root.left)
            
            root = orderedSet.rotateRight(root)
        
        elif orderedSet.TreeNode.height(root.right) - orderedSet.TreeNode.height(root.left) >= 2:
        
            if data < root.right.data:
                root.right = orderedSet.rotateRight(root.right)
        
            root = orderedSet.rotateLeft(root)
        else:
        
            root.height = 1 + max(orderedSet.TreeNode.height(root.left), orderedSet.TreeNode.height(root.right))
        
        return root

    def addNode(self, data):
        self.root = self.insert(self.root, data)

    def begin(self):
        return self.root.data

    # Return upper bound in log(N).
    def upperBound(self, data):

        curNode = self.root
        ans = None

        while curNode != None:

            if curNode.data >= data:
                ans = curNode.data
                curNode = curNode.left
            else:
                curNode = curNode.right

        return ans

    # Return lower bound in log(N).
    def lowerBound(self, data):

        curNode = self.root
        ans = None

        while curNode != None:

            if curNode.data <= data:
                ans = curNode.data
                curNode = curNode.right
            else:
                curNode = curNode.left

        return ans

def ninjaJump(arr, n):
    
    ans = 1;

    # Declaring bool arrays.
    dp = [ [False for j in range(2)] for i in range(n)]
    
    # Declared ordered Set.
    umap = orderedSet()
    index = {}
    
    evenJump = [0 for i in range(n)]
    oddJump  = [0 for i in range(n)]

    for i in range(n - 1,-1,-1):

        if (i == n - 1):
            dp[n - 1][0] =  True
            dp[n - 1][1] = True
            index[arr[n - 1]] = n - 1
            umap.addNode(arr[n - 1])
            continue

        # Finding higher element from map.
        high = umap.upperBound(arr[i])

        # Finding lower element from map.
        low = umap.lowerBound(arr[i])
        
        if (high != None):
            idx = index[high]
            dp[i][0] = dp[idx][1]

        if (low != None):
            idx = index[low]
            dp[i][1] = dp[idx][0]

        if (dp[i][0] == True):
            ans = ans + 1

        index[arr[i]] = i
        umap.addNode(arr[i])

    return ans;

Java (SE 1.8)

/*
    Time complexity: O(N * log(N))
    Space complexity: O(N) 

    Where 'N' represents the size of given array.
*/

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

public class Solution 
{
    
    public static int ninjaJump(ArrayList x, int n) 
    {
        // Storing the final result.
        int res = 1;

        // Declaring bool arrays with row 1 for storing lower bound and row 2 for upper bound.
        boolean[][] dp = new boolean[2][n];

        dp[1][n - 1] = dp[0][n - 1] = true;
        TreeMap map = new TreeMap<>();
        map.put(x.get(n - 1), n - 1);
        for (int i = n - 2; i >= 0; --i)
        {
            Map.Entry hi = map.ceilingEntry(x.get(i)), lo = map.floorEntry(x.get(i));
            if (hi != null)
            {
                dp[1][i] = dp[0][(int)hi.getValue()];
            }

            if (lo != null)
            {
                dp[0][i] = dp[1][(int)lo.getValue()];
            }

            if (dp[1][i])
            {
                res++;
            }

            map.put(x.get(i), i);
        }
        
        return res;
    }
}

Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.

So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.

For jumping you have to follow below instructions:

You may jump forward from index ‘i’ to index ‘j’ (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index ‘j’ such that ‘arr[i] <= arr[j]’ and ‘arr[j]’ is the smallest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index j.

During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index ‘j’ such that ‘arr[i] >= arr[j]’ and ‘arr[j]’ is the largest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index ‘j’.

It may be the case that for some index ‘i’, there are no legal jumps.

Input Format:

Output Format:

Note :

Constraints:

Top BugsMirror Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern