Compute Adjacent Pair

Question

I was given the following problem:

Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given. 
A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value 
in the array lies strictly between values A[P] and A[Q].
For example, in array A such that:
A[0] = 0 A[1] = 3 A[2] = 3
A[3] = 7 A[4] = 5 A[5] = 3
A[6] = 11 A[7] = 1
the following pairs of indices have adjacent values:
(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
For example, indices 4 and 5 have adjacent values because there is no value in array A that lies 
strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4, 
and it is not present in the array.
Write a function that returns number of adjacent values

My solution was as follows:

• For each pair, check whether there is any other element that is within this range
• If not, increment adjacentPair count
• Else, proceed to another pair.

This approach takes O(N^3). I wanted to know if there is a better way of solving this?

Answer 1

The input array that you have is:

0, 3, 3, 7, 5, 3, 11, 1

Imagine that the array instead would be this:

0, 1, 3, 3, 3, 5, 7, 11

If the array were organized like that, then you could loop through the array and more easily count pairs.

0 --> 1
1 --> 3, 3, 3
3 --> 3, 3, 5
3 --> 3, 5
3 --> 5
5 --> 7
7 --> 11

That's 1 + 3 + 3 + 2 + 1 + 1 + 1 = 12 pairs. The same number as you found before. Coincidence? I think not.

Now if there just was a way to re-order the array to make it look like this.... Oh, I know!

Time complexity? O(n) for the looping and counting pairs in the sorted array, and O(n log n) for sorting the array. So O(n log n + n) = O(n log n)