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)
.
Given an array of n distinct elements, find the minimum number of swaps required to sort the array. This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i'th index must be present at j'th index in the sorted array.
There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1.
Selection Sort requires the minimum number of swaps. Based on Number of Comparisons This is the number of times the algorithm compares elements to sort the input.
Selection sort performs (at most) n – 1 swaps between data elements, while the bubble sort swaps n * (n – 1) / 2 elements in the worst case (when the list is sorted in reverse order).
Consider α = [0, 7, 8, 3, 4, 10, 1, 6, 9, 2, 5]. There is no Sij(α) that can lower |B(α)| by more than 2.
Thinking on amendments to the method…
This solution only works when there are no array elements that are equal.
Feel free to propose generalizations by editing the answer.
Go straight to Conclusion if you want to skip the boring part.
Let`s define the swap operator Sij over the array a:
Sij(a) : [… ai, … aj, …] → [… aj, … ai, …] ∀i, j ∈ [0; |a|) ∩ ℤ : i ≠ j
Let`s also refer to the bitonicity as B(a), and define it more formally:
The obvious facts:
Swaps are symmetric:
Sij(a) = Sji(a)
Two swaps are independent if their target positions don`t intersect:
Sij(Skl(a)) = Skl(Sij(a)) ∀i, j, k, l : {i, j} ∩ {k, l} = ∅
Two 2-dependent swaps undo one another:
Sij(Sij(a)) = a
Two 1-dependent swaps abide to the following:
Sjk(Sij(a)) = Sij(Sik(a)) = Sik(Sjk(a))
Bitonicity difference is always even for equally sized arrays:
(B(a) – B(a')) mod 2 = 0 ∀a, a' : |a| = |a'|
Naturally, ∀i : 0 < i < |a|,
B([ai–1, ai]) – B([a'i–1, a'i]) = sgn(ai – ai–1) – sgn(a'i – a'i–1),
which can either be 1 – 1 = 0, or 1 – –1 = 2, or –1 – 1 = –2, or –1 – –1 = 0, and any number of ±2`s and 0`s summed yield an even result.
N.B.: this is only true if all elements in a differ from one another, same with a'!
Without loss of generality, let`s assume that:
Depending on ai, 3 cases are possible:
When altering ai and leaving all other elements of a intact, |B(a') – B(a)| ≤ 2 (where a' is the resulting array, for which the above 3 cases also apply), since no other terms of B(a) changed their value, except those two from the 1-neighborhood of ai.
Sij(a) implies what`s described above to happen twice, once for ai and once for aj.
Thus, |B(Sij(a)) – B(a)| ≤ 2 + 2 = 4.
Analogously, for each of the corners and j – i = 1 the max. possible delta is 2, which is ≤ 4.
Finally, this straightforwardly extrapolates to ai–1 > ai+1 and aj–1 > aj+1.
QED
{proof in progress, need to sleep}
{proof in progress, need to sleep}
From T1, T2 and T3, the minimal number of swaps needed to minimize |B(a)| equals:
⌊|B(a)| / 4⌋ + ß,
where ß equals 1 if |B(a)| mod 4 ≥ 2, 0 otherwise.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With