Given an array where all its elements are sorted except two elements which were swapped, sort the array in linear time. Assume there are no duplicates in the array.

For example,

**Input:** A[] = [3, 8, 6, 7, 5, 9] OR [3, 5, 6, 9, 8, 7] OR [3, 5, 7, 6, 8, 9]

**Output:** A[] = [3, 5, 6, 7, 8, 9]

The idea is to start from the y element in the array and compare every element with its previous element. We take two pointers (say x and y) to store location of the conflict. If previous element is greater than the current element, we update x to the index of previous element and y to the index of current element. If again at some point we find that previous element is greater than the current element, we update y to index of current element. Finally, after we are done processing each adjacent pair of elements, we swap the elements present at index x and index y.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <algorithm> using namespace std; void sortArray(int arr[], int n) { int x = -1, y = -1; int prev = arr[0]; // process each adjacent pair of elements for (int i = 1; i < n; i++) { // if previous element is greater than the current element if (prev > arr[i]) { // first occurrence of conflict if (x == -1) x = i - 1, y = i; else // second occurrence of conflict y = i; } prev = arr[i]; } // swap the elements present at index x and index y swap(arr[x], arr[y]); } // main function int main() { // int arr[] = { 3, 8, 6, 7, 5, 9 }; int arr[] = { 3, 5, 6, 9, 8, 7 }; int n = sizeof(arr) / sizeof(arr[0]); sortArray(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; } |

`Output:`

3 5 6 7 8 9

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
import java.util.Arrays; class Sort { private static void sortArray(int[] arr) { int x = -1, y = -1; int prev = arr[0]; // process each adjacent pair of elements for (int i = 1; i < arr.length; i++) { // if previous element is greater than the current element if (prev > arr[i]) { // first occurrence of conflict if (x == -1) { x = i - 1; y = i; } else { // second occurrence of conflict y = i; } } prev = arr[i]; } // swap the elements present at index x and index y swap(arr, x, y); } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { int[] a = { 3, 5, 6, 9, 8, 7 }; sortArray(a); System.out.println(Arrays.toString(a)); } } |

`Output: `

[3, 5, 6, 7, 8, 9]

The time complexity of above solution is `O(n)` as it does only one scan of the input array and auxiliary space used by the program is `O(1)`.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply