I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example: Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:


First we will link A to B Then when we have a look at B, we will link B to C Next when we consider X, we will link X to Y Next when we consider C, we will link C to D ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time. Not to mention it doesn't work. What might be a better algorithm?

Here is what the current algorithm is:

for(i in list)
  while (i and j) is not linked 
     increment j
  if j is not the end
     while ++j is not the end  
       if link exists (i and j)
     end while
     set link i to j
  end if
end for

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..? Can anyone point me in the right direction please?

  • $\begingroup$ Is this helpful: stackoverflow.com/questions/41403587/… and geeksforgeeks.org/closest-pair-of-points-onlogn-implementation $\endgroup$
    – Rob
    Commented Sep 13, 2018 at 1:55
  • $\begingroup$ @Rob Thats it, closest pair algorithm I think, thanks $\endgroup$
    – solarflare
    Commented Sep 13, 2018 at 2:07
  • 1
    $\begingroup$ @Rob thanks for that. I'm going to wait in case someone else has a better solution as a divide and conquer algorithm with 2 quicksorts might in fact be overkill in my situation when there's going to be 20 conditions for the sort. $\endgroup$
    – solarflare
    Commented Sep 13, 2018 at 2:30
  • $\begingroup$ If you could specify which algorithm you wanted to use in your question it would narrow down the answer to a speed/complexity appropriate answer. I suggested that algorithm because you wanted an improvement over $O(n^2)$. $\endgroup$
    – Rob
    Commented Sep 13, 2018 at 3:03

1 Answer 1


An alternative approach could be

  1. Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$

  2. Then you have two choices

    • Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
    • Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.

  • $\begingroup$ I like it. But as I have been informed by the business analysts the use case will never have more than around 7 or 8 items in it so I'm going with brute force. $\endgroup$
    – solarflare
    Commented Sep 14, 2018 at 0:03
  • 1
    $\begingroup$ "X will never happen" might be the quickest way to shoot yourself in the foot though. $\endgroup$
    – Aristu
    Commented Sep 14, 2018 at 0:36
  • $\begingroup$ @solarflare just like Aristu said, never trust the fact that the use case once specified will still be enforced many years later. Its always safer to use a condition like ' if (sizeof(dataset)<threshold) then doBruteForce() else doEfficientAlgo()'. $\endgroup$ Commented Sep 14, 2018 at 4:44
  • $\begingroup$ I don't want to reveal the industry or use case but trust me if it did happen it would be an incredibly bizarre (and somewhat laughable) rarity. If it happens, they can wait an extra 2 seconds we don't mind. Thanks for all the tips guys, much appreciated. $\endgroup$
    – solarflare
    Commented Sep 14, 2018 at 5:22

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.