4

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?

4

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)

  • in your example, when you are analyzing the element 1, you will iterate forward until you find an element higher than the current? When all elements in the array are equal, the complexity will be O(n * n). The alternative would be to keep a count of current value elements and also a count of previous inferior value so you can build all the necessary pairs. This way, you will keep the complexity to O(n*log(n).If it's of any help, here's an implementation in C# of what I described earlier: github.com/htoma/codility/blob/master/codility/Code/… – Horia Toma Aug 19 '17 at 15:56
  • @HoriaToma I didn't specify how I would iterate forward. Of course counting the number of the same elements is the best option. This answer was mostly made as a general approach description rather than a full fledged implementation. – Simon Forsberg Aug 30 '17 at 9:30

protected by gnat Aug 19 '17 at 7:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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