my approach- i made a copy of the array, and sorted the copy of the array...
now i traverse the given array,and find the correspoding position of the element in the sorted array...
now ,i check if there is any position in between the indexes of both of the position(i.e the given array,and the sorted) which is not allowed to swap.. if there is then the answer is no....
here is the solution....
but the tag that i saw in the question was of dfs...any approach on how dfs will be implemented...
Asked by: Shubham_Gupta on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
Firstly, please use the fact that all elements are in range of 1 to n and occur exactly once. So do you need to create the vector "ss" that you have used and sort it? The position in sorted array of any element will be the element itself.
Second, this would have been my approach. Let us create islands using the provided binary string. A group of 1s and a single following 0 forms one island. Any other 0 forms another island.
Example, for the string: 1110110
We have two islands, [1110] and [110]
Similarly, for the string 0110010, we will get following islands [0], [110], [0], [10].
Now, any number in one island cannot jump to another island by any possible swapping. Any number in the island can move within the island by any possible swapping. So we just have to check that all numbers in an island are in the range of the island position. That is, if an island extends from 1st position to 4th position, all the elements in the orginal array in 1st to 4th position should be in the range [1,4]. Can't see use of DFS, nor sorting. Single traversal.
