Ninja’s Circular Array

Moderate
0/80
profile
Contributed by
24 upvotes
Asked in companies
MicrosoftGoldman Sachs

Problem statement

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.
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 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
Sample Input 1 :
2
5
1 6 4 3 5
3
1 2 1
Sample Output 1 :
6 -1 5 5 6
2 -1 2
Explanation For Sample Input 1 :
For test case 1 : 
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.

For test case 2 :
We will return { 2, -1, 2 } because 2 is the first element to the right of 1 that is greater than 1, no element exists that is greater than 2, 2  is the first element to the circular-right of 1 that is greater than 1.
Sample Input 2 :
2
1
500
4
1 2 3 4
Sample Output 2 :
-1
2 3 4 -1
Hint

Can you take advantage of the small constraints?

Approaches (2)
Brute Force

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”.
Time Complexity

O( N ^ 2 ), where N denotes the size of the array 

 

For each array element in the worst case, we will have to run a while loop to iterate the remaining N-1 elements. This will happen if all the elements in the array have the same values.

Hence the time complexity is O( N ^ 2 ).

Space Complexity

O( 1 )


No extra space is used. Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Ninja’s Circular Array
Full screen
Console