 # Sort an array in one swap where two elements are swapped by mistake

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 a0, a1, a2, a3, … an. Since our original array was sorted, we can say that

a0 < a1 < a2 < a3, … < an

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.

1. ai > ai+1
2. aj-1 > aj

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";

}```

Scroll to Top