Suppose we are given an array of integer. All adjacent elements are guaranteed to be distinct. Let us define bitonicity of this array a
as bt
using the following relation:
bt_array[i] = 0, if i == 0;
= bt_array[i-1] + 1, if a[i] > a[i-1]
= bt_array[i-1] - 1, if a[i] < a[i-1]
= bt_array[i-1], if a[i] == a[i-1]
bt = last item in bt_array
We say the bitonicity of an array is minimum when its bitonicity is 0 if it has an odd number of elements, or its bitonicity is +1 or -1 if it has an even number of elements.
The problem is to design an algorithm that finds the fewest number of swaps required in order to make the bitonicity of any array minimum. The time complexity of this algorithm should be at worst O(n), n being the number of elements in the array.
For example, suppose a = {34,8,10,3,2,80,30,33,1}
Its initial bt
is -2. Minimum would be 0. This can be achieved by just 1 swap, namely swapping 2 and 3. So the output should be 1.
Here are some test cases:
Test case 1: a = {34,8,10,3,2,80,30,33,1}, min swaps = 1 ( swap 2 and 3)
Test case 2: {1,2,3,4,5,6,7}: min swaps = 2 (swap 7 with 4 and 6 with 5)
Test case 3: {10,3,15,7,9,11}: min swaps = 0. bt = 1 already.
And a few more:
{2,5,7,9,5,7,1}: current
bt
= 2. Swap 5 and 7: minSwaps = 1{1,7,8,9,10,13,11}: current
bt
= 4: Swap 1,8 : minSwaps = 1{13,12,11,10,9,8,7,6,5,4,3,2,1}: current
bt
= -12: Swap (1,6),(2,5) and (3,4) : minSwaps = 3
I was asked this question in an interview, and here's what I came up with:
1. Sort the given array.
2. Reverse the array from n/2 to n-1.
3. Compare from the original array how many elements changed their position.
Return half of it.
And my bit of code that does this:
int returnMinSwaps(int[] a){
int[] a = {1,2,3,4,5,6,7};
int[] b = a;
Arrays.sort(b);
for(int i=0; i<= b.length/2 - 1; i++){
swap(b[b.length - i], b[b.length/2 - i]);
}
int minSwaps = 0;
for(int i=0;i<b.length;i++){
if(a[i] != b[i])
minSwaps++;
}
return minSwaps/2;
}
Unfortunately, I am not getting correct minimum number of ways for some test cases using this logic. Also, I am sorting the array which is making it in O(n log n)
and it needs to be done in O(n)
.
{+, -, +, -, ...}
or it could also go{+, -, -, -, +, -, +, +}
. Both cases have "minimum bitonicity" as defined in this question.a[i] == a[i - 1]
.a={1, 3, 4, 1}
. This is valid according to your rule. We swap 3 with the last 1. Then we need to calculate bitonicity, but that is no longer possible.