## Similar Problems

Similar Problems not available

# Sort An Array Containing Zeroes Ones and Twos In Linear Time - Leetcode Solution

## Companies:

LeetCode: Sort An Array Containing Zeroes Ones and Twos In Linear Time Leetcode Solution

Difficulty: Easy

Topics: sorting

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.

- ai > ai+1
- 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

## Sort An Array Containing Zeroes Ones and Twos In Linear Time Solution Code

`1`