0

Given an unsorted array I want to find the number of unique pairs that are not sorted from highest to lowest.

If the array was { 3, 5, 9, 2, 6 } then the pairs would be (3, 5), (3, 9), (3, 6), (5, 9), (5, 6), (2, 6). Therefore the result would be 6 (the number of pairs).

What sort of algorithm (or data structure) would work faster than O(n^2) time. I've investigated heapsort which seemed promising but I'm unsure how to move forward after sorting the array in O(nlogn).

Note: the result could be on the order of billions, but should be calculated in seconds

Sung Jinwoo
  • 39
  • 5
  • 1
    Do you want generate all pairs or just calculate number of pairs? – yuri777 May 08 '22 at 07:16
  • 1
    @OleV.V., they are not asking for generating the pairs. They write *"Find number of..."* and *"Therefore the result would be 6"*. – trincot May 08 '22 at 07:26
  • 1
    @yuri777, isn't this clear from the question? *"Find number of..." and *"Therefore the result would be 6". – trincot May 08 '22 at 07:28

0 Answers0