Problem Name: PLAYYY (Play with Arrays)
Problem Link: CodeChef: Practical coding for everyone
Contest Link: Contest Page | CodeChef
Prerequisites: Array, Stacks
Difficulty: Easy
Problem:
Shreya has participated in a Programming Contest. She has been given an array A of N integers. Now, two functions I(X) and J(X) are defined:
I[X]= This is the smallest number Z such that X<Z<=N and A[X]<A[Z].
J[X]= This is the smallest number Z such that X<Z<=N and A[X]>A[Z]
Now, she needs to find for each index i of this array J(I(i)) where 1≤i≤N If such a number does not exist, for particular index i, output −1 as its answer. If such a number does exist, output A[J(I(i))] Help her to find the solution for the above problem.
Quick Explanation:
For each index X for an array of length N, we need to find values of two functions
I[X]= This is the smallest index Z such that X<Z<=N and A[X]<A[Z]
J[X]= This is the smallest index Z such that X<Z<=N and A[X]>A[Z]
If no such index Z exist, then -1 should be considered as an answer for these functions
And then for each index X (0<=X<=N), we need to print A[J(I(X))]
Explanation:
If we notice, then the functions define
I[X]: is the minimum index Z, greater than X for which the value at index Z is strictly greater than the value at index X
Similarly,
J[X]: is the minimum index Z, greater than X for which the value at index Z is strictly less than the value at index X
Therefore, for each index, we need to find these two values.
To accomplish this, we can use the stack data structure here.
We will use two Stacks here.
stGreater: which will keep the track of indices having value strictly greater than the current element
stLesser: which will keep the track of indices having value strictly lesser than the current element
Why stack?
The stack follows LIFO, so it ensures that the first index we get from the stack following our constraints of function, will be the minimum index only.
Here we can do traversal from the end of the array.
For each index X
Firstly, we pop out all the indices from stGreater for which value at the index is less than or equal to A[X]. This ensures that the index at the top of stGreater is the value of I(X) i.e., strictly greater than A[X]. If stGreater is empty then it indicates there exists no such value and we set I[X]=-1.
Similarly, we do for stLesser to find out the value of J(X).
And then we push current index X into both the stacks.
At end, for each index X (0<=X<=N)
we print A[J(I(X))] ensuring I(X)!=-1 and J(I(X))!=-1
Otherwise, we print -1
Solution:
#include <iostream>
#include <stack>
// to store values upto 10^18
typedef unsigned long long int Int;
using namespace std;
int main() {
// to make I/O fast (ignore)
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N; // size of array
cin >> N;
Int A[N]; // array
int I[N], J[N]; // to store value of functions I and J
for (int X = 0; X <= N - 1; X++)
cin >> A[X];
// stacks to track indices for both functions
stack<int> stGreater, stLesser;
// traverse the array from end
for (int X = N - 1; X >= 0; X--) {
// Finding value of I(X)
// remove the indices which dont follow rule of function I
while (!stGreater.empty() and A[stGreater.top()] <= A[X])
stGreater.pop();
// if stGreater stack is empty, no I(X) exists
if (stGreater.empty())
I[X] = -1;
else
I[X] = stGreater.top();
// Finding value of J(X)
// remove the indices which dont follow rule of function J
while (!stLesser.empty() and A[stLesser.top()] >= A[X])
stLesser.pop();
// if stGreater stack is empty, no J(X) exists
if (stLesser.empty())
J[X] = -1;
else
J[X] = stLesser.top();
// push X in both stacks
stGreater.push(X);
stLesser.push(X);
}
// print the output
for (int X = 0; X <= N - 1; X++) {
int i = I[X];
// if I(X) is -1, print -1
if (i == -1) {
cout << -1 << ' ';
} else {
int j = J[i];
// if J(X) is -1, print -1
if (j == -1) {
cout << -1 << ' ';
} else {
// print A[J(I(X))]
cout << A[j] << ' ';
}
}
}
}