NINJA'S JUMP

#include <bits/stdc++.h>
using namespace std;

int ninjaJump(vector<int> &arr, int n) {
    vector<vector<bool>> canReach(n, vector<bool>(2, false));
    canReach[n-1][0] = true;
    canReach[n-1][1] = true;

    int cnt = 1;
    for(int i=n-2 ; i>=0 ; i--) {
        int mini = 1e9, maxi = -1e9;
        int miniind = i, maxiind = i;
        // for odd numbered jump i.e. 1,3,5,7,9 // miniind
        // for even numbered jump i.e. 2, 4, 6  // maxiind
        for(int j=i+1 ; j<n ; j++) {
            if(arr[j]>=arr[i] && arr[j]<mini) {
                mini = min(mini, arr[j]);
                miniind = j;
            }

            if(arr[j]<=arr[i] && arr[j]>maxi) {
                maxi = max(maxi, arr[j]);
                maxiind = j;
            }
        }

        if(miniind!=i) {
            canReach[i][0] = canReach[miniind][1];
        }

        if(maxiind!=i) {
            canReach[i][1] = canReach[maxiind][0];
        }

        if(canReach[i][0]) cnt++;
    }

    return cnt;
    
}

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

int ninjaJump(vector<int> &arr, int n) {
    if (n == 1) return 1; // If there's only one stone, we can start there and are already at the end.

    // DP arrays
    vector<bool> can_reach_odd(n, false);
    vector<bool> can_reach_even(n, false);
    can_reach_odd[n-1] = true;
    can_reach_even[n-1] = true;

    // Monotonic stacks
    vector<int> next_higher(n, -1);
    vector<int> next_lower(n, -1);
    stack<int> stack_higher, stack_lower;

    // Finding next higher indices
    vector<pair<int, int>> indexed_arr(n);
    for (int i = 0; i < n; ++i) {
        indexed_arr[i] = {arr[i], i};
    }
    sort(indexed_arr.begin(), indexed_arr.end());

    for (const auto& p : indexed_arr) {
        int idx = p.second;
        while (!stack_higher.empty() && stack_higher.top() < idx) {
            next_higher[stack_higher.top()] = idx;
            stack_higher.pop();
        }
        stack_higher.push(idx);
    }

    // Finding next lower indices
    sort(indexed_arr.begin(), indexed_arr.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first > b.first || (a.first == b.first && a.second < b.second);
    });

    for (const auto& p : indexed_arr) {
        int idx = p.second;
        while (!stack_lower.empty() && stack_lower.top() < idx) {
            next_lower[stack_lower.top()] = idx;
            stack_lower.pop();
        }
        stack_lower.push(idx);
    }

    // Fill DP arrays
    for (int i = n - 2; i >= 0; --i) {
        if (next_higher[i] != -1) {
            can_reach_odd[i] = can_reach_even[next_higher[i]];
        }
        if (next_lower[i] != -1) {
            can_reach_even[i] = can_reach_odd[next_lower[i]];
        }
    }

    // Count starting indices that can reach the end
    int result = 0;
    for (int i = 0; i < n; ++i) {
        if (can_reach_odd[i]) {
            ++result;
        }
    }
    return result;
}

// Sample usage
int main() {
    vector<int> arr1 = {20, 23, 22, 24, 25};
    vector<int> arr2 = {5, 6, 4, 4, 7};
    vector<int> arr3 = {5, 1, 3, 4, 2};

    cout << ninjaJump(arr1, arr1.size()) << endl; // Output: 2
    cout << ninjaJump(arr2, arr2.size()) << endl; // Output: 3
    cout << ninjaJump(arr3, arr3.size()) << endl; // Output: 3

    return 0;
}

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

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

#include<climits>

int findGreater(vector<int> &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<int> &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<int> &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; }  

Hey everyone, creating this thread to discuss the interview problem - NINJA'S JUMP.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): NINJA'S JUMP