12

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).

44
  • 1
    @VidorVistrom: All elements are distinct. But in my opinion, I think you want to ask if two adjacent elements are distinct, right? All adjacent elements are distinct. Let me put this in edit as well. Thanks for pointing it out.
    – CodeHunter
    Commented Jul 15, 2017 at 3:54
  • 1
    @YakymPirozhenko Alternating permutation is just one specific case of a bitonic array. It could go {+, -, +, -, ...} or it could also go {+, -, -, -, +, -, +, +}. Both cases have "minimum bitonicity" as defined in this question.
    – darksky
    Commented Jul 21, 2017 at 23:57
  • 1
    @CodeHunter oh I see. So the whole array is not distinct. Then how do you calculate bitonicity of the resulting array aftet a swap that results in adjacent elements being the same? You dont have a condition on what happens when a[i] == a[i - 1].
    – darksky
    Commented Jul 22, 2017 at 4:27
  • 1
    After you swap. For example 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.
    – darksky
    Commented Jul 22, 2017 at 4:32
  • 3
    Okay. Note that with this rule, you are no longer constrained to have a guarantee that adjacent elements in the initial array are distinct. Now they can be the same, and that drastically changes the problem.
    – darksky
    Commented Jul 22, 2017 at 4:47

1 Answer 1

2
+50

URGENT UPDATE: T3 does not hold!

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…

Warning

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.

Introduction

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:

  1. Swaps are symmetric:

    Sij(a) = Sji(a)

  2. 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} = ∅

  3. Two 2-dependent swaps undo one another:

    Sij(Sij(a)) = a

  4. Two 1-dependent swaps abide to the following:

    Sjk(Sij(a)) = Sij(Sik(a)) = Sik(Sjk(a))

  5. 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'!

Theorems

[T1]   |B(Sij(a)) – B(a)| ≤ 4   ∀a, Sij(a)

Without loss of generality, let`s assume that:

  • 0 < i, j < |a| – 1
  • j – i ≥ 2
  • ai–1 < ai+1
  • aj–1 < aj+1

Depending on ai, 3 cases are possible:

  1. ai–1 < ai < ai+1: sgn(ai – ai–1) + sgn(ai+1 – ai) = 1 + 1 = 2
  2. ai < ai–1 < ai+1: sgn(ai – ai–1) + sgn(ai+1 – ai) = –1 + 1 = 0
  3. ai–1 < ai+1 < ai: sgn(ai – ai–1) + sgn(ai+1 – ai) = 1 + –1 = 0

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

[T2]   ∀a : |B(a)| ≥ 2   ∃Sij(a) : |B(Sij(a))| = |B(a)| – 2

{proof in progress, need to sleep}

[T3]   ∀a : |B(a)| ≥ 4   ∃Sij(a) : |B(Sij(a))| = |B(a)| – 4

{proof in progress, need to sleep}

Conclusion

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.

5
  • Really appreciate the effort! +1. Right now, I couldn't find any countercases but I encourage the people related to this question to please verify this. Also, can you please explain the assumption for T1, especially the last 2? There can be a case when a[i–1] > a[i+1] and a[j–1] < a[j+1] and vice versa. I conclude that in that case, B(a) will cancel out eventually and the T1 would still hold. Can you please identify my conclusion on this?
    – CodeHunter
    Commented Jul 23, 2017 at 1:47
  • @CodeHunter exactly. There can be a situation when there`s a +2 in the first place and –2 in the second (or vice versa), so they add nothing to the final sum. [UPD:] Adding proofs… Commented Jul 23, 2017 at 14:41
  • @CodeHunter But I thought if its for industrial practice, you must know the exact swaps. As you mentioned " trading data analysis pattern ", don't you want a mechanism that could tell you the exact swaps? Commented Jul 24, 2017 at 3:43
  • @CodeHunter sorry for breaking my promise to prove this today. Working on it. The main idea for T2 is: to reach at least B(a) = ±2, a must have a chain of at least 3 consecutively incr. or decr. values (bitonicity chain ± → ±). Dealing with 4-chains (± → ± → ±) or more is simple, as we may take any 2 non-edge values and swap them (± → ∓ → ±), thus disrupting the chain. So, what`s left to prove in T2 is that ∓ → ± → ± → ∓ bitonicity chains (let`s call them N-chains as they resemble N-s if drawn in slashes: /\\/) are also capable of being properly disrupted. Commented Jul 24, 2017 at 23:34
  • @hidefromkgb: Cool. I have actually tested the above logic you gave on most of test cases but failed with none. I think the idea is correct!
    – CodeHunter
    Commented Jul 24, 2017 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.