Last Updated: 29 Aug, 2021
Ninja’s Circular Array
Moderate
Asked in companies
Ninja has a circular array ‘Nums’ containing ‘N’ positive integers. An array is called circular if we consider the first element as next of the last element.
Ninja wants you to find the first greater number to the right of each element in the array, if there is no greater element to the right of an element, then output -1 for this element.
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 array.
The second line of each test case contains N positive integers denoting the array elements ‘Nums[i]’.
Output Format :
For each test case, print the next greater elements for each element in the circular array.
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
1 <= N <= 200
1 <= Arr[i] <= 10^5
Time limit: 1 sec
Approaches
For each number in the array, find the first greater element to its right by simply iterating the array circularly.
The steps are as follows :
- Initialize an array “ans” of size equal to N to store the NGE(next grater element) of each element of the input array.
- Iterate the input array “Nums”, for each element in the array run a while loop to find the first greater element to the right, terminate the while loop if visited all the remaining N-1 elements.
- Finally, return “ans”.
For a simple non-circular array we can find the next greater element by:
Iterating the array Nums and maintaining a stack to store the indices. We push the current index into the stack if the stack is empty or the current element is less than or equal to the element whose index is on the top of the stack.
If the current element is greater than the element whose index is on the top then the NGE(next grater element) for the index on the top of the stack is the current element and we pop out that index from the stack, we keep repeating this till the stack remains non-empty and till the current element is greater, after that push the current index into the stack.
In the end, the indices that will remain in the stack will have their NGE’s as -1. This can be tackled by initializing all the elements as -1.
To convert the above logic to include the fact that the given array is circular, simply iterate from 0th to 2*n-1th index. And while accessing the index, use its value modulo N (the fact that the array is circularly sorted).
The steps are as follows :
- Initialize an array “ans” of size equal to N and all its elements equal to -1 to store the NGE of each element of the input array.
- Initialize a stack data structure “st”.
- Run a loop for i from 0 to 2*N-1.
- In each iteration run a while loop till the stack “st” is non-empty and till the element at the top index of the stack is lesser than the element at i % N, for each iteration of the while loop set value of the index on top of the stack in “ans” array as the element at (i % N)th position in “Nums”, and also pop out the index on the top from the stack.
- After running the while loop insert the (i % N)th into the stack.
- Finally, return “ans”.
Similar problems