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

Companies:

Uber

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

Difficulty: Easy

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

Similar Problems

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

Companies:

Test Cases

Example Input 1

Solution

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