SDE - Intern

I used stack to solve this problem. Here we maintain items in increasing order in the stack (instead of decreasing in next greater element problem).

Push the first element to stack.
Pick rest of the elements one by one and follow following steps in loop.
Mark the current element as next.
If stack is not empty, then compare next with stack top. If next is smaller than top then next is the NSE for the top. Keep popping from the stack while top is greater than next. next becomes the NSE for all such popped elements
Push next into the stack
After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

Tip 1 : Analyse the complexity of every question that you solve
Tip 2 : Practice questions on time complexity
Tip 3 : Read DSA book Cormen thoroughly.

I used lists and recursion to solve the problem.

I created a list and add all values from 1 to n in it. Create a recursive function that takes list, start (position at which counting will start) and k ( number of person to be skipped) as argument. If size of list is one i.e. only one person left then return this position. Otherwise, start counting k person in clockwise direction from starting position and remove the person at kth position. Now the person at kth position is removed and now counting will start from this position. This process continues till only one person left.