We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Implementation
- Almost Sorted
- Discussions
Almost Sorted
Almost Sorted
Sort by
recency
|
483 Discussions
|
Please Login in order to post a comment
sort the input and compare with the input to get the difference and append to new list. if new list only has 2 values, we can assume that we only need to swap to achieve final result. if new list has more than 2 values, check that the corresponding values are in order.
Java
I enjoyed this coding
can anyone tell me what is wrong wirh this code ? when i am dry running for input 3 1 2 my code shoudl give correct output but its not idk why
void almostSorted(vector arr) { vector nums = arr; sort(nums.begin(), nums.end()); int swap = 0; int first = -1; int second; int start, ending; //3 1 2
}
Here's a "simple" linear solution in python runs in O(n) time complexity. I handled some special edge cases separately when length of array is two and three, other than that I ran a loop and make note of changes in array changes to note 1. Number of elements need to be swapped 2. Number of elements in continous reverse order 3. Add all indexes of above elements in a new array
After that just needed to analyze the values of above changes and made some logical checks