5 months ago

slime • 350

Hyderabad

Was this the only problem asked? If not please add other questions as well. Below is my solution for this problem:-

Platform Jump | Solution

While it maybe to use segment tree or fenwick tree to solve it, there exists an elegant solution using only stack! Some of students who gave test often made this mistake of getting into Range query kind of approach.
The main idea is to traverse the platforms from the tallest one and move in both directions (left and right) while keeping track of the number of jumps needed to reach each platform.

Approach:

1. Find the Tallest Platform: Identify the index of the tallest platform. This can be done in O(N) time using a linear search.

2. Traverse Left from the Tallest Platform: Starting from the tallest platform, move leftwards:

   • If the current platform is shorter than the one to its right, it means we can directly jump from the right platform to this one. So, the number of jumps required for the current platform is 1 + jumps[i + 1].
   • If the current platform is taller, we need to find the next platform to the right that is taller than the current one. We then jump to that platform and from there to the current platform. The number of jumps required for the current platform is 1 + jumps[j], where j is the index of the taller platform to the right.

3. Traverse Right from the Tallest Platform: Similarly, starting from the tallest platform, move rightwards:

   • If the current platform is shorter than the one to its left, it means we can directly jump from the left platform to this one. So, the number of jumps required for the current platform is 1 + jumps[i - 1].
   • If the current platform is taller, we need to find the next platform to the left that is taller than the current one. We then jump to that platform and from there to the current platform. The number of jumps required for the current platform is 1 + jumps[j], where j is the index of the taller platform to the left.

C++ Code:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> min_jumps_to_reach(const vector<int>& A) {
    int N = A.size();
    vector<int> jumps(N, 0);
    int tallest_idx = max_element(A.begin(), A.end()) - A.begin();

    // Traverse left from the tallest platform
    for (int i = tallest_idx - 1; i >= 0; --i) {
        if (A[i] < A[i + 1]) {
            jumps[i] = 1 + jumps[i + 1];
        } else {
            int j = i + 1;
            while (j < N && A[j] <= A[i]) {
                j++;
            }
            if (j < N) {
                jumps[i] = 1 + jumps[j];
            }
        }
    }

    // Traverse right from the tallest platform
    for (int i = tallest_idx + 1; i < N; ++i) {
        if (A[i] < A[i - 1]) {
            jumps[i] = 1 + jumps[i - 1];
        } else {
            int j = i - 1;
            while (j >= 0 && A[j] <= A[i]) {
                j--;
            }
            if (j >= 0) {
                jumps[i] = 1 + jumps[j];
            }
        }
    }

    return jumps;
}

int main() {
    int T, N;
    cin >> T;

    for (int t = 0; t < T; ++t) {
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        vector<int> result = min_jumps_to_reach(A);
        for (int i = 0; i < N; ++i) {
            cout << result[i] << " ";
        }
        cout << endl;
    }

    return 0;
}