My approach is using Topological Sorting.
But for buidling the Graph, I am using set. This set contains all the unmarked indices. I am connecting a directed edge from pi to pj if pi<pj. I think this way my graph will contain O(n^2) edges and thus it gives me TLE.
I know that my approach is correct, but how can I implement a better way of topological Sort such that it does not take O(n^2) time.
My code for reference:
Hey @ayushjain.iitg
Great code. Your code structure is representative of a great upcoming competitive coder. Kudos for that !!
Your logic needs some mending.
Firstly, all the -1 values. In the order in which they appear, you can assign them largest value in decreasing order. This way all -1 values will be filled.
Then each value gives index of next higher value. This way chains will be formed. Start assigning values in chains in ascending order.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
@Aarnav-Jindal-1059677350830863 Is it possible to have a one-to-one chat when you come online on this platform ?! That would be really efficient
Sure buddy. You can message me on chat and we can schedule a time to come chat on the platform.