Last Updated: 30 Aug, 2021
Increasing-Decreasing Array
Moderate
Asked in companies
Axel is busy with his football match and wants you to solve his math assignment.
You are given an integer ‘N’ denoting the size of the array and you are given a string ‘S’ of size equal to ‘N-1’ containing only characters ‘P’ and ‘N’.
You have to find an array consisting of unique elements in the range [1, N] which satisfies the following constraints:
A [ i + 1 ] - A [ i ] > 0 if and only if S [ i ] = ‘P’
A [ i + 1 ] - A [ i ] < 0 if and only if S [ i ] = ‘N’
for all 'i' belonging to [0, N-1] inclusive
In other words, ‘P’ and ‘N’ denote whether the difference between adjacent array elements is Positive or Negative.
Note:
If there are multiple answers possible, return any one of them.
Custom Test Case:
If you are running a custom test case, then 1 will be printed if the returned array is correct, else 0 will be printed.
If you wish to check your output then use print statements before returning the final answer.
For Example :
If N = 5 and the array is: { 1, 6, 4, 3, 5 }
We will return { 6, -1, 5, 5, 6 }
because 6 is the first element to the right of 1 that is greater than 1,
no element exists that is greater than 6,
5 is the first element to the right of 4 that is greater than 4,
5 is the first element to the right of 3 that is greater than 3,
6 is the first element to the circular-right of 5 that is greater than 5.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the size of the answer array.
The second line of each test case contains a string ‘S’ of length equal to ‘N-1’ containing only ‘P’ or ‘N’ characters.
Output Format :
For each test case, print the elements of the array, the elements should be unique and should be in the range from [1, N].
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return an array that stores the answer to each test case.
Constraints :
1 <= T <= 10
2 <= N <= 20000
S.length = N-1
S[i] = { ‘P’, ‘N’ }
Time limit: 1 sec
Approaches
Set the start pointer to ‘1’ and end pointer to ‘N’, start to end denotes the current range of available numbers.
Iterate the given string ‘S’, if the current character is ‘P’ then insert the element being pointed by ‘start’ and increment the value of start, if the current character is ‘N’ then insert the element being pointed by ‘end’ and decrement the value of end. In the end, we will be left with just one element being pointed by both start and end, insert this element and return the answer.
This works because if the current character is ‘P’, inserting the smallest element of our current range will make sure that the next element inserted will surely be greater than the current element, resulting in A[i+1] - A[i] > 0. A similar thing is true if the largest element of our range is inserted when the current character is ‘N’.
The steps are as follows :
- Initialize an array “ans” to store the answer.
- Initialize and set the value of “st” equal to ‘1’ and “en” equal to ‘N’.
- Iterate the string ‘S’, if the current character is equal to ‘P’ then insert “st” to “ans” and increment the value of “st”, else if the current character is equal to ‘N’ then insert “en” to “ans” and decrement the value of “en”.
- After iterating the string, insert “st” to “ans”.
- Finally, return “ans”.
Similar problems