Problem
Submissions
Hints & solutions
Discuss
Increasing-Decreasing Array
Moderate
0/80
Contributed by
4 upvotes
Asked in companies
Problem statement
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.
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.
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.
Detailed explanation ( Input/output format, Notes, Images )
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.
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.
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
Sample Input 1 :
2
4
PPN
4
PNN
Sample Output 1 :
1 2 4 3
1 4 3 2
Explanation For Sample Input 1 :
For test case 1 :
We will return { 1, 2, 4, 3 } as A[1] - A[0] = 1(Positive), A[2] - A[1] = 2(Positive), A[3] - A[2] = -1(Negative).
For test case 2 :
We will return { 1, 4, 3, 2 } as A[1] - A[0] = 3(Positive), A[2] - A[1] = -1(Negative), A[3] - A[2] = -1(Negative).
Note that { 2, 4, 3, 1}, { 3, 4, 2, 1} are also valid answers.
Sample Input 2 :
2
5
PPPP
2
NN
Sample Output 2 :
1 2 3 4 5
2 1
Hint
Hint 1
Try to select the smallest or the largest element from the range [1, N] and increment/decrement the range according to the selected element.
Approaches (1)
Approach 1
Constructive Approach
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ā.
Time Complexity
O( N ), where N denotes the size of the array to be returned
We iterate the string of size āN-1ā. We have also used 2 pointers method on integers of range [1, N] causing each number in the range to be visited exactly once.
Hence the time complexity is O( N ).
Space Complexity
O( 1 )
No extra space is used. Hence the space complexity is O( 1 ).
Code Solution
(100% EXP penalty)
Increasing-Decreasing Array
C++ (g++ 5.4)
Console