Hello,
I got AC in this problem. I used python as my language. But the time taken was somewhere around 2 seconds. My query is that whether the problem is in my algorithm or is it because python is slower in comparison to other languages.
Here is my algorithm description:
- Take the input in a stack.
- Start popping elements from the stack into a queue till you find an element such in the stack such that the next one is less than it. Lets denote the top element of stack now as x
- Start dequeuing the queue pushing the elements in stack. As soon as you find the 1st element greater than x, swap it with x and then continue dequeuing till the queue is empty.
Here is my code:
from collections import deque
def print_num(list1):
for item in list1:
print(item, end="")
T = int(input())
rn = range
ln = len
li = list
for test in range(T):
length = int(input())
given_number = li(map(int, input().split()))
new_list = deque()
for i in rn(1, length + 1):
if ln(given_number) != 1:
if given_number[-1] <= given_number[-2]:
new_list.append(given_number.pop())
else:
break
count = 0
temp = 0
fix_number = given_number
if ln(given_number) == 1:
print("-1")
continue
elif ln(new_list) == 0:
given_number[-1], given_number[-2] = given_number[-2], given_number[-1]
print_num(given_number)
else:
new_list.append(given_number.pop())
while ln(new_list) != 0:
given_number.append(new_list.popleft())
count += 1
if given_number[-1] > given_number[-1 - count] and temp == 0:
given_number[-1], given_number[-1 - count] = given_number[-1 - count], given_number[-1]
temp += 1
print_num(given_number)
print()
I have used aliases for functions to make my code faster.
So can there be a better algorithm?
