Given an array of size `n`

in which two elements were swapped by mistake. Sort this array in one swap. It is guaranteed that such a solution exists. This array doesn’t contain duplicates

### Test Cases

#### Example Input 1

`Input Array: 1 2 3 6 5 4`

`Expected Output: 1 2 3 4 5 6`

In the above test case, if we swap element `4`

and element `6`

, we will get back the sorted array.

## Solution

Let’s say that our original array was a_{0}, a_{1}, a_{2}, a_{3}, … a_{n}. Since our original array was sorted, we can say that

a_{0} < a_{1} < a_{2} < a_{3}, … < a_{n}

Let’s say that the two elements which got swapped from the above array were located at index `i`

and index `j`

respectively.

Therefore, we can say that for new elements at indexes `i`

and `j`

, the following equations hold.

- a
_{i}> a_{i+1} - a
_{j-1}> a_{j}

Therefore, we need to find both of these indexes and swap them to get back the original array. We can do that in just one iteration as shown in the below code

## Solution Implementation

#include <bits/stdc++.h> using namespace std; void swap(vector<int>& vec, int i, int j) { int temp = vec[i]; vec[i] = vec[j]; vec[j] = temp; } int main() { vector<int> vec = { 1, 2, 3, 6, 5, 4 }; int firstIndex = -1, secondIndex = -1; for(int i = 0; i < vec.size() - 1; i++) { if (vec[i] > vec[i+1]) { if (firstIndex == -1) { firstIndex = i; } else { secondIndex = i; } } } swap(vec, firstIndex, secondIndex + 1); for(int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n"; }