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

Companies:
  • Uber Interview Questions

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